Modular arithmetic

Take 17 and divide it by 6\. Two complete sixes fit inside it, with 5 left over.

Do the same with 23\. Three complete sixes fit inside it, again with 5 left over.

So 17 and 23 are different numbers, but division by 6 puts them in the same repeating position: both leave remainder 5\.

This is the basic idea of \\modular arithmetic\\. We choose a number to divide by and organise all integers according to their possible remainders. The number we divide by — 6 in this example — is called the \\modulus\\. We say that we are working \\modulo 6\\, or simply \\mod 6\\.

There are two closely related pieces of notation worth separating.

The remainder calculation can be written

A comparison of modular positions is usually written

($17\bmod 6=5$ asks for the remainder left when 17 is divided by 6\. By contrast, $17\equiv 5\pmod 6$ says that 17 and 5 occupy the same remainder class when the modulus is 6\. The ideas are closely connected, but the two notations are doing slightly different jobs.)

We also have $23\equiv 5\pmod 6$, and therefore $17\equiv 23\pmod 6$.

The symbol $\equiv$ is read here as “is congruent to”. In general,

means that $a$ and $b$ leave the same remainder when divided by $m$. Equivalently, their difference $a-b$ is divisible by $m$.

Changing the modulus changes the grouping. Modulo 6 there are six possible remainder positions: 0, 1, 2, 3, 4 and 5\. Modulo 10 there are ten. Modulo 30 there are thirty.

This simple change of viewpoint is extremely useful in number theory. Divisibility, repeating patterns, arithmetic progressions and many questions about prime numbers become easier to see when integers are organised by remainder rather than treated as one long sequence.

The Prime Spring makes this visible. Its turn modulus determines how many repeating modular positions are displayed. Changing the modulus does not change which numbers are prime; it changes only the way the same integers are arranged, allowing different arithmetic structure to become visible.

See also: residue class, arithmetic progression, prime number, Prime Spring.