Thread: Two problems with Fermat and Wilson

Prove that if is a reduced residue system modulo m, and m is odd, then (mod m).

and

What is the remainder when is divided by 5?

Any help would be appreciated! Thanks!

Originally Posted by kyldn6

Prove that if is a reduced residue system modulo m, and m is odd, then (mod m).

and

What is the remainder when is divided by 5?

Any help would be appreciated! Thanks!

First let us write r_1,..., r_s for the Reduced Residue System (RRS), for simplicity, with s = Phi(m).

Asumme m > 2 so that phi(m) > 1, and let r be any of the elements in the
RRS DIFFERENT from 1, and put S = r_1 +...+ r_s, so:

r*S = r(r_1 +...+ r_s) = r*r_1 +...+ r*r_s = S , since for any 1 <= i <=

there exists 1 <= j <= s s.t. r*r_i = r_j (the RRS is closed under multiplication).

Thuis, we got rS = S ==> S = 0 since r is not 1.

as for 473^38 mod 5: the powers of integers ending in 3 have a period 4, and the last digit in each power is 3,9,7,1,3,9,7,1,...etc.

So all we must know is 38 = 2 (mod 4) ==> 473^38 ends with 9 ==> 473^38 equals 4 mod 5 (or if you want: the remainder of 473^38 when divided by 5 is 4)

Tonio