Four formats for Fermat: correction!

In my previous post I explained three variants on Fermat’s Little Theorem, as well as a fourth, slightly more general variant, which it turns out is often called Euler’s Totient Theorem. Here’s what I said:

If n \geq 1 and a is any integer, then a^{\varphi(n)} \equiv 1 \pmod n.

However, this is wrong! We can easily find a counterexample. For example, let n = 6 and a = 3. Then \varphi(6) = 2, since there are only two numbers less than 6 that are relatively prime to it (namely, 1 and 5; each of 2, 3, and 4 shares a common factor with 6). But then a^{\varphi(n)} = 3^2 = 9 which has a remainder of 3, not 1, when divided by 6.

What’s wrong? It turns out I missed a small but important restriction: this is only true when a is relatively prime to n. Note this is stronger than saying a isn’t divisible by n; it says they cannot share any common factors at all. For example, 9 is not divisible by 6, but they share 3 as a common factor, so this theorem does not apply (and indeed, 9^2 \equiv 3 \pmod 6, not 1).

For completeness, here’s a corrected statement of the theorem (I have also fixed the previous post):

If n \geq 1 and a is any integer relatively prime to n, then a^{\varphi(n)} \equiv 1 \pmod n.

So what’s an example where this theorem does work? Let’s keep n = 6 but try a = 5 instead: now a^{\varphi(6)} = 5^2 = 25 \equiv 1 \pmod 6.

In my next post I’ll present a proof of Fermat’s Little Theorem.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in number theory, primes and tagged , , , , , , . Bookmark the permalink.

2 Responses to Four formats for Fermat: correction!

  1. Pingback: Four formats for Fermat | The Math Less Traveled

  2. Pingback: Fermat’s Little Theorem: proof by modular arithmetic | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

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