Modular Linear Equation
Solving the modular linear equation ax≡b (mod n): solutions exist if and only if gcd(a,n) divides b, and there are exactly gcd(a,n) of them.
Purpose
To solve modular equations and understand when division is possible under modular arithmetic.
Mechanism
Let d=gcd(a,n). If d does not divide b, there is no solution. Otherwise, use the extended Euclidean algorithm to find the unique solution of (a/d)·x0 ≡ b/d (mod n/d); all solutions are x0 + k*(n/d) mod n for k=0..d-1.
Use cases
- Cryptographic equation solving
- Modular arithmetic
- Number-theoretic computation