Divisibility and modulo arithmetic are foundational tools in number theory. They describe when one integer divides another, how remainders behave, and why many computations can be reduced to small residue classes.
A useful mental picture is that modular arithmetic performs addition, and every other operation built on it, not on an infinite line as usual, but on a circle of \(m\) points: counting past the last point simply wraps back around to the start. This single idea underlies clock arithmetic, the parity pattern further below, and the multiplication-circle picture in the applications section.
Division with Remainder
Let \(n\in\mathbb{Z}\) and \(m\in\mathbb{Z}\setminus\{0\}\). The division algorithm states that there exist unique integers \(q\) and \(r\) such that
\[ n = qm + r, \qquad 0\le r < |m|. \]
The integer \(q\) is the quotient and \(r\) is the remainder.
Divisibility
We say that \(m\) divides \(n\), written \(m\mid n\), if
\[ m\mid n \iff \exists k\in\mathbb{Z}:\ n=km. \]
Equivalently,
\[ m\nmid n \iff n=km+r\ \text{with}\ r\ne 0. \]
Rearranging gives
\[ r=n-km. \]
For \(m>0\), the quotient in the Euclidean division is \(q=\left\lfloor\frac{n}{m}\right\rfloor\), hence
\[ r=n-m\left\lfloor\frac{n}{m}\right\rfloor. \]
A natural number greater than \(1\) whose only positive divisors are \(1\) and itself is called prime; divisibility as defined here is exactly the relation used to build the prime factorization of every natural number.
Definition of Modulo
The modulo operation returns this canonical remainder:
\[ n\bmod m:=r=n-m\left\lfloor\frac{n}{m}\right\rfloor, \qquad m>0. \]
Example:
\[ 12\bmod 5 =12-5\left\lfloor\frac{12}{5}\right\rfloor =12-5\cdot2 =2. \]
In programming languages, the operator is usually written as %.
Important Programming Note (Negative Values)
Mathematics typically uses Euclidean remainders in \([0,m-1]\) for \(m>0\), while some languages define a % m via truncation toward zero. Therefore negative inputs can differ across languages.
Example:
- Euclidean convention: \(-7\bmod 5=3\).
- In many C-like languages, remainder follows truncation toward zero, so \((-7) \% 5=-2\): \(q=\operatorname{trunc}(-7/5)=-1\), so \(r=-7-5q=-7-5(-1)=-2\), hence \(-7 \% 5=-2\).
A robust Euclidean normalization in code is ((a % m) + m) % m for \(m>0\).
Congruence Modulo \(m\)
Two integers are congruent modulo \(m\) if they leave the same remainder:
\[ a\equiv b\pmod m \iff m\mid(a-b) \iff a\bmod m=b\bmod m. \]
Congruence partitions integers into residue classes and is the algebraic language behind modular arithmetic.
Modulo Arithmetic Rules
For integers \(a,b\) and \(m>0\):
Two basic identities follow directly from the definition. Shifting by a whole multiple of the modulus never changes the remainder,
\[ (a+km)\bmod m = a\bmod m \qquad(k\in\mathbb{Z}), \]
and applying the modulo operation twice has no further effect, since \(a\bmod m\) already lies in \([0,m-1]\):
\[ (a\bmod m)\bmod m = a\bmod m. \]
Both extend to sums, differences, products, and powers:
\[ (a+b)\bmod m = ((a\bmod m)+(b\bmod m))\bmod m, \]
\[ (a-b)\bmod m = ((a\bmod m)-(b\bmod m))\bmod m, \]
\[ (ab)\bmod m = ((a\bmod m)(b\bmod m))\bmod m, \]
\[ a^b\bmod m = (a\bmod m)^b\bmod m \qquad(b\in\mathbb{N}). \]
These are immediate from congruence: if \(a\equiv a'\pmod m\) and \(b\equiv b'\pmod m\), then \(a\pm b\equiv a'\pm b'\pmod m\), \(ab\equiv a'b'\pmod m\), and therefore also \(a^k\equiv (a')^k\pmod m\).
Applications
Multiplication on a Circle
Let \(N\ge 2\) and place the residue classes \(\mathbb{Z}/N\mathbb{Z}=\{0,1,\dots,N-1\}\) as equally spaced points on the unit circle. For a fixed multiplier \(M\in\mathbb{R}\), define
\[ T_M(i)=(M i)\bmod N. \]
The chord diagram obtained from all pairs \((i,T_M(i))\) is a geometric image of modular multiplication. For integer \(M\), \(T_M\) is an endomorphism of \(\mathbb{Z}/N\mathbb{Z}\), and for \(\gcd(M,N)=1\) it is a permutation.
A classical case is \(M=2\): as \(N\) increases, the envelope of the chords approaches a cardioid. This is exactly the family illustrated by the animation above.
Cycle Length of an Additive Sequence
Consider the sequence generated by repeatedly stepping by a fixed increment \(n\) modulo \(m\),
\[ a_i = (a+i\cdot n)\bmod m, \qquad i\in\mathbb{N}_0, \]
such as hue values sampled around a color wheel, or array indices sampled at a fixed stride. Because there are only \(m\) possible residues, the sequence must eventually repeat; the question is after how many steps.
The sequence first returns to an earlier value once \(a_i\equiv a_j\pmod m\) for some \(i>j\), that is,
\[ a+i\cdot n\equiv a+j\cdot n\pmod m \quad\Longleftrightarrow\quad (i-j)\cdot n\equiv 0\pmod m. \]
Writing \(p=i-j>0\) for the period, this says \(m\mid pn\), so \(pn\) must be a common multiple of \(m\) and \(n\). The smallest such \(p\) therefore comes from the smallest common multiple of \(m\) and \(n\), the least common multiple \(\operatorname{lcm}(m,n)\):
\[ p\cdot n=\operatorname{lcm}(m,n) \quad\Longrightarrow\quad p=\frac{\operatorname{lcm}(m,n)}{n}=\frac{m}{\gcd(m,n)}, \]
using \(\operatorname{lcm}(m,n)=\dfrac{mn}{\gcd(m,n)}\) in the last step. So the sequence returns to its starting value after exactly
\[ p=\frac{m}{\gcd(m,n)} \]
steps, producing \(p\) distinct values \(a_0,\dots,a_{p-1}\) before the pattern repeats.
Worked Example: Stepping Through Hues
Take a hue angle \(a=33\) and advance in steps of \(n=20\) modulo \(m=100\). Since
\[ \gcd(100,20)=20, \]
the sequence has period
\[ p=\frac{100}{20}=5. \]
Indeed, \(33,53,73,93,13,33,\dots\) returns to \(33\) after exactly \(5\) steps, so this choice of \(a\), \(n\), and \(m\) generates \(5\) distinct colors before the pattern repeats.
Divisibility via Modulo
Another equivalent divisibility test is
\[ m\mid n \iff n\bmod m=0. \]
This criterion is used directly in the Euclidean GCD algorithm, where divisibility is detected as soon as a remainder becomes zero.
Modulo 2: Even or Odd
\[ n\bmod 2= \begin{cases} 0,& \text{if } n \text{ is even},\\ 1,& \text{if } n \text{ is odd}. \end{cases} \]
Small table:
| n | n mod 2 |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
| 4 | 0 |
| ... | ... |
Flipping parity, that is going from \(k\bmod 2\) to \((k+1)\bmod 2\), can also be written in closed form without any case distinction:
\[ (k+1)\bmod 2 = 1-(k\bmod 2). \]
Since \((-1)^k=1\) for even \(k\) and \((-1)^k=-1\) for odd \(k\), the same quantity is
\[ 1-(k\bmod 2) = \frac{1+(-1)^k}{2}. \]
Since \(\cos(k\pi)=(-1)^k\) for every integer \(k\), this can be written trigonometrically, turning the two points of the mod-2 circle into the two values a cosine takes at integer multiples of \(\pi\):
\[ (k+1)\bmod 2 = \frac{1+\cos(k\pi)}{2}. \]
Modulo 9: Digital Root and Digit Sum
If \(n=\sum_{i=0}^{k}10^i d_i\) in decimal digits \(d_i\), then
\[ n\bmod 9 = \left(\sum_{i=0}^{k}10^i d_i\right)\bmod 9 = \sum_{i=0}^{k}(10^i\bmod 9)(d_i\bmod 9) = \sum_{i=0}^{k}(d_i\bmod 9), \]
because \(10\equiv 1\pmod 9\), hence \(10^i\equiv 1\pmod 9\). So a number is congruent to its digit sum modulo 9.
For \(n>0\), the one-digit digital root is
\[ \operatorname{dr}(n)=1+(n-1)\bmod 9, \]
and \(\operatorname{dr}(0)=0\). The identity for \(n>0\) follows from the residue \(r=n\bmod 9\), and it is best read as a shift with correction:
First shift by one position into \(0,\dots,8\): \[ s=(n-1)\bmod 9\in\{0,\dots,8\}. \]
Then shift back by adding 1: \[ \operatorname{dr}(n)=1+s=1+(n-1)\bmod 9. \]
This is exactly the needed correction of the raw remainder behavior: modulo 9 returns \(0\) for multiples of 9, but the digital root should be \(9\). The \(-1\)-shift moves that special case to \(8\), and the final \(+1\) maps it to \(9\), while all other residues \(1,\dots,8\) stay unchanged.
Modulo 10: Last Decimal Digit
A number modulo 10 is exactly its last decimal digit. Example: \(123\bmod 10=3\).
Sketch:
\[ 123 =1\cdot10^2+2\cdot10^1+3\cdot10^0, \]
and modulo 10 all terms with \(10^1,10^2,\dots\) vanish, leaving only \(3\cdot10^0=3\).
The same principle holds in any base \(b\): the least significant digit is \(n\bmod b\).
Base Conversion via Repeated Division
Write
\[ n=d_k b^k + d_{k-1} b^{k-1}+\dots+d_1 b+d_0, \qquad 0\le d_i<b. \]
Then
\[ d_0=n\bmod b, \]
and removing the last digit is
\[ \left\lfloor\frac{n}{b}\right\rfloor =d_k b^{k-1}+\dots+d_1. \]
Repeating this step yields all digits in base \(b\), from least significant to most significant.
baseConvert(n, b)
i = 0
while (n > 0)
d_i = n % b
n = floor(n / b)
i = i + 1 The collected digits \(d_0,d_1,\dots\) must be read in reverse order.
Worked Example: \(123_{10}\) to Binary
Repeated division by \(2\):
\[ \begin{aligned} 123 &= 2\cdot 61 + 1,\\ 61 &= 2\cdot 30 + 1,\\ 30 &= 2\cdot 15 + 0,\\ 15 &= 2\cdot 7 + 1,\\ 7 &= 2\cdot 3 + 1,\\ 3 &= 2\cdot 1 + 1,\\ 1 &= 2\cdot 0 + 1. \end{aligned} \]
Read remainders bottom-up: \(123_{10}=1111011_2\).
Digit Symbols for Bases Above 10
For \(d_i>9\), symbols continue with letters: \(10=A,11=B,\dots\). This standard notation is commonly used up to base 36. Encodings such as Base64 use an extended alphabet with additional symbols.
Number to Decimal String (Special Case \(b=10\))
The same repeated-division method with \(b=10\) produces decimal digits. If a digit \(d\in\{0,\dots,9\}\) is converted to an ASCII character, one uses
\[ \text{char}=d+48, \]
because ASCII code 48 is the character '0'. Since digits are generated from least significant to most significant, the resulting character sequence must be reversed.
Key Results
- Division algorithm: \(n=qm+r\) with \(0\le r<|m|\) and unique \((q,r)\).
- Divisibility criterion: \(m\mid n\iff n\bmod m=0\).
- Congruence criterion: \(a\equiv b\pmod m\iff m\mid(a-b)\).
- Compatibility of congruence with \(+,-,\cdot\), and therefore with powers.
- Base conversion by repeated division: remainders are read from bottom to top.