How do you solve linear congruences?

Hi all,

So we just covered solving congruence's in my discrete 1 class. Our professor gave us 1 example in the notes, and to be honest it sucked and I don't understand it at all. Can someone explain to me how you solve this linear congruence(the one example she did in class)

http://i58.tinypic.com/ftj9xf.jpg

Re: How do you solve linear congruences?

Can we assume that you know what "congruent modulo 27" **means**? Two numbers, x and y, are "congruent modulo 27" if and only if there difference, x- y, is a multiple of 27. Equivalently, if they have the same remainder when divided by 27.

Here, the problem is to find x such that 10x= 2 (mod 27). That is the same as saying that 10x= 27k+ 2 and that is the same as the "Linear Diophantine" equation 10x- 27k= 2.

10 divides into 27 twice with remainder 7: 27- 2(10)= 7.

7 divides into 10 once with remander 2: 10- 7= 3.

3 divides into 7 twice with remainder 1: 7- 2(3)= 1

Replace the "3" in that last equation with 10- 7: 7- 2(10- 7)= 3(7)- 2(10)= 1.

Replace the "7" in that equation with 27- 2(10): 3(27- 2(10))- 2(10)= 3(27)- 8(10)= 1.

Multiply through by 2: 6(27)- 16(10)= 2.

So one solution is x= -16, k= -6. But adding any multiple of 27 to x and any multiple of 10 to k is also a solution:

10(-16+ 27n)- 27(-6+ 10n)= -160+ 270n-(-162+ 270n)= 2 for any integer n:

x= -16+ 27n, k= -6+ 10n. In particular, taking n= 1 gives x= -16+ 27= 11, the only solution lying between 0 and 27.

As a check, 10(11)= 110= 4(27)+ 2.