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 be a prime, and let be an integer not divisible by . Then .

If you aren’t comfortable with the notation of modular arithmetic, you might like to phrase the conclusion of the theorem as saying that divides . (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 be a prime, and any integer. Then .

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 , then, multiplying by , we have . That deals with the case that is not divisible by . If *is* divisible by , then and so certainly .

In the other direction, suppose that is not divisible by and that . Then the fact that is not divisible by means that has a multiplicative inverse . So we can cancel one from each side, to get .

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 is not divisible by , whereas the second is true for all . But that should be reasonably easy to remember, just by thinking about it. (If , then it’s going to be difficult to make congruent to …)

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 is prime, in the form that it means we can divide by numbers coprime to (numbers not divisible by ).

Let’s think about the numbers , , , …, . If we multiply them together, we get . (Here, means factorial.)

But we know more about these numbers. They are all different, . Indeed, if , then , because we can “cancel the ” (because it’s coprime to ). So we have numbers, all different, and none of them is . So they must be congruent to , , , …, in some order. So their product is congruent to .

We now have two expressions for this product, so we can equate them. We have . Now is coprime to , so we can again cancel, to give — 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 to prove that . This is easy for , the base case, and it’s also pretty easy for . The interesting bit is to justify the induction step, so let’s think about that.

We’re allowed to suppose that , and we want to deduce that . We can expand , using the binomial theorem. We get , together with a bunch of terms of the form , with . It turns out that if then the binomial coefficient is divisible by . 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 . But our induction hypothesis tells us that , so we have , 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 isn’t prime? It turns out that the result as stated isn’t true if 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 be an integer greater than 1, and let be an integer coprime to . Let denote the number of positive integers less than that are coprime to (see below for more about ). Then .

The function 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: , because there are 4 positive integers less than 12 that are coprime to 12 (namely 1, 5, 7, and 11).

Notice that if is prime, then this theorem is exactly Fermat’s Little Theorem, because if is prime then (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.

June 3, 2010 at 11:37 am

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

July 12, 2010 at 7:55 am

[…] 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 […]

September 18, 2010 at 12:41 am

[…] 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 […]

September 21, 2010 at 10:11 pm

[…] 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 […]

November 12, 2010 at 5:07 pm

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

August 15, 2011 at 12:34 pm

[…] 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 […]

October 19, 2011 at 12:08 pm

[…] 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 […]

October 21, 2011 at 12:08 pm

[…] 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 […]

October 23, 2011 at 4:32 pm

[…] 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 […]

January 6, 2012 at 5:59 pm

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??

January 6, 2012 at 6:12 pm

I just mean that if is not prime, then we cannot be sure that for all coprime to .

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 is coprime to 4 then ?

Does that help?

January 10, 2012 at 4:25 pm

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?

January 10, 2012 at 4:31 pm

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.

January 10, 2012 at 4:42 pm

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?

January 10, 2012 at 4:52 pm

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!

January 10, 2012 at 4:57 pm

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?

January 10, 2012 at 5:17 pm

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?

January 10, 2012 at 5:31 pm

thanks again. you teach at cambridge university?

January 10, 2012 at 5:37 pm

yup i meant something like this

January 10, 2012 at 5:45 pm

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?

January 10, 2012 at 6:22 pm

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

January 10, 2012 at 6:57 pm

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)

January 16, 2012 at 6:27 pm

is this a theorem or just a conjucture?

January 16, 2012 at 7:26 pm

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!

January 19, 2012 at 3:31 pm

oh thanks. sorry for the inconvinience

February 4, 2012 at 9:32 pm

[…] 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 […]

July 31, 2012 at 10:41 am

[…] 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 […]

August 16, 2012 at 11:48 am

[…] 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. […]

October 25, 2012 at 2:40 pm

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

May 7, 2013 at 9:02 pm

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

September 2, 2013 at 3:59 pm

Reblogged this on Singapore Maths Tuition.

October 14, 2013 at 10:15 am

[…] 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. […]

March 13, 2015 at 11:57 am

[…] 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 […]

March 10, 2016 at 2:26 pm

[…] 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 […]

March 9, 2017 at 3:13 pm

[…] 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 […]