Thread: Euclidan Algorithm linear congruence

Use Extended Euclidan Algorithm to find a solution to the linear congruence 16x=11(mod23)

Originally Posted by knights

Use Extended Euclidan Algorithm to find a solution to the linear congruence 16x=11(mod23)

The congruence is equivalent to the equation 16x + 23y = 11. Use the extended euclidean algorithm to find integers x' and y' such that 16x' + 23y' = 1. Then multiply by 11 to get x and y.

Originally Posted by Opalg

The congruence is equivalent to the equation 16x + 23y = 11. Use the extended euclidean algorithm to find integers x' and y' such that 16x' + 23y' = 1. Then multiply by 11 to get x and y.

could you work this out for me?

i'd like to see this also but im still confused

16 divides into 23 once with remainder 7. That is, 1(23)- (1)16= 7. 7 divides into 16 twice with remainder 2: 1(16)- 2(7)= 2. 2 divides into 7 3 times with remainder 1: 1(7)- 3(2)= 1 so 1(7)- 3(16- 2(7))= 7(7)- 3(16)= 1.
7(23- 16)- 3(16)= 7(23)- 10(16)= 1.

So one solution to 16x'+ 23y'= 1 is x'= -10, y'= 7. so x= -10(11)= -110 and y= 7(11)= 77 satisfy 16x+ 23y= 11. But that means x= -110+ 23k and y= 77- 16k are solutions for all k because 16(-110+ 23k)+ 23(77- 16k)= -1760+ (16)(23)k+ 1771- (23)(16)k= 1 for all k.

Now, what values of k make both -110+ 23k and 77- 16k non-negative and less than 23?