Solving 7x ≡ 3 (mod 11)

Discrete Math · Axiom Academy

EXAMPLE Solving Modular Equations Use the Extended Euclidean Algorithm to find multiplicative inverses and solve linear congruences. Excellent work! You've successfully solved a modular equation using the Extended Euclidean Algorithm. Here's what we learned: Inverse Exists When gcd = 1: The multiplicative inverse of a modulo n exists if and only if gcd( a , n ) = 1. This is why we first checked gcd(7, 11) = 1. Extended Euclidean Algorithm: This powerful method not only finds the gcd but also expresses it as a linear combination: 1 = 7s + 11t. The coefficient s is our inverse! Back-Substitution: Working backwards through the Euclidean algorithm steps allows us to express 1 in terms of the original numbers. Solving the Equation: Once we have the inverse, we multiply both sides by it to isolate x . Since 7 × 8 ≡ 1 (mod 11), multiplying by 8 "cancels" the 7. Verification is Important: Always check your solution: 7(2) = 14 ≡ 3 (mod 11) ✓ This technique is fundamental in number theory and cryptography. You can use it to solve any linear congruence ax ≡ b (mod n ) when gcd( a , n ) = 1!

This is the written version of the interactive lesson above. See the full Discrete Math course.