A Primer on Modulo Arithmetic A Primer on Modulo Arithmetic

By Mike Kaarhus

June 2016. Corrected on Aug. 11, 2022. UNITED STATES – Here is a peculiar fact about prime numbers: For any prime number p ≥ 5, if you divide p by 6, the remainder is either 1 or 5.  When you consider just the remainder of a division, you are doing modulo arithmetic.  If working with integers, it’s rather simple to do.

The most popular modulo operators are mod and %.  They both mean modulo division.  One places the operator between a dividend and a divisor, as in division.  But all one is after is the remainder, not the quotient.  For example,

15 mod 6 = 3,  or 15 % 6 = 3,  because the remainder of the division 15 ÷ 6 is 3.  When dividing an integer by an integer, one wants the remainder as an integer, not as a fraction (not as 3/6 or 0.5).  The result of a modular division is called the residue.  Residue implies that modular division was done, whereas remainder implies that division was done.  The dividend and the divisor don’t have to be integers.  For instance, 15.75 % 6 = 3.75,  because the remainder of the division 15.75 ÷ 6 is 3.75.  Similarly, one can get the residue of a non-integer divided by a non-integer.  But that is not as intuitive.  You have to use the formula:

Here’s the way a Texas Instruments calculator obtains the residue of x mod 6: calculate the floor or int of x/6, multiply that by 6, then subtract the product from x.  Or,

x mod 6 = x – (6 · int(x ÷ 6)).

15 mod 6 = 15 – (6 · int(15 ÷ 6)).
= 3

15.75 mod 6 = 15.75 – (6 · int(15.75 ÷ 6)).
= 3.75

15.75 mod 6.25 = 15.75 – (6.25 · int(15.75 ÷ 6.25))
= 3.25.

Again, it is simplest to work with integers only.  For instance,

33 mod 6 = 3, because 33 ÷ 6 = 5 with a remainder of 3.  Or
3 = 33 – (6 · int(33 ÷ 6)).

People then say things like “33 is congruent to 3 (mod 6)”, which means that 33 is one of an infinite class of integers x, such that x mod 6 = 3.  For instance,

{33, 39, 45, 51, ...} mod 6 = 3.
{33, 39, 45, 51, ...} are congruent to 3 (mod 6).

The symbol for “is congruent to” or “are congruent to” is

{33, 39, 45, 51, ...} ≡ 3 (mod 6).

One can use modular division to accept or reject whole classes of integers as possible primes:

• The possible residues (mod 6) are {0, 1, 2, 3, 4, 5}.
• (All integers) ≡ {0, 2 or 4} (mod 6) are even, and (except 2) are not prime.
• (All integers) ≡ 3 (mod 6) have a factor of 3, and (except 3) are not prime.  For instance, {3, 9, 15, 21 ...} ≡ 3 (mod 6). All have a factor of 3.
• (All integers) ≡ {1 or 5} (mod 6) are odd, and have no factor of 2 or 3.

As a result, for twin prime pairs (p, p+2), p ≥ 5,

(all p) ≡ 5 (mod 6), and
(all p+2) ≡ 1 (mod 6).

For any twin prime pair, the composite (p+1) at the center of the pair is the average of the pair.  Since 0 is the residue (mod 6) between 5 and 1,

(all twin prime averages ≥ 6) ≡ 0 (mod 6).

Not only (primes p, p+2, p ≥ 5) ≡ {5 and 1} (mod 6) (respectively), but also,

(All prime numbers ≥ 5) ≡ {5 or 1} (mod 6).

Caution!  The reverse is not true:

Not (all integers ≡ {5 or 1} (mod 6)) are prime numbers.

For instance, 55 ≡ 1 (mod 6), but 55 is composite. 