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

Printable View

- Mar 8th 2009, 11:27 PMknightsEuclidan Algorithm linear congruence
Use Extended Euclidan Algorithm to find a solution to the linear congruence 16x=11(mod23)

- Mar 9th 2009, 02:18 AMOpalg
- Mar 9th 2009, 04:20 AMJoeBabble
- Mar 9th 2009, 11:35 AMHallsofIvy
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?