Arithmetic and number theory

Congruences and modular arithmetic

Arithmetic where numbers wrap around after reaching a fixed modulus.

IntuitionThe clock: numbers that wrap around

Look at a clock face. After $12$ o'clock comes $1$ again, not $13$ : the hours "wrap around" every $12$ steps. If it is $9$ o'clock now, $8$ hours later it is not " $17$ o'clock" but $5$ o'clock, because $17$ and $5$ leave the same remainder when divided by $12$ . This everyday wrapping is exactly the idea behind congruences: two integers are treated as "the same" if they differ by a multiple of a fixed number $m$ , called the modulus. Congruences let us replace huge numbers by their remainders and still compute correctly — the engine behind clocks, calendars, check digits, hash tables, and modern cryptography.

On the modulo-

m

clock, chords connect each residue

x

a x \bmod m

. Change

m

and

a

to watch when the map permutes all residues vs collapses onto a subgroup.

SchoolDefinition and basic properties

Definition: Congruence modulo $m$

Fix a positive integer $m$ (the modulus). Two integers $a$ and $b$ are **congruent modulo $m$ **, written $a \equiv b \pmod{m}$ , when $m$ divides their difference: $m \mid (a-b)$ . Equivalently, $a$ and $b$ leave the same remainder when divided by $m$ . All integers congruent to a fixed $a$ form its residue class $[a] = \{\dots, a-m, a, a+m, a+2m, \dots\}$ , and there are exactly $m$ distinct residue classes, written $\mathbb{Z}/m\mathbb{Z}$ .

a \equiv b \pmod{m} \iff m \mid (a-b)

Here $a,b,m$ are integers with $m>0$ ; the symbol $\mid$ reads "divides", and $\pmod m$ names the modulus attached to a congruence. This single definition already tells us that congruence is reflexive, symmetric, and transitive — an equivalence relation — which is why it makes sense to talk about "the residue classes modulo $m$ " as objects in their own right, collected into the set $\mathbb{Z}/m\mathbb{Z} = \{\,[0],[1],\dots,[m-1]\,\}$ .

\mathbb{Z}/m\mathbb{Z} = \{\,[0],\,[1],\,\dots,\,[m-1]\,\}

Which operations respect congruence?
Operation	Rule (if $a\equiv b,\ c\equiv d \pmod m$ )	Numeric example (mod $12$ )
Addition	$a+c\equiv b+d \pmod m$	$9+8\equiv 21\equiv 9 \pmod{12}$
Subtraction	$a-c\equiv b-d \pmod m$	$2-5\equiv -3\equiv 9 \pmod{12}$
Multiplication	$ac\equiv bd \pmod m$	$5\times 5\equiv 25\equiv 1 \pmod{12}$
Division (cancel $c$ )	valid only if $\gcd(c,m)=1$	$4\times 2\equiv 4\times 5\pmod 6$ but $2\not\equiv 5$

UndergraduateTheorems

Theorem: Congruence is an equivalence relation compatible with

+

and

\times

For a fixed modulus $m$ : (i) $a \equiv a \pmod{m}$ for every $a$ ; (ii) $a\equiv b \pmod m \implies b\equiv a\pmod m$ ; (iii) $a\equiv b,\ b\equiv c \pmod m \implies a\equiv c \pmod m$ ; and if $a\equiv b \pmod m$ and $c\equiv d\pmod m$ then $a+c \equiv b+d \pmod{m}$ and $ac \equiv bd \pmod{m}$ .

Why is it true?

This is what makes congruences usable as arithmetic: it means we can add, subtract, and multiply remainders directly instead of the huge original numbers, and always get the correct remainder back — the reason computers can check a $16$ -digit card number or compute $7^{100} \bmod 13$ without ever storing a $100$ -digit number.

Proof

Reflexivity: $a-a=0$ and $m\mid 0$ for every $m$ , so $a\equiv a\pmod m$ .

Symmetry: if $a\equiv b\pmod m$ then $a-b=mk$ for some integer $k$ , so $b-a=m(-k)$ ; since $-k$ is also an integer, $m\mid(b-a)$ , i.e. $b\equiv a\pmod m$ .

Transitivity: if $a\equiv b\pmod m$ and $b\equiv c\pmod m$ , write $a-b=mk_1$ and $b-c=mk_2$ . Adding these, $a-c=(a-b)+(b-c)=m(k_1+k_2)$ , so $m\mid(a-c)$ and $a\equiv c\pmod m$ .

Compatibility with addition: from $a-b=mk_1$ and $c-d=mk_2$ , add the two equations: $(a+c)-(b+d) = m(k_1+k_2)$ , which is a multiple of $m$ , so $a+c\equiv b+d\pmod m$ .

Compatibility with multiplication: write $ac-bd = ac-bc+bc-bd = c(a-b)+b(c-d) = c\cdot mk_1 + b\cdot mk_2 = m(ck_1+bk_2)$ . This is again a multiple of $m$ , so $ac\equiv bd\pmod m$ . Together, (i)-(iii) make congruence an equivalence relation, and the last two steps show every ring operation on $\mathbb{Z}$ descends to a well-defined operation on residue classes $\mathbb{Z}/m\mathbb{Z}$ .

Theorem: Cancellation law and the existence of modular inverses

If $\gcd(c,m)=1$ , then $ac\equiv bc \pmod m,\ \gcd(c,m)=1 \implies a\equiv b \pmod m$ . Equivalently, $c$ has a multiplicative inverse modulo $m$ : an integer $u$ with $cu\equiv 1\pmod m$ .

Why is it true?

Ordinary "division" is really multiplication by an inverse, and this theorem tells us exactly when that inverse exists modulo $m$ : precisely when $c$ shares no common factor with $m$ . Without this condition cancellation genuinely fails (see the last row of the table above), which is why every later result about powers modulo $m$ — Fermat's little theorem, Euler's theorem, the Chinese remainder theorem — is built on top of this single algebraic fact.

Proof

Since $\gcd(c,m)=1$ , Bézout's identity (a consequence of the Euclidean algorithm) guarantees $\exists\, u,v \in \mathbb{Z}:\ cu+mv=1$ : there exist integers $u,v$ with $cu+mv=1$ .

Multiply both sides of $ac\equiv bc\pmod m$ by $u$ : $acu\equiv bcu\pmod m$ . Now substitute $cu=1-mv$ : the left side becomes $a(1-mv)=a-amv$ , and since $amv$ is a multiple of $m$ , $a(1-mv)\equiv a\pmod m$ ; likewise the right side $b(1-mv)\equiv b\pmod m$ . Hence $a\equiv b\pmod m$ , proving cancellation.

Moreover, taking $a=1,b=0,c=c$ is not needed — directly, $cu = 1-mv \equiv 1 \pmod m$ by the same substitution, so $u$ itself is the multiplicative inverse of $c$ modulo $m$ : this is exactly the object whose existence Theorem statement claims.

The hypothesis $\gcd(c,m)=1$ is essential: take $c=4,\ m=6$ (so $\gcd(4,6)=2\neq1$ ). Then $4\times 2=8\equiv 2\pmod 6$ and $4\times 5=20\equiv 2\pmod 6$ , so $4\times2\equiv 4\times5\pmod 6$ , yet $2\not\equiv 5\pmod 6$ — cancellation genuinely fails once the coprimality hypothesis is dropped.

AdvancedReal-World Applications and Worked Examples

Modular arithmetic is one of the most quietly ubiquitous tools in applied mathematics. Calendars use it to find the day of the week (mod $7$ ); barcode and ISBN systems use it to catch typing errors with a single check digit (mod $11$ or mod $10$ ); hash tables in computer science map keys to buckets by taking a remainder; and RSA-style cryptography (covered in depth in the next two topics) encodes and decodes messages entirely through modular exponentiation. Two concrete examples below show the everyday reasoning behind the calendar and the check-digit applications.

Example: Finding the day of the week

If today is Tuesday, what day of the week will it be $100$ days from now?

Solution

The days of the week repeat with period $7$ , so only the remainder of $100$ upon division by $7$ matters: $100 = 7\times 14 + 2$ , so $100 \equiv 2 \pmod 7$ .

By the additive compatibility proved above, moving forward $100$ days has the same effect modulo $7$ as moving forward just $2$ days: Tuesday $+\,2$ days is Thursday.

So $100$ days from a Tuesday is a Thursday. Notice that we never had to count all $100$ days one by one — congruence let us collapse a large number into its small, equivalent remainder.

Example: Verifying an ISBN-10 check digit

An ISBN-10 code $d_1d_2\cdots d_{10}$ is valid exactly when $\sum_{i=1}^{10} i\, d_i \equiv 0 \pmod{11}$ . Check whether $0\text{-}306\text{-}40615\text{-}2$ is a valid ISBN-10.

Solution

List the digits $d_1,\dots,d_{10} = 0,3,0,6,4,0,6,1,5,2$ and form the weighted sum $\sum i\,d_i = 1(0)+2(3)+3(0)+4(6)+5(4)+6(0)+7(6)+8(1)+9(5)+10(2)$ .

Compute each term: $0,6,0,24,20,0,42,8,45,20$ . Adding them: $0+6+0+24+20+0+42+8+45+20 = 165$ .

By the multiplicative and additive compatibility of congruence, we only need $165 \bmod 11$ : since $11\times 15 = 165$ , we get $165 \equiv 0 \pmod{11}$ . The check passes, so $0\text{-}306\text{-}40615\text{-}2$ is a valid ISBN-10. If a single digit were mistyped, the weighted sum would almost certainly fail to be $\equiv 0 \pmod{11}$ , which is exactly why publishers use this scheme to catch data-entry errors automatically.

ResearchCongruences at the research frontier: residue systems in modern cryptography

Research frontier as of 2026

Where the subject stands (as of 2026). Two-hundred-year-old congruence arithmetic is now the computational core of two very active research areas.

1. Homomorphic encryption and residue number systems (RNS). Modern fully homomorphic encryption schemes such as CKKS (Cheon, Kim, Kim, Song, 2017) let a server compute directly on encrypted data. Their efficient implementations represent each large ciphertext coefficient in an RNS: a tuple of remainders modulo several small, pairwise coprime primes (an idea built directly on the Chinese remainder theorem, covered in the next-but-one topic). This turns one slow big-integer multiplication into several fast, independent, parallelizable modulo-small-prime multiplications — an active hardware and systems research direction (GPU- and FPGA-accelerated RNS-CKKS, 2023-2026).

2. Post-quantum lattice cryptography. NIST's finalized post-quantum standards ML-KEM (Kyber) and ML-DSA (Dilithium, both 2024) perform almost all of their arithmetic modulo a fixed small prime (e.g. $3329$ for Kyber), using the Number-Theoretic Transform — a Fourier transform built entirely from modular congruences — to multiply polynomials quickly. Choosing moduli that make this transform efficient, and proving the resulting schemes secure, remains an active area of cryptographic engineering.

3. Distribution of residues. On the purely theoretical side, questions about how residues modulo $m$ are distributed (e.g. how large the smallest quadratic non-residue modulo a prime $p$ can be) remain open in general and are only fully resolved under the Generalized Riemann Hypothesis; explicit numerical bounds for these quantities continue to be improved.

Using the standard convention $0 \le r < m$ , what is $-17 \bmod 5$ ?

If $a \equiv 4 \pmod 9$ and $b \equiv 7 \pmod 9$ , what is $ab \bmod 9$ ?

If today is Tuesday, what day of the week is $50$ days from now?

The cancellation law $ac\equiv bc \pmod m \implies a\equiv b\pmod m$ is guaranteed to hold when:

References

Carl Friedrich Gauss (1801). Disquisitiones Arithmeticae
Jung Hee Cheon, Andrey Kim, Miran Kim, Yongsoo Song (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers · DOI:10.1007/978-3-319-70694-8_15