[Contact] [About] [Articles] [Links] [Toggle Color]
[Exorcism]
A Primer on Modulo Arithmetic

By Mike Kaarhus

June 2016. 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 or %.  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 just one of an infinite class of integers x, such that x mod 6 = 3.  For instance, {33, 39, 45, 51, ...} mod 6 all equal 3.  So we say

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

The symbol for “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 congruent to {0, 2 or 4} (mod 6) are even, and (except 2) are not prime.
  • All integers congruent to 3 (mod 6) have a factor of 3, and therefore (except 3) are not prime.  For instance, {9, 12, 15, 18, ...} ≡ 3 (mod 6), and all have a factor of 3 (even though half of them are odd).
  • Integers congruent to {1 or 5} (mod 6) are always odd, and have no factor of 2 or 3.

As a result, for twin prime pairs (p, p+2) ≥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).

And it is not just primes p and p+2 that are congruent to 5 and 1 (mod 6) (respectively):

(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

[Contact] [About] [Articles] [Links] [Top] [Privacy] [Sitemap] [Toggle Color]
[Main Page] [Get NTAS Advisory]