Fermat's Little Theorem and Exponential Congruences

  • Thread starter kmeado07
  • Start date
  • Tags
    Theorem
In summary, using Fermat's Little Theorem, we can deduce that for any prime number p, n^p is equivalent to n (mod p) for all integers n. This is because dividing n^p by n is equivalent to dividing n^(p-1) by n, which is equivalent to 1 (mod p) according to Fermat's Little Theorem. This holds true for all integers n, even when p divides n, by starting with Fermat's Little Theorem and then multiplying by n.
  • #1
kmeado07
40
0

Homework Statement



From fermat's little theorem deduce that when p is prime,

n^p is equivalent to n (mod p)

for all integers n.

Homework Equations





The Attempt at a Solution



I know from Fermat's Little Theorem that ,

n^(p-1) is equivalent to 1 (mod p),

but i don't know how to use it for this particular question.
 
Physics news on Phys.org
  • #2
If a is equivalent to b mod(p) then c*a is equivalent to c*b mod(p). What might be a good choice for c in your problem?
 
  • #3
ok, so in my question, c=n ?
So by dividing by n i would get,

1^p is equiavlent to 1 (mod p)

How do i reach n^(p-1) on the left hand side?
 
  • #4
n^p divided by n IS NOT 1^p. PLEASE stop and review algebra with exponents before you try to continue.
 
  • #5
sorry, silly mistake.
dividing by n would give me,

n^(p-1) equivalent to 1 (mod p)

which is fermat's little theorem. so is this all i need to do?
 
  • #6
This is ok if p doesn't divide n, but the question asks me for all integers n.
So how do i show it's also true for when p divides n?
 
  • #7
kmeado07 said:
This is ok if p doesn't divide n, but the question asks me for all integers n.
So how do i show it's also true for when p divides n?

You actually want to go the other way. Start with Fermat's little theorem and then go to your conclusion. Multiply by n, you can always do that.
 

What is Fermat's little theorem?

Fermat's little theorem is a fundamental theorem in number theory discovered by Pierre de Fermat. It states that if p is a prime number, then for any integer a, a^p - a is divisible by p.

How does Fermat's little theorem work?

Fermat's little theorem is based on the properties of modular arithmetic. It states that if p is a prime number, then for any integer a, a^p is equivalent to a (mod p). This means that when we divide a^p by p, the remainder will always be a. In other words, a^p and a are congruent (mod p).

What are some applications of Fermat's little theorem?

Fermat's little theorem has many applications in number theory and cryptography. It is used to test whether a number is prime, to generate pseudorandom numbers, and to prove the correctness of certain algorithms. It is also a key component in the RSA encryption algorithm.

What is the difference between Fermat's little theorem and Fermat's last theorem?

Fermat's little theorem and Fermat's last theorem are two separate theorems discovered by Pierre de Fermat. While Fermat's little theorem is a relatively simple result that can be easily proven, Fermat's last theorem is a famously difficult problem that remained unsolved for over 300 years until it was finally proven by Andrew Wiles in 1994.

Are there any limitations to Fermat's little theorem?

Yes, Fermat's little theorem only holds true for prime numbers. If p is not a prime number, then a^p - a may not be divisible by p. Additionally, the theorem only applies to integers, not real numbers. It also does not provide a way to find the value of a^p - a, only that it is divisible by p.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
928
Replies
1
Views
705
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
983
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top