Solve the congruence 150x ≡ 680 (mod 823) for 0 ≤ x ≤ 823, given that gcd(150,823) = 1?

Favorite Answer

Since gcd(10, 823) = 1, we can divide both sides of the congruence by 10 without reducing the modulus, obtaining 15x ≡ 68 (mod 823).

(Of course, since gcd(150, 823) = 1 and 15 | 150, we have gcd(15, 823) = 1.)

Now, we use the Euclidean Algorithm to find 15^(-1) (mod 823).
823 = 54 * 15 + 13
15 = 1 * 13 + 2
13 = 6 * 2 + 1.

So, 13 - 6 * 2 = 1
==> 13 - 6(15 - 13) = 1
==> 7 * 13 - 6 * 15 = 1

So, 7(823 - 54 * 15) - 6 * 15 = 1
==> 7 * 823 - 384 * 15 = 1

Thus, -384 * 15 ≡ 1 (mod 823)
==> 15^(-1) ≡ -384 ≡ 439 (mod 823).
----------
So, multiplying both sides of 15x ≡ 68 (mod 823) by 439 yields
x ≡ 68 * 439 ≡ 224 (mod 823).

I hope this helps!...Show more