求助：同模二元一次同余方程组的Python求解算法开发

Hey there! Let's break down how to solve this system of linear congruences step by step. I'll walk you through the math first, then give you a complete Python implementation that covers all possible cases: unique solution, infinitely many solutions, or no solution at all.

Mathematical Background #

Your system looks like this:

ax + by ≡ c (mod n)
dx + ey ≡ f (mod n)

We can frame this using matrix notation for clarity:

[ a b ] [x]   ≡ [c] (mod n)
[ d e ] [y]     [f]

The key here is the determinant of the coefficient matrix: D = (a*e - b*d) % n. The determinant tells us everything about the solution set:

1. Case 1: gcd(D, n) = 1
   The coefficient matrix is invertible modulo n, which means there's a unique solution modulo n. We can use Cramer's rule here:

   • Find the modular inverse of D (using the Extended Euclidean Algorithm)
   • Calculate x ≡ D⁻¹ * (e*c - b*f) mod n
   • Calculate y ≡ D⁻¹ * (a*f - d*c) mod n

2. Case 2: gcd(D, n) = g > 1
   For solutions to exist, both (e*c - b*f) and (a*f - d*c) must be divisible by g. If not, no solution exists. If yes, we can reduce the system modulo n/g to get a system with a unique solution, then generate all g distinct solutions modulo n.

3. Case 3: D ≡ 0 mod n
   The two equations are linearly dependent. We need to check if they're consistent:

   • If the second equation isn't a valid multiple of the first (mod n), no solution exists.
   • If they are consistent, we're left with a single linear congruence ax + by ≡ c mod n. This equation has infinitely many solutions if gcd(a, b, n) divides c; otherwise, no solution.

Python Implementation #

First, let's write helper functions for core modular arithmetic tasks:

def extended_gcd(a, b):
    """Return (gcd, x, y) such that a*x + b*y = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return (gcd, y - (b // a) * x, x)

def mod_inverse(a, n):
    """Return the modular inverse of a modulo n, or None if it doesn't exist"""
    gcd, x, _ = extended_gcd(a, n)
    if gcd != 1:
        return None
    else:
        return x % n

def solve_single_congruence(a, b, c, n):
    """Solve ax + by ≡ c mod n. Returns info about the solution set."""
    g = extended_gcd(extended_gcd(a, b)[0], n)[0]
    if c % g != 0:
        return "No solution exists for the single congruence."
    
    # Reduce the equation to coprime coefficients
    a_red = a // g
    b_red = b // g
    c_red = c // g
    n_red = n // g
    
    # Find one particular solution
    inv_a = mod_inverse(a_red, n_red)
    if inv_a is not None:
        x0 = (c_red * inv_a) % n_red
        y0 = 0
    else:
        inv_b = mod_inverse(b_red, n_red)
        y0 = (c_red * inv_b) % n_red
        x0 = 0
    
    # General solution parameterized by integer k
    return f"Infinitely many solutions. General form:\n x ≡ {x0} + {b_red}*k (mod {n_red})\n y ≡ {y0} - {a_red}*k (mod {n_red})\n where k is any integer."

Now the main function to solve the system:

def solve_congruence_system(a, b, c, d, e, f, n):
    n = abs(n)
    if n == 0:
        return "Modulus n cannot be zero."
    
    D = (a * e - b * d) % n
    g_D_n = extended_gcd(D, n)[0]
    
    # Numerators for Cramer's rule
    num_x = (e * c - b * f) % n
    num_y = (a * f - d * c) % n
    
    if g_D_n == 1:
        # Unique solution exists
        inv_D = mod_inverse(D, n)
        x = (inv_D * num_x) % n
        y = (inv_D * num_y) % n
        return f"Unique solution modulo {n}:\n x ≡ {x}\n y ≡ {y}"
    else:
        if D == 0:
            # Linearly dependent equations; check consistency
            if (a*f - d*c) % n != 0 or (b*f - e*c) % n != 0:
                return "No solution exists: equations are linearly dependent but inconsistent."
            else:
                # Solve the single valid congruence
                return solve_single_congruence(a, b, c, n)
        else:
            # Determinant shares a common divisor with n
            if num_x % g_D_n != 0 or num_y % g_D_n != 0:
                return "No solution exists for the system."
            else:
                # Reduce system to find base solution, then generate all solutions
                n_new = n // g_D_n
                a_new = a // g_D_n
                b_new = b // g_D_n
                c_new = c // g_D_n
                d_new = d // g_D_n
                e_new = e // g_D_n
                f_new = f // g_D_n
                
                # Get unique solution for reduced system
                D_new = (a_new * e_new - b_new * d_new) % n_new
                inv_D_new = mod_inverse(D_new, n_new)
                x0 = (inv_D_new * (e_new * c_new - b_new * f_new)) % n_new
                y0 = (inv_D_new * (a_new * f_new - d_new * c_new)) % n_new
                
                return f"Infinitely many solutions modulo {n}. General form:\n x ≡ {x0} + {(e // g_D_n)}*k (mod {n})\n y ≡ {y0} - {(a // g_D_n)}*k (mod {n})\n where k is any integer (0 ≤ k < {g_D_n} gives all distinct solutions modulo {n})."

# Example user input handling
if __name__ == "__main__":
    print("Enter coefficients for the system:")
    a = int(input("a: "))
    b = int(input("b: "))
    c = int(input("c: "))
    d = int(input("d: "))
    e = int(input("e: "))
    f = int(input("f: "))
    n = int(input("n: "))
    
    result = solve_congruence_system(a, b, c, d, e, f, n)
    print("\n" + result)

Testing the Code #

Let's verify with a few examples:

• Unique solution: System 3x + 2y ≡ 1 mod7, x + y ≡3 mod7 returns x≡2, y≡1 mod7 (check: 32+21=8≡1 mod7; 2+1=3 mod7).
• No solution: System 2x +4y≡1 mod6, x+2y≡2 mod6 returns "No solution exists: equations are linearly dependent but inconsistent."
• Infinitely many solutions: System 2x +4y≡2 mod6, x+2y≡1 mod6 returns the general solution for the single congruence.

内容的提问来源于stack exchange，提问作者polko