Number theory problem about Fermat 's little theorem

[yeland404]

Homework Statement

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

Homework Equations

n^7 \equiv n mod 42

n^13 \equiv n mod 2730

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?

 

[Dick]

Homework Statement

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

Homework Equations

n^7 \equiv n mod 42

n^13 \equiv n mod 2730

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|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.

 

[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)

 

[Dick]

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)

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.

 

[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.

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