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).

Easy now: Multiply on both sides by 23 (mod 130).(2) Hence solve the equation

says that x= 12n+ 8. Putting that into gives or . 7 is small enough that we don't have to use the Euclidean algorithm above: just checking numbers shows that . That is, we have which means that n= 7k+ 5. Putting that into x= 12n+ 8 gives x= 12(7k+ 5)+ 8= 84k+ 68.and

Give the general solution tot he following system of equivalences

Thanks to anyone who can help

Now becomes or simply 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 , and that .