Solving Congruent Equations

Congruent Equations and Relatively Prime Numbers

  • Question: How to know when an answer can be found for a congruent equation and when it cannot?

  • Examples:

    • A: 3x≡1(mod7)3x \equiv 1 \pmod{7}
    • B: 2x≡1(mod4)2x \equiv 1 \pmod{4}

Difference Between Congruent Equations

  • Observation: The key difference lies in the relationship between the coefficient of x and the modulus.

  • In example A, 3 and 7 are relatively prime.

  • In example B, 2 and 4 are not relatively prime because 2 divides into 4 perfectly.

Relatively Prime Condition

  • If the coefficient of x and the modulus are relatively prime (i.e., their greatest common divisor is 1), then the congruent equation ax≡1(modm)ax \equiv 1 \pmod{m} always has a solution.

  • Example:

    • In 3x≡1(mod7)3x \equiv 1 \pmod{7}, GCD(3, 7) = 1, so a solution exists.
    • In 2x≡1(mod4)2x \equiv 1 \pmod{4}, GCD(2, 4) = 2, so a solution does not exist.

Solving Congruent Equations

Guess and Check Method

  • For small values of 'a' (coefficient of x) and 'n' (modulus), one can use the guess and check method.

  • However, this method is not ideal for large values.

Euclidean Algorithm

  • The Euclidean algorithm can be used to solve ax≡1(modn)ax \equiv 1 \pmod{n}.

  • It helps find the inverse of 'a' modulo 'n'.

Steps:
  1. Find the GCD of a and n.
    • If GCD(a, n) ≠ 1, there is no inverse, and thus no solution.
  2. Use the Extended Euclidean Algorithm (Bézout's Identity).
    • Find integers 's' and 't' such that sa+tn=GCD(a,n)=1sa + tn = \text{GCD}(a, n) = 1
    • 's' is the inverse of 'a' modulo 'n'.

Bézout's Coefficients

  • Find 's' and 't' such that sa+tn=1sa + tn = 1.

  • ss is the inverse of aa.

Explanation

  • Starting with sa+tn=1sa + tn = 1, take modulo mm.

  • sa+tn≡1(modm)sa + tn \equiv 1 \pmod{m}

  • Since tntn is a multiple of mm, tn≡0(modm)tn \equiv 0 \pmod{m}.

  • Therefore, sa≡1(modm)sa \equiv 1 \pmod{m}, which means ss is the inverse of aa modulo mm.

Finding the Inverse Using the Euclidean Algorithm: Example

Problem
  • Find the inverse of 7 modulo 32, i.e., solve 7x≡1(mod32)7x \equiv 1 \pmod{32}.
Steps

  1. Check GCD(7, 32).

    • Use the Euclidean algorithm to find the GCD.

    • 32=4⋅7+432 = 4 \cdot 7 + 4

    • 7=1⋅4+37 = 1 \cdot 4 + 3

    • 4=1⋅3+14 = 1 \cdot 3 + 1

    • 3=3⋅1+03 = 3 \cdot 1 + 0

    • GCD(7, 32) = 1, so 7 and 32 are relatively prime.

  2. Express remainders.

    • 32=4⋅7+432 = 4 \cdot 7 + 4
    • 7=1⋅4+37 = 1 \cdot 4 + 3
    • 4=1⋅3+14 = 1 \cdot 3 + 1

  3. Isolate 1 and work backwards.

    • Goal: Find 1=s⋅7+t⋅321 = s \cdot 7 + t \cdot 32

    • Start with 1=4−1⋅31 = 4 - 1 \cdot 3

    • Replace 3: 1=4−1⋅(7−1⋅4)=2⋅4−1⋅71 = 4 - 1 \cdot (7 - 1 \cdot 4) = 2 \cdot 4 - 1 \cdot 7

    • Replace 4: 1=2⋅(32−4⋅7)−1⋅7=2⋅32−9⋅71 = 2 \cdot (32 - 4 \cdot 7) - 1 \cdot 7 = 2 \cdot 32 - 9 \cdot 7

  4. Result:

    • 1=2⋅32−9⋅71 = 2 \cdot 32 - 9 \cdot 7

    • So, s=−9s = -9 and t=2t = 2.

  5. Find the inverse.

    • The inverse of 7 modulo 32 is -9.
    • To find a positive inverse, add multiples of 32: −9+32=23-9 + 32 = 23

  6. Verification:

    • −9⋅7=−63≡1(mod32)-9 \cdot 7 = -63 \equiv 1 \pmod{32}
    • 23⋅7=161≡1(mod32)23 \cdot 7 = 161 \equiv 1 \pmod{32}

  7. General Solution:

    • The inverse can be represented as −9+n⋅32-9 + n \cdot 32 or 23+n⋅3223 + n \cdot 32 for any integer n.

Inverse and Solutions

  • Given ax≡k(modm)ax \equiv k \pmod{m}, finding the inverse of 'a' modulo 'm' helps solve the equation.

Example:

  • Solve 7x≡5(mod32)7x \equiv 5 \pmod{32}

    • Find the inverse of 7 modulo 32 (which is -9 or 23).

    • Multiply both sides by -9: −9⋅7x≡−9⋅5(mod32)-9 \cdot 7x \equiv -9 \cdot 5 \pmod{32}

    • This simplifies to x≡−45(mod32)x \equiv -45 \pmod{32}

    • Since −45+64=19-45 + 64 = 19, x≡19(mod32)x \equiv 19 \pmod{32}

Example 2

22x≡5(mod41)22x \equiv 5 \pmod{41}

  1. Find the inverse of 22 mod 41

Important

When encountering "if and only if" statements, prove both directions of the implication.