1. Euclidan Algorithm linear congruence

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

2. 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.

3. 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

4. 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?