2012/031) Show that for each integer n, n^13 = n mod 2730

first factorize 2730 = 13*7*5*3*2

So we are done if we can show that n^13 == n (mod k), for k=2,3,5,7, and 13.

Use both forms of the Little Theorem...

n^p == n (mod p), for all prime p and a^(p-1) == 1 (mod p) for prime p, when p does not divide n.

Clearly n^13 == n mod 13 ---- (1)

n^13 = n = 0 mod 7 if n is multiple of 7 

if n is co-prime to 7 then 

Also n^7 == n (mod 7) and
n^6 == 1 (mod 7), so
(n^7)*(n^6) = n^13 == n mod 7 ---(2)

n^13 = n = 0 mod 5 if n is multiple of 5

if n is coprime to 5
Again, n^5 == n (mod 5)
and n^4 == 1 (mod 5) => n^8 == 1 (mod 5)
Hence n^13 == n (mod 5) ---(3)

n^13 = n = 0 mod 3 if n is multiple  of 3

if n is coprime to3

n^2 = 1 mod 3
so n^12 = 1 mod 3 Taking power 6

n^13 = n mod 3 . (4)

n^13 = n = 0 mod 2 if n is multiple of 2

if n is coprime to 2

n^2 = n mod 2

so n^12 = n^ 6 mod 2 = n^3 mod 2

so n^13 = n^4 mod 2 = n^2 mod 2 = n mod 2 ...5

so from 1,2,3,4,5 we get

n^ 13 = n mod 2730

Source(s):

http://en.wikipedia.org/wiki/Fermat%27s_…