# Number theory problem about Fermat 's little theorem

## 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 Helper

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

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
Homework Helper
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