Linear Congruence Examples

Number Theory · Axiom Academy

EXAMPLE Linear Congruence Examples Solving ax ≡ b (mod n) with unique, multiple, and no solutions Excellent work! You've learned how to solve linear congruences. Here's what we covered: Existence of Solutions: A linear congruence ax ≡ b (mod n) has solutions if and only if gcd(a, n) divides b. Number of Solutions: If solutions exist, there are exactly gcd(a, n) incongruent solutions modulo n. Finding Solutions: When gcd(a, n) = 1, find the multiplicative inverse of a modulo n, then multiply both sides by this inverse. Multiple Solutions: When gcd(a, n) > 1, simplify the congruence by dividing through by the gcd, then solve in a reduced modulus. No Solutions: If gcd(a, n) does not divide b, the congruence has no solutions. These principles are fundamental to number theory and cryptography. Practice with different examples to build mastery!

This is the written version of the interactive lesson above. See the full Number Theory course.