Questions on solving linear congruences - Please answer whichever ones you can :)

Printable View

• Mar 13th 2011, 03:31 AM
ironz
Questions on solving linear congruences - Please answer whichever ones you can :)
I have to solve the congruence 15x = 45 mod 50. I used the normal equals sign as I can't get the three one.

To solve it, I did this:

General linear congruence is ax = b mod n (a,n)=d, where d is the greatest common factor.

(a,n) = (15,50) = 5 .................. 5 divides 45 => solutions exist.

15x = 45 mod 50 is the same as 3x = 9 mod 10

Greatest common factor of (3,10) = 1, and therefore the inverse of 3 exists, which means that x = 3mod 10.

I don't understand how to get the answer for that very last bit. So what if the inverse exists? Does that mean you simply divide 9 by the number in front of the x? Why not the 10 as well? What if the inverse didn't exist?

Thank you :)
• Mar 14th 2011, 07:26 AM
HallsofIvy
Here is how I would solve such a problem:
15x= 45 (mod 50). Since both 15 and 45 are divisible by 5, that becomes 3x= 9 (mod 50).

That means that 3x= 9+ 50y for some integer y. That is the same as 3x- 50y= 9

Now, 3 divides into 50 16 times with a remainder 2. 2 divides into 3 once with remainder 1.

That is, 3- 2= 1 and 50- 3(16)= 2. Then 3- (50- 3(16))= 3(17)- 50= 1 and, multiplying by 9, 3(153)- 50(9)= 9. That is, x= 153= 3 (mod 50),

Check: 15*3= 45 which is, of course, 45 (mod 15).
• Mar 14th 2011, 10:30 AM
Soroban
Hello, ironz!

I too have an alternate approach . . .

Quote:

$\displaystyle 15x \:\equiv\:45\text{ (mod 50)}$

We have: .$\displaystyle 15x \:=\:50a + 45$

Solve for $\displaystyle x\!:\;\;3x \:=\:10a + 9 \quad\Rightarrow\quad x \:=\:\dfrac{10a+9}{3}$

And we have: .$\displaystyle x \:=\:3a + 3 + \dfrac{a}{3}$ .[1]

Since $\displaystyle \,x$ is an integer, $\displaystyle \,a$ must be a multiple of 3: .$\displaystyle a \,=\,3b$

Substitute into [1]: .$\displaystyle x \:=\:3(3b) + 3 + \dfrac{3b}{3} \quad\Rightarrow\quad x\;=\;10b + 3$

Therefore: .$\displaystyle x \:\equiv\:3,\,13,\,23,\,33,\,43 \text{ (mod 50)}$