When Sophie Germain wrote to Gauss in 1804, the two spoke a language that had just been born. Three years earlier, in the Disquisitiones Arithmeticae, Gauss had introduced a new sign, $\equiv$, and a new way of thinking about whole numbers: not by what they are, but by the remainder they leave on division. Everything Sophie later did on Fermat was written in that language. It is worth learning.

Clock arithmetic

If it is 9 o’clock now, what time will it be in 5 hours? Nobody answers 14 on a clock with hands: they answer 2. The clock keeps only the remainder on division by 12. Gauss wrote this as

$$14\equiv2\pmod{12},$$

which reads “14 is congruent to 2 modulo 12”. In general, $a\equiv b\pmod m$ means that $a$ and $b$ leave the same remainder on division by $m$, that is, that $a-b$ is a multiple of $m$.

The great advantage is that congruences can be added and multiplied like equalities. If $a\equiv b$ and $c\equiv d\pmod m$, then

$$a+c\equiv b+d\qquad\text{and}\qquad a\cdot c\equiv b\cdot d\pmod m.$$

This lets us replace huge numbers by small remainders in the middle of a calculation. For example, what is the last digit of $7^{100}$? The last digit is the remainder modulo 10. The powers of 7 end in $7, 9, 3, 1$ and then repeat, because $7^4=2401\equiv1\pmod{10}$. So

$$7^{100}=\left(7^4\right)^{25}\equiv1^{25}=1\pmod{10}.$$

The number $7^{100}$ has 85 digits, and we know the last one without computing any of the others.

Powers and remainders

Gauss’s favourite subject, and later Sophie’s, was powers modulo a prime number. Take the prime $p=7$ and cube each number, keeping only the remainder modulo 7:

$x$ 0 1 2 3 4 5 6
$x^3 \bmod 7$ 0 1 1 6 1 6 6

Only three remainders appear: $0$, $1$ and $6$, that is, $0$ and $\pm1$, because $6\equiv-1\pmod7$. Seen on a 7-hour clock, cubes are very poor. That poverty is exactly what Sophie Germain used in her theorem on Fermat.

Why does this happen? By Fermat’s little theorem, if $x$ is not a multiple of 7, then $x^6\equiv1\pmod 7$. But $x^6=(x^3)^2$. So $x^3$ is a number whose square is 1, and modulo a prime the only such numbers are $1$ and $-1$. The same argument works whenever $2p+1$ is prime: $p$-th powers modulo $2p+1$ can only be $0$, $1$ or $-1$.

What was in the letters

In the first letters, Monsieur Le Blanc sent Gauss new proofs of results from the Disquisitiones and some generalisations. Gauss replied, delighted to have found a reader able to go beyond him. When he discovered who the reader was, his admiration only grew. In the 1807 letter Gauss tells her, as a gift, some new and still unpublished results on remainders of powers.

Exercise: what is the remainder of 2¹⁰ on division by 11?

$2^5=32=2\cdot11+10$, so $2^5\equiv10\equiv-1\pmod{11}$. Hence $2^{10}=\left(2^5\right)^2\equiv(-1)^2=1\pmod{11}$. This agrees with Fermat’s little theorem: $2^{11-1}\equiv1\pmod{11}$.

Exercise: which remainders do fifth powers leave on division by 11?

Since $11=2\cdot5+1$ is prime, the argument in the text says that only $0$, $1$ and $-1\equiv10$ can appear. Checking a few: $2^5=32\equiv10$, $3^5=243=22\cdot11+1\equiv1$, $4^5=1024=93\cdot11+1\equiv1$. The eleven numbers from $0$ to $10$ give, in all, only the remainders $0$, $1$ and $10$.

Sources: Carl Friedrich Gauss, Disquisitiones arithmeticae (1801), articles 1 and 2 · biography of Sophie Germain, MacTutor · Andrea Del Centina and Alessandra Fiocca, “The correspondence between Sophie Germain and Carl Friedrich Gauss”, Archive for History of Exact Sciences (2012).

All Sophie Germain topics · ← The life of Sophie Germain · Sophie Germain’s theorem and Fermat’s Last Theorem →

Image credits.