☧

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.

Copyright © 2011-2016 Michael Kaarhus

All rights reserved