Fermat's little theorem

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0
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!
 

Answers and Replies

  • #2
StatusX
Homework Helper
2,571
1
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).
 
  • #3
1,270
0
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...
 
  • #4
morphism
Science Advisor
Homework Helper
2,015
4
Because both sides are zero.
 
  • #5
1,270
0
OK, I got it! :)

Any idea about my 2nd question?
 
  • #6
morphism
Science Advisor
Homework Helper
2,015
4
Like StatusX said, if p is a prime, then they are equivalent.
 
  • #7
1,270
0
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!
 
  • #8
StatusX
Homework Helper
2,571
1
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.
 

Related Threads on Fermat's little theorem

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
1K
Replies
6
Views
981
Replies
3
Views
2K
Replies
4
Views
3K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
0
Views
1K
Replies
4
Views
3K
Top