Tuesday, August 30, 2005

Fermat's Little Theorem

Despite its name, Fermat's Little Theorem is one of Pierre de Fermat's most important theorems. Fermat first presented it without proof in one of his letters in 1640. Leonhard Euler provided the first published proof in 1736. The theorem is very useful as a way of testing very large primes.

In a nutshell, the proof states that given an integer a and a prime p that does not divide a, then we know that a(p-1) has a remainder of 1 when divided by p.

From this theorem, then we know that:
472 ≡ 1 (mod 3).
1106 ≡ 1 (mod 7).
etc.

From the basic ideas of modulus (see here for review), we also know that:
(472)n ≡ 1 (mod 3)
(1106)n ≡ 1 (mod 7)

This theorem is also the foundation of Sophie's Proof (see here for the details), an important result from the mathematician Sophie Germain.

Theorem: If an integer a is not divisible by a prime p, then ap-1 ≡ 1 (mod p).

(1) From the Division Algorithm, we know that any number divided by an integer p has a remainder between 0 and p-1.

(2) This means that for any value a there is exactly p-1 possible congruences.
a ≡ 0 (mod p) or
a ≡ 1 (mod p) or
...
a ≡ p-1 (mod p)

(3) Consider the values 0a, 1a, 2a,... (p-1)a.

(4) It turns out that each of these values (0a, 2a, ...) is equal to a unique congruence when divided by p since:

(a) Assume that 2 of the values are equal to the same congruence: let's say ia, ja
(b) So ia ≡ ja (mod p)
(c) This tells us that p divides ia - ja (from the definition of )
(d) Which means that p divides a(i-j).
(e) From Euclid's Lemma, we know that p must divide i-j (since a is not divisible by p)
(f) But then i = j since both values are between 0 and p.

(5) So, this tells us that:
(1a)(2a)...(p-1)a ≡ (1)(2)...(p-1) (mod p). [Applying the principles of modular arithmetic]

(6) We also know that (1a)(2a)*...*(p-1)a = a(p-1)(p-1)! [See here for a review of factorials such as (p-1)!]

(7) Putting (5) and (6) together gives us:
a(p-1)(p-1)! ≡ (p-1)! (mod p).

(8) Since (p-1)! is not equal to 0, we can divide this from both sides of the modulus (see Lemma 4, here) and get:
a(p-1) ≡ 1 (mod p).

QED

7 comments:

  1. Hello!
    I'm a student from Barcelona, Spain, Europe. And I'm making a work about test primality.
    I'm trying to understand this proof but I get lost in the 4th point letter a.
    I would be really pleased if you answer my question.
    I can't understand why ia is equal to ja. How can I proof I'll always find some ia=ja (mod p)?

    Sorry if this a stupid question. And excuse my low level in english.
    Thanks for all.
    Nice Blog! :)

    ReplyDelete
  2. Hi Ulises,

    Thanks for your question. :-)

    In the proof, I am trying to show that for any value i, j, if ia = ja (mod p), then i=j.

    Keep in mind, I am not proving that ia = ja (mod p); I am showing that if they are equal (mod p), then the conclusion follows.

    This is a conditional proof. If it so happens that ia = ja (mod p), then this implies that i = j.

    -Larry

    ReplyDelete
  3. Hello Larry,
    Thanks for your answer.
    I can see that if ja=ia (mod p) then j=i (mod p) but when you proof the little theorem you say: "(a) Assume that 2 of the values are equal to the same congruence: let's say ia, ja"
    My question is: Why is this supposition always true?
    Thanks.

    ReplyDelete
  4. Hi Ulises,

    We can make the supposition because we can always assume that j=i. In this case, ia = ja (mod p) since ia - ja = ia - ia = 0 which is divisible by p.

    -Larry

    ReplyDelete
  5. Thank you for your clear proof

    ReplyDelete
  6. From Fermat’s little theorem to Fermat’s Last Theorem

    http://primemath.wordpress.com/2012/11/16/from-fermat-little-theorem-to-fermat-last-theorem/
    PDF
    http://primemath.files.wordpress.com/2013/01/fltflt.pdf

    Please read . It's short.

    ReplyDelete
  7. From Fermat’s little theorem to Fermat’s Last Theorem

    http://primemath.wordpress.com/2012/11/16/from-fermat-little-theorem-to-fermat-last-theorem/
    PDF
    http://primemath.files.wordpress.com/2013/01/fltflt.pdf

    Please read . It's short.

    ReplyDelete