1. ## Questions using mod

Its been ages since I have done any maths and im a little rusty. Can someone please show me how to do these?

(1) Find $17^{-1} mod \ 130$
(2) Hence solve the equation $17x \equiv 123 (mod 130)$

and

Give the general solution tot he following system of equivalences

$x \equiv 3 (mod \ 5)$
$x \equiv 5 (mod \ 7)$
$x \equiv 8 (mod \ 12)$

Thanks to anyone who can help

2. Originally Posted by woody198403
Its been ages since I have done any maths and im a little rusty. Can someone please show me how to do these?

(1) Find $17^{-1} mod \ 130$
Search for a number, n, such that 17n= 1 (mod 130). That is the same as saying that 17n= 130m+ 1 or 17n- 130m= 1 for some integers m and n.
17 divides into 130 7 times with remainder 11.
11 divides into 17 once with remainder 6.
6 divides into 11 once with remainder 5.
5 divides into 6 once with remainder 1.
That is: 6- 5= 1. From 5= 11- 6, 6- (11- 6)= 2(6)- 11= 1. From 6= 17- 11, 2(17- 11)- 11= 2(17)- 3(11)= 1. Finally, from 11= 130- 7(17), 2(17)- 3(130- 7(17))= 23(17)- 3(130)= 1.

One solution to 17n- 130m= 1 is n= 23, m= 3. That is 23(17)= 3(130)+1 so 17(23)= 1 (mod 130).

(2) Hence solve the equation $17x \equiv 123 (mod 130)$
Easy now: Multiply on both sides by 23 (mod 130).

and

Give the general solution tot he following system of equivalences

$x \equiv 3 (mod \ 5)$
$x \equiv 5 (mod \ 7)$
$x \equiv 8 (mod \ 12)$

Thanks to anyone who can help
$x \equiv 8 (mod \ 12)$ says that x= 12n+ 8. Putting that into $x \equiv 5 (mod 7)$ gives $12n+ 8\equiv 5n+ 1\equiv 5(mod 7)$ or $5n\equiv 4 (mod 7)$. 7 is small enough that we don't have to use the Euclidean algorithm above: just checking numbers shows that $5*5= 25\equiv 4 (mod 7)$. That is, we have $n\equiv 5 (mod 7)$ which means that n= 7k+ 5. Putting that into x= 12n+ 8 gives x= 12(7k+ 5)+ 8= 84k+ 68.

Now $x\equiv 3 (mod 5)$ becomes $84k+ 68\equiv 4k+ 3\equiv 3 (mod 5)$ or simply $4k= 0 (mod 3)$ which means k is a multiple of 3: k= 3j so x= 84k+ 68= 252j+ 68. If we take j= 0, x= 68. It is easy to see that $68= 13(5)+ 3\equiv 3 (mod 5)$, $68= 9(7)+ 5\equiv 5 (mod 7)$ and that $68= 5(12)+ 8\equiv 8 (mod 12)$.