Modular arithmetic

If you think back to doing division with whole numbers, you may remember finding the whole number result and the remainder after division.

Modulus

The modulus[1] is another name for the remainder after division.

For example, 17 mod 5 = 2, since if we divide 17 by 5, we get 3 with remainder 2.

Modular arithmetic is sometimes called clock arithmetic, since analog clocks wrap around times past 12, meaning they work on a modulus of 12. If the hour hand of a clock currently points to 8, then in 5 hours it will point to 1. While 8 + 5 = 13, the clock wraps around after 12, so all times can be thought of as modulus 12. Mathematically, 13 mod 12 = 1.

Example 1

Compute the following:

1. 10 mod 3
2. 15 mod 5
3. 27 mod 5

1. Since 10 divided by 3 is 3 with remainder 1, 10 mod 3 = 1
2. Since 15 divided by 5 is 3 with no remainder, 15 mod 5 = 0
3. 27 = 128. 128 divide by 5 is 25 with remainder 3, so 27 mod 5 = 3

Try it Now

Compute the following:

1. 23 mod 7
2. 15 mod 7
3. 2034 mod 7

Recall that when we divide 17 by 5, we could represent the result as 3 remainder 2, as the mixed number $\displaystyle3\frac{2}{5}\\$, or as the decimal 3.4. Notice that the modulus, 2, is the same as the numerator of the fractional part of the mixed number, and that the decimal part 0.4 is equivalent to the fraction $\displaystyle\frac{2}{5}\\$. We can use these conversions to calculate the modulus of not-too-huge numbers on a standard calculator.

Modulus on a Standard Calculator

To calculate a mod n on a standard calculator

1. Divide a by n
2. Subtract the whole part of the resulting quantity
3. Multiply by n to obtain the modulus

Example 2

Calculate 31345 mod 419.

 $31345\div{419}=74.8090692$ Now subtract 74 to get just the decimal remainder $74.8090692-74=0.8090692$ Multiply this by 419 to get the modulus $0.8090692\times{419}=339$ This tells us 0.8090692 was equivalent to $\frac{339}{419}$