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 $\displaystyle 17^{-1} mod \ 130$
(2) Hence solve the equation $\displaystyle 17x \equiv 123 (mod 130)$

and

Give the general solution tot he following system of equivalences

$\displaystyle x \equiv 3 (mod \ 5)$
$\displaystyle x \equiv 5 (mod \ 7)$
$\displaystyle 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 $\displaystyle 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 $\displaystyle 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

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

Thanks to anyone who can help
$\displaystyle x \equiv 8 (mod \ 12)$ says that x= 12n+ 8. Putting that into $\displaystyle x \equiv 5 (mod 7)$ gives $\displaystyle 12n+ 8\equiv 5n+ 1\equiv 5(mod 7)$ or $\displaystyle 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 $\displaystyle 5*5= 25\equiv 4 (mod 7)$. That is, we have $\displaystyle 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 $\displaystyle x\equiv 3 (mod 5)$ becomes $\displaystyle 84k+ 68\equiv 4k+ 3\equiv 3 (mod 5)$ or simply $\displaystyle 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 $\displaystyle 68= 13(5)+ 3\equiv 3 (mod 5)$, $\displaystyle 68= 9(7)+ 5\equiv 5 (mod 7)$ and that $\displaystyle 68= 5(12)+ 8\equiv 8 (mod 12)$.