Number theory problem about Fermat 's little theorem

  • Thread starter yeland404
  • Start date
  • #1
23
0

Homework Statement



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

Homework Equations



n^7 [itex]\equiv[/itex] n mod 42

n^13 [itex]\equiv[/itex] 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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619

Homework Statement



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

Homework Equations



n^7 [itex]\equiv[/itex] n mod 42

n^13 [itex]\equiv[/itex] 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.
 
  • #3
23
0
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
Dick
Science Advisor
Homework Helper
26,263
619
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.
 
  • #5
Dick
Science Advisor
Homework Helper
26,263
619
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.
 

Related Threads on Number theory problem about Fermat 's little theorem

Replies
4
Views
3K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
6K
Replies
6
Views
984
  • Last Post
Replies
1
Views
928
Top