Three Theorems in Number Theory

August 5, 2026 · #number theory

In this post, I would like to discuss three elementary theorems in number theory that I first learned in my middle school. It has been really ages since then, and I only vaguely remember their proofs.

During a rather boring midnight coach ride from the airport, I found myself with nothing to do but share some random mathematical thoughts with my wife. As the journey went on, the proofs gradually became clearer in my mind—and, meanwhile, she happily fell asleep.

Let’s start with Fermat’s little theorem.

Theorem 1 (Fermat). Let $𝑝$ be a prime number. For any $𝑎$ coprime to $𝑝$ , we have $𝑎^{𝑝 - 1} = 1 (mod 𝑝)$ .

Proof. Let $𝑆 = {1, 2, \dots, 𝑝 - 1}$ . We notice that the set $𝑎 𝑆 ≔ {𝑎, 2 𝑎, \dots, 𝑎 (𝑝 - 1)}$ coincides with $𝑆$ , since $𝑎$ and $𝑝$ are coprime. We immediately get

(𝑝 - 1)! = \prod_{𝑛 \in 𝑆} 𝑛 = \prod_{𝑛 \in 𝑎 𝑆} 𝑛 = 𝑎^{𝑝 - 1} (𝑝 - 1)! (mod 𝑝) .

After canceling out $(𝑝 - 1)!$ on both sides of the equation, we derive $𝑎^{𝑝 - 1} = 1 (mod 𝑝)$ .⁠∎

The next theorem also involves a double counting technique.

Theorem 2 (Wilson). Let $𝑝$ be a prime number. We have $(𝑝 - 1)! = - 1 (mod 𝑝)$ .

Proof. The elements in $𝑆 = {1, 2, \dots, 𝑝 - 1}$ can be grouped into pairs $(𝑎, 𝑎^{- 1})$ , where $𝑎^{- 1}$ is the unique element such that $𝑎 \cdot 𝑎^{- 1} = 1 (mod 𝑝)$ . There are only two special cases where $𝑎 = 𝑎^{- 1}$ , namely $𝑎 = 1$ or $𝑎 = 𝑝 - 1$ . So, when we compute $\prod_{𝑛 \in 𝑆} 𝑛$ , almost all the terms in the same pair cancel out and only leave 1 and $𝑝 - 1$ . Therefore, we derive

(𝑝 - 1)! = 1 \cdot (𝑝 - 1) = - 1 (mod 𝑝) .

⁠∎

The last theorem is also named after Fermat. But, as usual, he did not write down the proof. The first proof was given by Euler using infinite descent. Here, I present a more constructive proof.

Theorem 3 (Sum of two squares). A prime number $𝑝$ can be represented as a sum of two squares if and only if $𝑝 = 1 (mod 4)$ .

Proof. The necessity is obvious. Now, we assume that $𝑝 = 1 (mod 4)$ . By Wilson’s theorem, we have $(𝑝 - 1)! = - 1 (mod 𝑝)$ . In particular, it yields

- 1 = (𝑝 - 1)! = \prod_{𝑛 = 1}^{\frac{𝑝 - 1}{2}} 𝑛 \cdot (𝑝 - 𝑛) = {(- 1)}^{\frac{𝑝 - 1}{2}} \prod_{𝑛 = 1}^{\frac{𝑝 - 1}{2}} 𝑛^{2} = {(\prod_{𝑛 = 1}^{\frac{𝑝 - 1}{2}} 𝑛)}^{2} (mod 𝑝) .

Therefore, there exists $𝑎$ such that $𝑎^{2} = - 1 (mod 𝑝)$ .

Let $𝑛 = ⌊ \sqrt{𝑝} ⌋$ and we consider the set $𝐴 = {0, 𝑎, \dots, 𝑛 𝑎}$ . Since $| 𝐴 | = 𝑛 + 1$ , by pigeonhole principle, there must be two elements $(𝑥 𝑎, 𝑦 𝑎)$ in $𝐴$ such that $𝑥 𝑎 - 𝑦 𝑎 = 𝑧 (mod 𝑝)$ for some $0 < 𝑧 \leq 𝑛$ . We notice that

0 < {(𝑥 - 𝑦)}^{2} + 𝑧^{2} \leq 𝑛^{2} + 𝑛^{2} < 2 𝑝 .

Moreover, by our choice of $𝑎$ ,

{(𝑥 - 𝑦)}^{2} + 𝑧^{2} = {(𝑥 - 𝑦)}^{2} + {(𝑥 𝑎 - 𝑦 𝑎)}^{2} = {(𝑥 - 𝑦)}^{2} (𝑎^{2} + 1) = 0 (mod 𝑝) .

We deduce that ${(𝑥 - 𝑦)}^{2} + 𝑧^{2} = 𝑝$ .

⁠∎