# Why Does Fermat's Little Theorem Lead to Its Corollary?

• kingwinner
In summary: So if p doesn't divide a, then p and a are relatively prime, and vice versa. In summary, Fermat's little theorem states that if p is a prime and p does not divide a, then ap-1 is congruent to 1 mod p. The Corollary states that for all a in the integers and all primes p, ap is congruent to a mod p. The assumption that p does not divide a is removed in the Corollary because it is implied by the fact that p and a are relatively prime. Therefore, the two statements are equivalent. However, this only holds true if p is a prime, as composite numbers can have common divisors even if one does not divide the other.
kingwinner
1st question:
Fermat's little theorem: If p is prime and p does not divide a, a E Z, then ap-1 is congruent to 1 mod p.

Corollary: For all a E Z and all primes p, ap is congruent to a mod p.

I don't really understand the corollary part, why is the assumption "p does not divide a" removed?

I can see why Corollary => Fermat's little theorem,
but I can't see why Fermat's little theorem => Corollary

2nd question:
(i) p does not divide a
(ii) a and p are relatively prime
Are (i) and (ii) equivalent? (i.e. (i)=>(ii) and (ii)=>(i) )

Can someone help? Thanks!

If p does divide a, then a=0 mod p, so the congruence is trivial. And those two statements are equivalent (assuming p is a prime, as I'm assuming you are assuming).

StatusX said:
If p does divide a, then a=0 mod p, so the congruence is trivial. And those two statements are equivalent (assuming p is a prime, as I'm assuming you are assuming).
Why is ap is congruent to a mod p trivial if p does divide a? Sorry, I can't see your point...

Because both sides are zero.

OK, I got it! :)

Any idea about my 2nd question?

Like StatusX said, if p is a prime, then they are equivalent.

morphism said:
Like StatusX said, if p is a prime, then they are equivalent.
I thought StatusX said that Fermat's little theorem and the Corollary are equivalent, my bad...

2nd question: So, why does p have to be a prime for them to be equivalent and why are they equivalent?

Thanks!

Sorry, that was a little unclear.

The condition that two numbers are relatively prime means that they have no common divisors (I'll ignore 1 as a divisor). The only divisor of a prime p is p itself, so p can only have a common divisor with n if p is a divisor of n, ie, p divides n. On the other hand, composite numbers n and m can have common divisors even if one doesn't divide the other, eg, 6 and 8 have 2 as a common divisor.

## What is Fermat's little theorem?

Fermat's little theorem is a fundamental theorem in number theory, named after French mathematician Pierre de Fermat. It states that if p is a prime number and a is any positive integer less than p, then a raised to the power of p minus one is congruent to one modulo p.

## What is the significance of Fermat's little theorem?

Fermat's little theorem is significant because it provides a simple and elegant proof for many other theorems in number theory, such as the Euler's theorem and the Chinese remainder theorem. It also has important applications in cryptography and number theory algorithms.

## How is Fermat's little theorem related to modular arithmetic?

Fermat's little theorem is closely related to modular arithmetic, as it states that for any prime number p, the remainder when a number is divided by p is the same as the remainder when the number is raised to the power of p minus one and divided by p. This property is useful in solving problems involving modular arithmetic.

## Can Fermat's little theorem be extended to non-prime moduli?

Yes, Fermat's little theorem can be extended to non-prime moduli using Euler's theorem, which is a generalization of Fermat's little theorem. Euler's theorem states that for any positive integer n, if a and n are relatively prime, then a raised to the power of phi(n) is congruent to one modulo n, where phi(n) is the Euler's totient function.

## What is the proof for Fermat's little theorem?

The proof for Fermat's little theorem is based on the concept of modular arithmetic and group theory. It involves showing that the set of numbers {1, 2, ..., p-1} forms a group under multiplication modulo p, and then proving that each element in this group has an inverse. This shows that every element raised to the power of p-1 is congruent to one modulo p.

• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
16
Views
1K
• Calculus and Beyond Homework Help
Replies
17
Views
3K
• Calculus and Beyond Homework Help
Replies
10
Views
2K
• Calculus and Beyond Homework Help
Replies
16
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
473
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
2K