= Modular arithmetic
{title2=$\mathbb Z/m\mathbb Z$}
{wiki}
Modular arithmetic performs <addition> and <multiplication> on <integers> while remembering only their <remainders> for a fixed positive <integer modulus> $m$. The relation $a\equiv b\pmod m$ means that $m$ divides $a-b$: the two <integers> lie in the same <congruence class>. For example, $-3$, $2$ and $7$ represent one class modulo $5$. Choosing the <least nonnegative residue> gives exactly $m$ representatives, $0,1,\ldots,m-1$, even though each <congruence class> contains infinitely many <integers>.
A clock supplies a familiar example. Represent the twelve positions by $0,1,\ldots,11$, with $0$ at the position usually labelled twelve. Starting at ten and moving seven positions gives
$$
10+7=17\equiv5\pmod{12}.
$$
The <integer congruence> records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single <congruence class> modulo five spread along the <number line>.
\Image[/modular-arithmetic-clock-and-classes.png]
{title=Clock addition wraps modulo twelve, while integers separated by five represent one congruence class}
The useful surprise is that discarding this information still preserves the arithmetic. If $a\equiv a'$ and $b\equiv b'$ modulo $m$, then $a+b\equiv a'+b'$ and $ab\equiv a'b'$ modulo $m$. Thus a large calculation can reduce its intermediate <integers> after every step. For instance,
$$
10+7\equiv5\pmod{12},\qquad 10\cdot7\equiv10\pmod{12},\qquad 10^2\equiv4\pmod{12}.
$$
Replacing $10$ by $-2$ gives the same answers with smaller intermediate values. The <congruence classes> with these operations form the <quotient ring> $\mathbb Z/m\mathbb Z$; their <addition> alone forms a <cyclic group>. This passage from <integers> to a finite arithmetic system is the setting for <modular exponentiation>, <primality testing> and the <RSA cryptosystem>. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[Ankur Moitra, MIT 18.200, Lecture 15, modular arithmetic and its applications]{ref}
<Multiplicative cancellation> needs extra care. Modulo six, $2\cdot1\equiv2\cdot4$, but $1\not\equiv4$: multiplication by two has merged distinct <congruence classes>. Cancelling a factor while retaining the <integer modulus> is justified when that factor has a <modular multiplicative inverse>, equivalently when it is <coprime> to the <integer modulus>. A <linear congruence> can consequently have no solutions, one solution class, or several solution classes. The <Chinese remainder theorem> supplies a complementary operation: splitting a calculation across <coprime> <integer moduli> and reconstructing its class modulo their product.
Small remainders can also certify impossibility. A <perfect square> has residue zero or one modulo four, as checking the four <congruence classes> shows. Therefore an <integer> equation $x^2=4k+2$ has no solution. The converse direction needs care: a permitted residue does not guarantee an <integer> solution, since $5\equiv1\pmod4$ but five is not a <perfect square>. Such local tests provide necessary conditions for <Diophantine equations> without replacing the full problem.
In \i[Disquisitiones arithmeticae] (1801), <Carl Friedrich Gauss> defines <integer congruence> in article 1 and adopts the symbol $\equiv$ in article 2. Article 12 derives <divisibility> tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima[Gauss, Disquisitiones arithmeticae, section I, articles 1–2 and 12; text from the 1870 collected edition]{ref}
Back to article page
