# Thread: Fermat's

1. ## Fermat's

Find least nonnegative residue... n=99^999999 m=23

Let n be an integer. Prove each congruence below.
a. n^21 is congruent to n mod 30
b. n^7 congruent to n mod 42
c. n^13 is congruent to n mod 2730

Let a E Z and let p be a prime number. Prove that p|a^p + (p-1)!a and p|(p-1)!a^p +a

2. Originally Posted by kel1487
a. n^21 is congruent to n mod 30
I do this first one - others should be similar. Let (Z_30)* be the multiplicative group of the units of (Z_30) under multiplication. A consequence of the Chinese Remainder Theorem is that (Z_30)* is isomorphic to the group (Z_2)* x (Z_3)* x (Z_5)* and this group in turn is isomorphic to G = (Z_2) x (Z_4). Note the group G has the property that any element raised to the power of four returns the identity. Therefore, if gcd(n,30)=1 then we can regard n being in (Z_30)* and so n^4 is the identity. Thus, n^4 = 1 (mod 30) if gcd(n,30)=1. This means n^21 = (n^4)^5 = 1 (mod 30).

A simple calculation will prove that this problem is true for n=2,3,5. Now let n be an integer (not divisible by 30 - otherwise the problem is trivial). Then gcd(n,30)=1,2,3,5,6,10,15. If the gcd = 1 then that is the case above. If gcd = 2 then it mean we can write n=2m where gcd(m,30)=1. But this means n^21 = (2m)^21 = 2^21 * n^21 = 1 (mod 30). The situation is similar if gcd = 3 or 5 because we proved this special cases. Say that gcd = 6. Then we can write n = 2*3*m where gcd(m,30)=1. But then n^21 = 2^21 * 3^21 * m^21 = 1 (mod 30). The same situation if gcd = 10 because then we could write n=2*5*m. And repeat the argument.

3. Originally Posted by kel1487
Let a E Z and let p be a prime number. Prove that p|a^p + (p-1)!a and p|(p-1)!a^p +a
1) a^p + (p-1)!a = a + (-1)a = 0 (mod p)
2)a^p(p-1)! + a = a(-1) + a = 0 (mod p)