Fun with Modular Multiplicative Inverses


A regular multiplicative inverse (or just “inverse”) is the reciprocal of a number—the inverse of 2 is 1/2 and the inverse of 1/2 is 2.  The key property is that a number times its inverse equals 1.

Modular multiplicative inverses involve modular arithmetic, which involves the remainders of (typically whole) numbers when divided by a given base.  For example, 15 divided by 7 leaves a remainder of 1, so 15 = 1 modulo 7.  The phrase “modulo 7” means the remainder when divided by 7, and is often abbreviated “mod 7.”  Likewise, 22 = 6 mod 8 (remainder of 6 when 22 is divided by 8) and 143 = 3 mod 10 (remainder of 3 when 143 is divided by 10).

So modular multiplicative inverses combine the ideas of two numbers multiplying to 1 with the notion of the remainder, or mod.  The modular multiplicative inverse of a number is (the smallest) number such that the product of the two is 1, modulo some base.  For example, 3 x 5 = 15 and 15 = 1 mod 7.  So 3 and 5 are modular multiplicative inverses, for the base of 7.  For the base of 7, here are the modular multiplicative inverses:

NumberInverseNotes
0noneAnything × 0 is 0, so the product will never have a remainder of 1.
111 × 1 = 1, for any base.
242 × 4 = 8, or 1 × 7 with a remainder of 1.
353 × 5 = 15, or 2 × 7 with a remainder of 1.
424 and 2 are inverses for base 7.
535 and 3 are inverses for base 7.
666 × 6 = 36, or 5 × 7 with a remainder of 1.
7noneAnything × 7 will be a multiple of 7 and will have a remainder of 0.

The inverses depend on the base and some numbers will not have an inverse.  For example, with base 8:

NumberInverseNotes
0noneAnything × 0 is 0, so the product will never have a remainder of 1.
111 × 1 = 1, for any base.
2noneAnything × 2 will be even and will never have a remainder of 1.
333 × 3 = 9, or 1 × 8 with a remainder of 1.
4noneSame as for 2.
555 × 5 = 25, or 3 × 8 with a remainder of 1.
6noneSame as for 2.
777 × 7 = 48, or 6 × 8 with a remainder of 1.
8noneAnything × 8 will be a multiple of 8 and will have a remainder of 0.

So what has this to do with the image?  Here are graphical representations of the modular multiplicative inverses for bases from 2 to 8.  In each image, the number and its inverse are plotted as squares in the (x, y) plane, where x is the number and y is its inverse.

  

The next image combines the previous seven by using the differences in colors of the corresponding pixels.  Black minus black is black, white minus white is black, and black minus white or white minus black is white.



Now, that image is combined with the one for mod 7, yielding this:

   

Finally, the one at the top of the page is a similar one, only using modulo bases 11 and 13.