Theorem 14: Fermat’s Little Theorem

Firstly, apologies for the long gap.  Very far from being Theorem of the Week, I know.  Here’s another theorem for now, and I’ll do what I can to revert to a weekly post.

So, to this week’s theorem.  I have previously promised to write about Fermat‘s Little Theorem, and I think it’s time to keep that promise.  In that post (Theorem 10, about Lagrange’s theorem in group theory), I introduced the theorem, so I’m going to state it straightaway.  If you haven’t seen the statement before, I suggest you look back at that post to see an example.

Theorem (Fermat’s Little Theorem) Let p be a prime, and let a be an integer not divisible by p.  Then a^{p-1} \equiv 1\mod{p}.

If you aren’t comfortable with the notation of modular arithmetic, you might like to phrase the conclusion of the theorem as saying that p divides a^{p-1} - 1.  (I do encourage you to learn about modular arithmetic, though, because it’s incredibly helpful.)

The theorem can be presented in a slightly different (but equivalent) way.  I’ll record that here, for convenience.

Theorem (Fermat’s Little Theorem, alternative statement) Let p be a prime, and a any integer.  Then a^p \equiv a\mod{p}.

One important point to note.  The name of this theorem is sometimes abbreviated to FLT, but it should not be confused with a rather more famous theorem with the same abbreviation!

Why are these equivalent?

In one direction, if a^{p-1} \equiv 1\mod{p}, then, multiplying by a, we have a^p \equiv a \mod{p}.  That deals with the case that a is not divisible by p.  If a is divisible by p, then a \equiv 0\mod{p} and so certainly a^p \equiv a\mod{p}.

In the other direction, suppose that a is not divisible by p and that a^p \equiv a\mod{p}.  Then the fact that a is not divisible by p means that a has a multiplicative inverse \mod{p}.  So we can cancel one a from each side, to get a^{p-1} \equiv 1\mod{p}.

The fact that these two statements are equivalent is supposed to be pretty easy.  The important thing to remember that the first is true only if a is not divisible by p, whereas the second is true for all a.  But that should be reasonably easy to remember, just by thinking about it.  (If a\equiv 0\mod{p}, then it’s going to be difficult to make a^{p-1} congruent to 1\mod{p}…)

I’d like to give outlines of three proofs of this theorem, since I think they are all interesting and have nice features.

Proof 1

The idea here is to exploit the fact that p is prime, in the form that it means we can divide by numbers coprime to p (numbers not divisible by p).

Let’s think about the p-1 numbers a, 2a, 3a, …, (p-1)a.  If we multiply them together, we get (p-1)! a^{p-1}.  (Here, (p-1)! means p-1 factorial.)

But we know more about these numbers.  They are all different, \mod{p}.  Indeed, if ua \equiv va \mod{p}, then u\equiv v\mod{p}, because we can “cancel the a” (because it’s coprime to p).  So we have p-1 numbers, all different, and none of them is 0\mod{p}.  So they must be congruent to 1, 2, 3, …, p-1 in some order.  So their product is congruent to (p-1)! \mod{p}.

We now have two expressions for this product, so we can equate them.  We have (p-1)! a^{p-1} \equiv (p-1)! \mod{p}.  Now (p-1)! is coprime to p, so we can again cancel, to give a^{p-1} \equiv 1 \mod{p} — and that’s exactly what we wanted!

Proof 2

I’m not going to write out this proof in detail, but I’ll describe the ideas.  The main idea is to use induction on a to prove that a^p \equiv a \mod{p}.  This is easy for a\equiv 0\mod{p}, the base case, and it’s also pretty easy for a\equiv 1\mod{p}.  The interesting bit is to justify the induction step, so let’s think about that.

We’re allowed to suppose that a^p \equiv a\mod{p}, and we want to deduce that (a+1)^p \equiv a+1 \mod{p}.  We can expand (a+1)^p, using the binomial theorem.  We get a^p + 1, together with a bunch of terms of the form \binom{p}{j} a^j, with 1\leq j\leq p-1.  It turns out that if 1\leq j\leq p-1 then the binomial coefficient \binom{p}{j} is divisible by p.  I think I’m going to leave this as an exercise; it’s a nice problem, and not too hard.  Using this fact, we now have (a+1)^p \equiv a^p + 1\mod{p}.  But our induction hypothesis tells us that a^p \equiv a \mod{p}, so we have (a+1)^p \equiv a^p + 1 \equiv a+1 \mod{p}, and that completes the proof of the induction step.

Proof 3

The third proof I’d like to mention uses Lagrange’s theorem (a result about groups).  I described that proof in my previous post about that theorem (link in the last sentence), so I think I’ll point readers there and not say any more here.

Generalisation and applications

One very natural question to ask now is: what happens if p isn’t prime?  It turns out that the result as stated isn’t true if p is prime (think of an example!).  But one can come up with an analogous result.  I think that Proofs 1 and 3 above generalise most naturally, and if you think about it for a bit you can use these arguments to see what the result should be.  The result is often called the Fermat-Euler theorem.  I’ll state it here, and leave the proof as an exercise (try to generalise proofs 1 and 3 above).

Theorem (Fermat-Euler) Let n be an integer greater than 1, and let a be an integer coprime to n.  Let \phi(n) denote the number of positive  integers less than n that are coprime to n (see below for more about \phi(n)).  Then a^{\phi(n)} \equiv 1\mod{n}.

The function \phi(n) is called the Euler totient function, or the Euler phi function, and it is extremely useful in number theory.  It has many interesting properties.  Quick example: \phi(12) = 4, because there are 4 positive integers less than 12 that are coprime to 12 (namely 1, 5, 7,  and 11).

Notice that if n is prime, then this theorem is exactly Fermat’s Little Theorem, because if n is prime then \phi(n) = n-1 (I’ll let you check that!).

Applications.  Fermat’s Little Theorem and the Fermat-Euler Theorem are very useful, both in number theory and in applications to the outside world (such as cryptography).  But I think this post is long enough now, so I shan’t say more about that: I’ll let you enjoy the results on their own merits!

Further reading

Any introduction to number theory should talk about these results.  As usual, I’d like to plug Davenport’s The Higher Arithmetic.  No doubt there are also loads of online resources that are good too.

Advertisements

35 Responses to “Theorem 14: Fermat’s Little Theorem”

  1. Theorem 28: there are infinitely many Carmichael numbers « Theorem of the week Says:

    […] By theoremoftheweek This week’s theorem follows from my previous posts on Fermat’s little theorem and (to a lesser extent) Wilson’s […]

  2. Theorem 31: the non-zero integers (mod p) form a group under multiplication « Theorem of the week Says:

    […] about Lagrange’s theorem in group theory, and mentioned it again in Proof 3 in my post about Fermat’s little theorem.  It’s a handy sort of thing to know (and the existence of inverses is really crucial to all […]

  3. Lagrange theorem and “the” proof of Fermat little theorem. « Pure Math Notes Says:

    […] the first proof in 1736. Although there are several proofs, many of which are more elementary (c.f Theorem of the week: Fermat’s Little Theorem for a couple of other proofs), The proof presented here is quite standard and rely on very basic […]

  4. Lagrange theorem and “the” proof of Fermat little theorem. « Pure Notes Says:

    […] criterion (also understood through (Z/nZ)*). For other proofs of Fermat little theorem, see Theorem of the week: Fermat’s Little Theorem for a couple of other proofs, some of which are more […]

  5. Homomorphisms, Generators, and Cyclic Groups « Gracious Living and the Two Meat Meal Says:

    […] prove the second bit, we need something called Fermat’s Little Theorem, of which proofs are here and […]

  6. Theorem 27: Wilson’s theorem « Theorem of the week Says:

    […] the first proof I gave of Fermat’s little theorem, I suggested multiplying together the p-1 numbers a, 2a, …, (p-1)a (where a is coprime […]

  7. Number Theory: Lecture 6 « Theorem of the week Says:

    […] odd prime, and let be an integer.  Then .  This is interesting only when is coprime to .  From Fermat’s Little Theorem (in Lecture 2), we know that , and we can then deduce that .  We can take a primitive root modulo […]

  8. Number Theory: Lecture 7 « Theorem of the week Says:

    […] We then multiplied together the two lists; this is rather reminiscent of one of the proofs of Fermat’s Little Theorem.  Euler’s criterion (which we saw in Lecture 6) finishes the […]

  9. Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:

    […] observation is that we always seem to get back to 1 at some point.  But we know from Fermat’s Little Theorem that this should be the case: we know that , so in this case we were bound to get back to 1 after 6 […]

  10. Muhammad Usman Qureshi Says:

    One very natural question to ask now is: what happens if p isn’t prime? It turns out that the result as stated isn’t true if p is prime (think of an example!).

    i could not understand what u meant here that the result as stated isn’t true if p is prime!!
    i really am trying hard to find if there is any theorem or esult on what happens or can we find any way that p isn’t prime??

  11. theoremoftheweek Says:

    I just mean that if p is not prime, then we cannot be sure that a^{p-1} \equiv 1 \pmod{p} for all a coprime to p.

    The best way for you to see this might be to try some numerical examples. For example, what happens mod 4? Is it the case that if a is coprime to 4 then a^3 \equiv 1 \pmod{4}?

    Does that help?

  12. Muhammad Usman Qureshi Says:

    thanx i understood.
    now can u answer my second question plz that is there any condition or theorem with a formal proof of how to test or confirm whether a given number is composite?

  13. theoremoftheweek Says:

    There are various `primality tests’ to determine whether a given number is prime or composite. I haven’t written much about this yet, but there are some key topics mentioned here and here. Those posts might give you some words and phrases to look for, as well as some useful links and references to books.

  14. usman Says:

    A fraction in lowest terms with a prime denominator other than 2 or 5 (i.e. coprime to 10) always produces a repeating decimal. The period of the repeating decimal of 1/p is equal to the order of 10 modulo p. If 10 is a primitive root modulo p, the period is equal to p − 1; if not, the period is a factor of p − 1. This result can be deduced from Fermat’s little theorem, which states that 10p−1 = 1 (mod p).

    have u ever heard about this before in a theorem or something?

  15. theoremoftheweek Says:

    I’ve come across results like this, but I don’t know a name for them — I couldn’t attribute them to a particular mathematician.

    It’s a nice exercise, though. Thanks for mentioning it!

  16. usman Says:

    u talked about primality tests , like there are fermat’s little, euler’s and other theorems to check for primality. i was asking about any theorem regarding the compositeness of a number that u have ever come across?

  17. theoremoftheweek Says:

    I’m not sure that I know what you mean by a theorem regarding the compositeness of a number. There are results of the form `n has this property if and only if n is prime’ (e.g. Wilson’s theorem, to give a quick example). Is that what you mean?

  18. Muhammad Usman Qureshi Says:

    thanks again. you teach at cambridge university?

  19. Muhammad Usman Qureshi Says:

    yup i meant something like this

  20. Muhammad Usman Qureshi Says:

    and one last question if you dont mind. i have read little bit about psuedoprimes and their different kinds, when some composite numbers were found fulfilling the fermat’s little theorem we called them psuedoprime or fermat psuedoprime to be exact. now is their any xplanation or theorem of any sorts as to y they satisfy this theorem? or some generalization for psuedoprimes?

  21. theoremoftheweek Says:

    You might like to go and read about Carmichael numbers. Perhaps that will answer your question?

  22. Muhammad Usman Qureshi Says:

    i read that before it doesnt help in what im searching, but thanx for pointing out.
    now have you ever heard this?

    The period T of the repeating decimal of (1/pq) is LCM(Tp, Tq) where Tp is the period of the repeating decimal of (1/p) and Tq is the period of the repeating decimal of .(1/q)

  23. Muhammad Usman Qureshi Says:

    is this a theorem or just a conjucture?

  24. theoremoftheweek Says:

    Well, do you have a proof?!

    May I suggest that you post questions like this on Ask NRICH? It’s completely free to register there, and there’s a team of people on hand to help answer questions — you’ll get a response there more quickly than I can guarantee on my own!

  25. usman Says:

    oh thanks. sorry for the inconvinience

  26. Theorem 39: Euler’s criterion « Theorem of the week Says:

    […] previously written about Fermat’s Little Theorem, which tells us that if is a prime and is not divisible by , then .  That’s not terribly […]

  27. Theorem 41: Gauss’s lemma « Theorem of the week Says:

    […] going to write this post on the assumption that you know about Fermat’s little theorem and Euler’s criterion.  Fortunately, those links take you to places on this blog where you […]

  28. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] Other mathematicians who were mentioned during the week: Cantor, Cardano, Diophantus, Fermat, Galois, Tartaglia, Wiles.  At some point we mentioned that there are infinitely many primes.  We saw a special case of Fermat’s Little Theorem. […]

  29. Theorem 42: Fermat’s Last Theorem « Theorem of the week Says:

    […] previously written about Fermat’s Little Theorem, but today it’s time for his (perhaps more famous) Last Theorem.  Today’s blog post […]

  30. overflow possibilities in modular exponentiation by squaring | BlogoSfera Says:

    […] am looking to implement the fermat’s little theorem for prime testing. Here’s the code I have […]

  31. mathtuition88 Says:

    Reblogged this on Singapore Maths Tuition.

  32. Number Theory: Lecture 2 | Theorem of the week Says:

    […] Theorem 8 (Fermat-Euler): Let be a natural number, and let be an integer coprime to .  Then .  We proved this using Lagrange‘s theorem from group theory. […]

  33. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] be confused with another Lagrange’s Theorem that I’ve also written about), and about Fermat’s Little Theorem (that post outlines the three proofs I mentioned in today’s lecture).  Remember to watch […]

  34. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] be confused with another Lagrange’s Theorem that I’ve also written about), and about Fermat’s Little Theorem (that post outlines the three proofs I mentioned in today’s lecture).  Remember to watch out […]

  35. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

    […] be confused with another Lagrange’s Theorem that I’ve also written about), and about Fermat’s Little Theorem (that post outlines the three proofs I mentioned in today’s lecture).  You’ll find a […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: