yeland404 said: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?
yeland404 said: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 said: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.
Fermat's Little Theorem is a fundamental theorem in number theory that states that if p is a prime number, then for any integer a, the number ap - a is divisible by p.
Fermat's Little Theorem is often used to prove the primality of a number or to find the remainder when a number is divided by a prime number. It can also be used to simplify complex number theory problems.
No, Fermat's Little Theorem only applies to prime numbers. It cannot be used to determine the primality of composite numbers.
Fermat's Little Theorem is a cornerstone of modern number theory and has many applications in cryptography, coding theory, and other fields. It also paved the way for other important theorems, such as Euler's Theorem and Wilson's Theorem.
While Fermat's Little Theorem is a powerful tool in number theory, it does have some limitations. It cannot be used to prove the primality of all prime numbers, and it is not applicable to all number theory problems. Additionally, there are some cases where the theorem may not hold, such as when the base number a is not relatively prime to the modulus p.