Modular arithmetic

Modular arithmetic operates on the remainders of numbers divided by a given modulus rather than on the numbers themselves. For example, rather than computing 2134 + 87659 = 89793, we might compute 4 + 9 = 3 by a modulus of 10. Thus modular arithmetic reduces the unmanageably infinite to the manageably finite. Addition, subtraction, multiplication and exponentiation can all readily be done in modular arithmetic.

With $n$ being an integer, $m$ being a modulus and $r$ being the remainder of $n\div m$ (the number such that $xm+r=n$, here we are unconcerned with the value of the integer $x$), the notation is either $n\equiv r\mod m$ or $n\equiv r{\pmod {m}}$ In our earlier example, $89793\equiv 3\mod 10$. (This also demonstrates that if the modulo is the base of place-value numeration, then taking the remainder is the same as fetching the least significant digit of the integer part). The infinity of $\mathbb {Z} ^{+}$ has been reduced to $\{0,1,\ldots m-1\}$. Obviously $n\equiv n\mod m$ when $0\leq n<m$.

The simplest modular arithmetic uses a modulus of 2; this is the arithmetic of odd and even numbers. Thus, without examining each possible pair of an odd number and an even number (which is of course impossible) we know that an odd number plus an even number is odd but an odd number times an even number is even, because $0+1=1$ but $0\times 1=0$.

Perhaps the moduli of most practical use are 12 and 24 (and thus modular arithmetic is sometimes called "clock arithmetic"). Suppose there is a task which takes a machine precisely 98 hours to complete, and we start the machine on this task at 7:00 AM on Monday. We could compute $7+98=105$, then $105\div 24=4.375$ and then $0.375\times 24=9$ to figure out that, uninterrupted, the machine will finish at 9:00 AM on Friday. Or we could just observe that since $98\equiv 2\mod 24$, the finishing time will be just two hours after the starting time (but on a different day, of course).

Number theory is generally concerned with prime numbers as moduli. Consider for example Fermat's little theorem. Usually remainders are expressed as positive numbers, but mathematicians often use $-1$ when $r=m-1$ (or as a shortcut for $m-1$ when considering arbitrary moduli).

Most calculators don't do modular arithmetic. Instead, they display the decimal expansion of ${\frac {r}{m}}$ to the extent allowed. For example, with a modulo of 7, a calculator will show after the integer part and decimal point, if there is enough room:

0	00 (if fixed to 2 decimal places)
1	142857...
2	285714...
3	428571...
4	571428...
5	714285...
6	857142...

If the integer part of the result has as many digits as the calculator's screen has places, then the result will have the appearance of an integer, and is subject to rounding.

Some computer programming languages, and of course all computer algebra systems, offer built-in tools for modular arithmetic. Programming languages generally implement taking the remainder as an operator rather than a function. The percent sign (%) is used as a modulus operator in C++, Javascript, and a few others. In most flavors of BASIC, the word "mod" is used as the operator. Visual Basic used Mod while REALbasic uses mod.

"From a mathematical point of view, REALbasic's mod works incorrectly when the dividend is negative. Properly, the result of mod should always be positive," writes Matt Newburg. Newburg then gives the examples $-7\equiv 1\mod 8$ (because $-7$ is one more than $-8$) but REALbasic says $-7\equiv -7\mod 8$, as do "a number of other computer [programming] languages." Newburg then suggests programming one's own mod function:

 Function myMod(i as integer, k as integer) As integer
  return ((i mod k) + k) mod k
 End Function