# Number theory problem about Fermat 's little theorem

1. Feb 11, 2012

### yeland404

1. The problem statement, all variables and given/known data

let n be an integer . Prove the congruence below.
n^21 $\equiv$ n mod 30

2. Relevant equations

n^7 $\equiv$ n mod 42

n^13 $\equiv$ n mod 2730

3. The attempt at a solution

to prove 30| n^21-n，it suffices to show 2|n^21-n,3|n^21-n,5|n^21-n
and how to prove them?

2. Feb 11, 2012

### Dick

2|n^21-n should be pretty easy. Just think about odd and even. To start on the second one n^3=n mod 3. n^(21)=(n^3)^7. Now keep going.

3. Feb 11, 2012

### yeland404

then n^21-n = n(n^20-1), suppose n is even , then 2|n^21-n
if n is odd, n^20 is odd, so n^20-1 is even;

to 3, it means n^21=(n^3）^7=n^7=(n^3)^2*n
then how is the next to prove 3|n(n^20-1)

4. Feb 11, 2012

### Dick

You are almost there with this line, "to 3, it means n^21=(n^3）^7=n^7=(n^3)^2*n". Think about it a little more and you will get it.

5. Feb 12, 2012

### Dick

Keeping thinking n^3=n, n^3=n.