Linear congruence help

I'm totally confused about how to solve linear congruences, could someone please go through the steps (as simply as possible), I promise to rep!!
I have this example 11x (congruent to) 4 mod (19), and apparently the answer is x (congruent to) 9 mod (19). What are the steps to get this?
Thanks :smile:

Reply 1

KAISER_MOLE

Use the extended Euclidean algorithm

11a + 19b = 1

19 = 11 + 8
11 = 8 + 3
8 = 2*3 + 2
3 = 2 + 1

So

1 = [3] - [2]
= ([11]-[8]) - [8] + 2[3]
= 3[11] -4[8]
= 3[11] - 4[19] + 4[11]
= 7[11] - 4[19]

so a=7 b=-4 works.

To get it as 4, which is the required form, multiply through by 4, gives 28[11] = 4mod19

and 28 is congruent to 9mod19

Reply 2

mikesgt2

Just to explain why the euclidean algorithm is useful here...

11x = 4 (mod 19) iff 19|(11x-4) iff 11x-4 = 19y (some y) iff 11x-19y = 4

The euclidean algorithm givs us a method of finding integers a,b with 11a+19b = 1, because hcf(11,19) = 1. But if this holds, then 11(4a)+19(4b) = 4, so (x,y) = (4a,-4b) solves the equation above. Therefore x = 4a will solve the congruence.

Reply 3

lauzy

KAISER_MOLE

so a=7 b=-4 works.

To get it as 4, which is the required form, multiply through by 4, gives 28[11] = 4mod19

and 28 is congruent to 9mod19

Thanks guys, I understand what u have done as far as here but I don't understand what you mean by 4 being the required form and also what does it mean for 28 to be congruent to 9mod19? Thanks

Reply 4

mikesgt2

I realised there were mistakes in my post, they're corrected now.

Now first things first, if you don't know what it means for 28 to be congruent to 9 modulo 19 then you have no hope in solving linear congruences. Look in your notes and make sure you know the very basics, then come back and read this.

To solve this congruence we first use the euclidean algorithm to get 11(7)-19(4) = 1. But then, multiplying by 4 and rearranging gives

11(28)-4 = 19(16)

So 19|(11(28)-4), that is 11(28) = 4 (mod 19). As 28 = 9 (mod 19) we get 11(9) = 4 (mod 19) so x = 9 solves the linear congruence.