Tell HN: Fermat's Little Theorem fails on complex numbers | Hacker News Reader

Tell HN: Fermat's Little Theorem fails on complex numbers

2 pointsAnimalMuppet3 comments

Fermat's Little Theorem says that, if p is prime, then a^p = a mod p. You can take complex numbers mod p as well, but for them, the little theorem fails.

More specifically, for p > 2, if c = (a, b), then c^p = c mod p iff p is of the form p=4n+1. If p=4n+3, then c^p = c conjugate mod p. In this context, the conjugate of c is (a, p-b).

Why? Because i^4n+1 = i, but i^4n+3 = -i. The rest follows from the binomial proof of the little theorem (see https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem).

View on HN

You have discovered a fascinating nugget from the subject of algebraic number theory.

It is a theorem that if every prime p of the form 4n+1 can be written as a sum of two squares: 5 = 1 + 4, 13 = 4 + 9, etc. Conversely, no prime of the form 4n+3 can be (reduce it mod 4).

Let Z[i] be the set in which you're doing arithmetic, of complex numbers of the form a + bi, where a,b are both integers. These are called the Gaussian integers [1].

If p = a^2 + b^2, then p = (a + bi)(a - bi) in the Gaussian integers. So that means that whenever p=4n+1, p is no longer prime in Z[i]. So you shouldn't expect the machinery of Fermat's little theorem to work. Conversely, any prime p=4n+3 is still prime in this bigger set, and so the machinery underlying Fermat's little theorem still works.

The rabbit hole goes very deep :)

[1] https://en.wikipedia.org/wiki/Gaussian_integer

...no one ever said it worked on complex numbers.

Per the wiki link, it only works with integers.

Ah, but this is the heart and soul of mathematics. Taking a theorem that is known for one setting, and seeing if it works in some other setting as well. Can you prove it, or alternatively find a counterexample?

There is a version of it that always works in "complex numbers" (or more precisely in "integer rings" inside the complex numbers), but unfortunately it requires a long technical digression to state precisely. (And, once you've developed all the language, it's trivial to prove.)

This Wikipedia page discusses it: https://en.wikipedia.org/wiki/Algebraic_number_theory

Reply on news.ycombinator.com