In June 1830, aged 18, Galois published a short paper, On the theory of numbers, in a Paris scientific bulletin. In it he invented new numbers, which he called imaginaries, for a world in which only finitely many numbers exist. For more than a century the paper looked like a curiosity. Today it is inside every mobile phone.

Counting with remainders

In clock arithmetic we count only with the remainders of division by a fixed number. With the number 5 there are only $0, 1, 2, 3, 4$, and the sums “wrap around”:

$$3+4=7\equiv2,\qquad3\cdot4=12\equiv2\pmod5.$$

Here is the multiplication table modulo 5:

$\times$ 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

Every row contains a 1. This means that every non-zero number has an inverse: $2\cdot3\equiv1$, $4\cdot4\equiv1$. We can divide! With only 5 numbers we have a complete arithmetic, with all four operations, like that of the rational numbers. A structure like this is called a field.

With the number 6 this fails. Since $2\cdot3=6\equiv0$, 2 cannot have an inverse: if $2x\equiv1$, multiplying by 3 we would get $0\equiv3$. The remainders of division by $n$ form a field exactly when $n$ is prime.

An i for the world of three numbers

Modulo 3 there are only $0, 1, 2$. The equation $x^2+1=0$, that is, $x^2\equiv2$, has no solution: $0^2=0$, $1^2=1$ and $2^2=4\equiv1$. It is the same situation as with the real numbers, where $x^2=-1$ has no solution.

Galois did what one does with the reals: he invented a root. He called it $i$, with $i^2\equiv-1\equiv2$, and considered all numbers of the form

$$a+bi,\qquad a,b\in\{0,1,2\}.$$

There are $3\times3=9$ numbers, and the calculations follow the usual rules, reducing modulo 3. For example,

$$(1+i)^2=1+2i+i^2=1+2i-1=2i.$$

Continuing, $(1+i)^4=(2i)^2=4i^2=-4\equiv2$, and $(1+i)^8=2^2=4\equiv1$. The eight powers $(1+i)^1,\dots,(1+i)^8$ are all different and run through all eight non-zero numbers. The result is a field with nine elements.

Galois’s theorem

Galois proved that the same holds in general. For each prime $p$ and each $n\geq1$ there is a field with exactly $p^n$ elements, built with an “imaginary” root of a polynomial that has no roots modulo $p$. And in every finite field there is an element, like $1+i$ in the example, whose powers give all the non-zero elements. Later it was proved that there are no others: every finite field has $p^n$ elements, and two fields with the same number of elements are, at bottom, the same. In his honour the field with $p^n$ elements is called a Galois field and written $\mathrm{GF}(p^n)$.

Inside the phone

Computers store everything in bytes of 8 bits, and there are $2^8=256$ different bytes. That is exactly the number of elements of $\mathrm{GF}(2^8)$. By treating each byte as an element of this field, bytes can be added, multiplied and divided, and this opens the way to two technologies:

  • Reed-Solomon codes, from 1960, add to the data a few check bytes computed with polynomials over a Galois field. If part of the data is lost, the equations make it possible to recover it. They are used on CDs and DVDs, which keep playing even when scratched, in QR codes, which can be read with up to 30% of the image damaged, and in communications with space probes.
  • AES, the encryption standard adopted by the US government in 2001 and used in secure internet connections, scrambles data with calculations in $\mathrm{GF}(2^8)$.
Exercise: modulo 7, what is the inverse of 3? And of 6?

We look for $x$ with $3x\equiv1\pmod7$. Testing, $3\cdot5=15=2\cdot7+1$: the inverse of 3 is 5. For 6, $6\cdot6=36=5\cdot7+1$: 6 is its own inverse. It makes sense, because $6\equiv-1$ and $(-1)\cdot(-1)=1$.

Exercise: in the field of nine elements, compute (1 + i)(2 + i).

$(1+i)(2+i)=2+i+2i+i^2=2+3i-1=1+3i$. Since $3\equiv0$, the result is $1$. So $2+i$ is the inverse of $1+i$: in this world of nine numbers, $\frac1{1+i}=2+i$.

Sources: Évariste Galois, “Sur la théorie des nombres”, Bulletin des sciences mathématiques de M. Férussac 13 (1830) · Rudolf Lidl and Harald Niederreiter, Finite Fields (Cambridge University Press, 1997) · Irving Reed and Gustave Solomon, “Polynomial codes over certain finite fields”, Journal of the SIAM 8 (1960).

All topics on Évariste Galois · ← When an equation can be solved by radicals · Doubling the cube and trisecting the angle: the impossible constructions →

Image credits.