Thread: 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
(2) Hence solve the equation

and

Give the general solution tot he following system of equivalences





Thanks to anyone who can help

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

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

Easy now: Multiply on both sides by 23 (mod 130).

and

Give the general solution tot he following system of equivalences





Thanks to anyone who can help

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.

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 .