Thread: Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

1. Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

This one ..well I hope it's ok ..bit rusty on the mods.
To find the reciprocal of 3 (mod 22) we must first ensure it exists by finding if they have 1 as their greatest common factor(thanks HallofIvy) remembered to put this
gcd(22,3): 22 = 7 ⋅ 3 + 1 1 = 22 ⋅ 1 – 3 ⋅ 7
-7 ⋅ 3 ≡ 1 (mod 22)

3x ≡ 5 (mod 22)
-7 ⋅ 3x ≡ -7 ⋅ 5 (mod 22)[multiply both sides by -7]
1x ≡ -35 (mod 22) [sub in 7 ⋅ 3 ≡ 1 (mod 22)]
x ≡ -13 (mod 22) [add 22 to -35]
x ≡ 9 (mod 22)[add 22 to -13]

Which I’m pretty sure works because 5 mod 22 ≡ {...,-39,-17,5,27,49,71, ...}
So you just find one that 3 goes into (27) to get 3x9 ≡ 5 mod 22, so x ≡ 9 (mod 22)

Is this ok??

2. Re: Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

Yes, that is ok. And it is easy to check that 3(9)= 27= 22+ 5= 5 (mod 22).
Frankly, I wouldn't have bothered to check on the "gcd" since if there is no solution, that will appear while trying to solve.

Here is how I would solve "3x= 5 (mod 22)". That is the same as 3x- 22y= 5 for integers x and y. Now, 3 divides into 22 7 times with remainder 1: 22- 3(7)= 1. So one solution to "3x- 22y= 1" is x= -7, y= -1. From that, one solution of "3x- 22y= 5" is x= -7(5)= -35= - 44+ 9= 9 (mod 22) and y= -1(5)= -1= -22+ 21= 21 (mod 22).

So the solution to the problem is x= 9 (mod 22).