In short
Modular arithmetic is arithmetic with remainders. Two integers a and b are congruent modulo n — written a \equiv b \pmod{n} — if n divides their difference. Congruence behaves like equality: you can add, subtract, and multiply both sides freely. This turns remainders into a self-contained number system where only n values (0, 1, 2, \dots, n-1) exist, and every operation wraps around. Applications range from clock calculations to divisibility tests to finding the last digit of enormous powers.
What is 23 hours after 14{:}00? Not 37{:}00 — clocks do not go that high. After reaching 24, the hours reset to 0. So 14 + 23 = 37, and 37 - 24 = 13, giving you 13{:}00.
You just did modular arithmetic. You added two numbers and then took the remainder when dividing by 24. The clock does not care whether the total is 37 or 13 or 61 — all it shows is the remainder after dividing by 24. In the language of this article, 37 \equiv 13 \pmod{24}.
This idea — arithmetic where numbers wrap around — turns out to be far more than a clock trick. It is a full number system with its own addition and multiplication, and it is the right tool for questions about remainders and last digits. What is the remainder when 7^{100} is divided by 5? What is the last digit of 3^{2026}? Is 123456789 divisible by 9? All of these are modular arithmetic questions, and all of them have clean answers once you know the rules.
The Indian mathematician Aryabhata used remainder-based calculations in the Aryabhatiya (499 CE) to solve astronomical problems — computing planetary positions that cycle with fixed periods. The technique of reducing large numbers to small remainders and working entirely with those remainders is one of the most efficient computational tools in mathematics.
Congruence modulo n
Congruence Modulo $n$
Let n be a positive integer. Two integers a and b are congruent modulo n, written
if n \mid (a - b) — that is, if n divides the difference a - b.
Equivalently, a \equiv b \pmod{n} if and only if a and b have the same remainder when divided by n.
Some examples with n = 5:
- 17 \equiv 2 \pmod{5} because 17 - 2 = 15 and 5 \mid 15. Also, 17 \div 5 = 3 remainder 2, and 2 \div 5 = 0 remainder 2 — same remainder.
- -3 \equiv 2 \pmod{5} because -3 - 2 = -5 and 5 \mid (-5). Negative numbers work too: -3 divided by 5 gives quotient -1 and remainder 2 (since -3 = 5 \times (-1) + 2).
- 23 \equiv 8 \equiv 3 \pmod{5} — all three leave remainder 3 when divided by 5.
The symbol \equiv with \pmod{n} is not the same as =. The statement 17 \equiv 2 \pmod{5} does not say 17 = 2. It says 17 and 2 are equivalent from the point of view of remainders mod 5. They are different integers but they belong to the same residue class — the set of all integers that leave remainder 2 when divided by 5, namely \{\dots, -8, -3, 2, 7, 12, 17, 22, \dots\}.
Modulo n, there are exactly n residue classes: one for each possible remainder 0, 1, 2, \dots, n-1. Every integer falls into exactly one of these classes. The entire infinite number line is partitioned into n lanes, and modular arithmetic is the arithmetic of those lanes.
Properties of congruence
Congruence modulo n is an equivalence relation — it satisfies reflexivity (a \equiv a), symmetry (if a \equiv b then b \equiv a), and transitivity (if a \equiv b and b \equiv c then a \equiv c). These are the same three properties that ordinary equality satisfies, and they are the reason you can manipulate congruences almost like equations.
The algebraic properties that make modular arithmetic powerful:
Addition. If a \equiv b \pmod{n} and c \equiv d \pmod{n}, then a + c \equiv b + d \pmod{n}.
Proof: n \mid (a - b) and n \mid (c - d), so n \mid [(a + c) - (b + d)] by the linearity property of divisibility.
Subtraction. If a \equiv b \pmod{n} and c \equiv d \pmod{n}, then a - c \equiv b - d \pmod{n}.
Multiplication. If a \equiv b \pmod{n} and c \equiv d \pmod{n}, then ac \equiv bd \pmod{n}.
Proof: Write a = b + nk and c = d + nl. Then ac = (b + nk)(d + nl) = bd + bnl + dnk + n^2kl = bd + n(bl + dk + nkl). So n \mid (ac - bd).
Powers. If a \equiv b \pmod{n}, then a^k \equiv b^k \pmod{n} for any positive integer k. This follows by applying the multiplication rule repeatedly — or by mathematical induction.
These four rules mean you can reduce first, then compute. To find 47 \times 83 \pmod{5}, you do not need to multiply 47 \times 83 = 3901 and then divide by 5. Instead: 47 \equiv 2 \pmod{5} and 83 \equiv 3 \pmod{5}, so 47 \times 83 \equiv 2 \times 3 = 6 \equiv 1 \pmod{5}. The answer is 1, and you never handled a number larger than 6.
One critical warning: division does not always work. From 6 \equiv 0 \pmod{6}, you might want to divide both sides by 2 to get 3 \equiv 0 \pmod{6}, but 3 \not\equiv 0 \pmod{6}. Division by d is valid only when \gcd(d, n) = 1 — that is, when d and the modulus are co-prime. This subtlety separates modular arithmetic from ordinary arithmetic.
Modular addition and multiplication tables
For a fixed modulus n, the n residues \{0, 1, 2, \dots, n-1\} form a closed system under addition and multiplication mod n. You can write out the complete addition and multiplication tables. Here they are for n = 4:
Addition mod 4:
| + | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
Multiplication mod 4:
| \times | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 0 | 2 |
| 3 | 0 | 3 | 2 | 1 |
Look at the multiplication table. The row for 2 contains only 0 and 2 — it never produces 1 or 3. This means 2 has no multiplicative inverse mod 4: there is no x with 2x \equiv 1 \pmod{4}. But 3 does have an inverse: 3 \times 3 = 9 \equiv 1 \pmod{4}, so 3 is its own inverse. A residue a has a multiplicative inverse mod n if and only if \gcd(a, n) = 1 — the co-primality condition again.
Applications
Divisibility tests
Many standard divisibility tests are secretly statements about congruences.
Divisibility by 9. A number is divisible by 9 if and only if the sum of its digits is divisible by 9. The reason: 10 \equiv 1 \pmod{9}, so 10^k \equiv 1^k = 1 \pmod{9} for every k. A number like 5274 is 5 \times 10^3 + 2 \times 10^2 + 7 \times 10 + 4, which mod 9 becomes 5 \times 1 + 2 \times 1 + 7 \times 1 + 4 \times 1 = 18 \equiv 0 \pmod{9}. So 9 \mid 5274.
Divisibility by 3. The same logic: 10 \equiv 1 \pmod{3}, so a number is divisible by 3 if and only if its digit sum is.
Divisibility by 11. Here 10 \equiv -1 \pmod{11}, so 10^k \equiv (-1)^k \pmod{11}. This alternates: 10^0 \equiv 1, 10^1 \equiv -1, 10^2 \equiv 1, and so on. The test: a number is divisible by 11 if and only if its alternating digit sum (add and subtract digits from right to left) is divisible by 11. For 918082: 2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0 \pmod{11}, so 11 \mid 918082.
Last digits of powers
The last digit of an integer is its remainder mod 10. So finding the last digit of 7^{100} is the same as computing 7^{100} \pmod{10}.
Compute the first few powers of 7 mod 10: 7^1 \equiv 7, 7^2 \equiv 49 \equiv 9, 7^3 \equiv 63 \equiv 3, 7^4 \equiv 21 \equiv 1 \pmod{10}. The pattern repeats every 4 powers: 7, 9, 3, 1, 7, 9, 3, 1, \dots Since 100 = 4 \times 25, we have 7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}. The last digit of 7^{100} is 1.
This "find the cycle, then reduce the exponent" strategy works for any base and modulus, and it is the standard approach to last-digit problems in Indian competitive exams.
Two worked examples
Example 1: Find the remainder when $3^{2026}$ is divided by $7$
Step 1. Compute powers of 3 modulo 7 until you find a cycle.
3^1 \equiv 3 \pmod{7}
3^2 \equiv 9 \equiv 2 \pmod{7}
3^3 \equiv 3 \times 2 = 6 \equiv -1 \pmod{7}
3^4 \equiv 3 \times (-1) = -3 \equiv 4 \pmod{7}
3^5 \equiv 3 \times 4 = 12 \equiv 5 \pmod{7}
3^6 \equiv 3 \times 5 = 15 \equiv 1 \pmod{7}
Why: at each step, multiply the previous result by 3 and reduce mod 7. The cycle ends when you hit 1, because then multiplying by 3 again gives 3 — back to the start.
Step 2. Identify the cycle length.
The powers of 3 mod 7 cycle with period 6: 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, \dots
Why: 3^6 \equiv 1 \pmod{7} means every sixth power resets. To find 3^{2026} \pmod{7}, you only need to know where 2026 falls in this 6-cycle.
Step 3. Reduce the exponent modulo the cycle length.
2026 = 6 \times 337 + 4, so 2026 \equiv 4 \pmod{6}.
Why: 3^{2026} = (3^6)^{337} \times 3^4 \equiv 1^{337} \times 3^4 = 3^4. The enormous exponent reduces to a small one.
Step 4. Read off the answer.
3^{2026} \equiv 3^4 \equiv 4 \pmod{7}.
Why: from Step 1, 3^4 \equiv 4 \pmod{7}.
Result. The remainder when 3^{2026} is divided by 7 is 4.
The power of the method: 3^{2026} is a number with nearly a thousand digits, yet you found its remainder mod 7 using only single-digit arithmetic.
Example 2: Prove that $n^3 - n$ is divisible by $6$ for every positive integer $n$
This is not a computation problem — it is a proof. But modular arithmetic turns it into a clean case analysis.
Step 1. Factor n^3 - n.
n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1)
Why: this is the product of three consecutive integers. Three consecutive integers always include a multiple of 2 and a multiple of 3, so their product is divisible by 2 \times 3 = 6.
Step 2. Prove divisibility by 2 using congruences.
Every integer n satisfies either n \equiv 0 \pmod{2} or n \equiv 1 \pmod{2}.
If n \equiv 0: then n is even, so 2 \mid n, so 2 \mid n(n-1)(n+1).
If n \equiv 1: then n - 1 \equiv 0, so n - 1 is even, and 2 \mid (n-1)n(n+1).
Either way, 2 \mid (n^3 - n).
Why: among any two consecutive integers, one is even. Since n-1, n are consecutive, at least one is even.
Step 3. Prove divisibility by 3 using congruences.
Every integer satisfies n \equiv 0, 1, or 2 \pmod{3}.
If n \equiv 0: 3 \mid n, done.
If n \equiv 1: n - 1 \equiv 0, so 3 \mid (n-1), done.
If n \equiv 2: n + 1 \equiv 3 \equiv 0, so 3 \mid (n+1), done.
Why: among any three consecutive integers, exactly one is a multiple of 3. Since n-1, n, n+1 are three consecutive integers, one of them is divisible by 3.
Step 4. Combine.
2 \mid (n^3 - n) and 3 \mid (n^3 - n). Since \gcd(2, 3) = 1, it follows that 6 \mid (n^3 - n).
Why: when two co-prime numbers both divide a quantity, their product divides it too. This is a consequence of the Fundamental Theorem of Arithmetic — see Number Theory Basics.
Result. 6 \mid (n^3 - n) for every positive integer n.
The factoring insight — recognising n^3 - n as the product of three consecutive integers — is what makes the proof short. Without that factoring, you would need to handle many more cases. Factoring first, then using modular arithmetic on each factor, is a pattern that applies broadly.
Common confusions
-
"a \equiv b \pmod{n} means a = b." It does not. Congruence is a weaker relation than equality. 17 \equiv 2 \pmod{5}, but 17 \neq 2. The symbol \equiv means "same remainder when divided by n," not "same number."
-
"You can divide both sides of a congruence by any number." You cannot. 12 \equiv 6 \pmod{6}, but dividing both sides by 6 gives 2 \equiv 1 \pmod{6}, which is false. Division by d is valid only when \gcd(d, n) = 1. This is the single biggest source of errors in modular arithmetic.
-
"Modular arithmetic only works with positive numbers." It works with all integers, including negative ones. -3 \equiv 2 \pmod{5} is a perfectly valid congruence: -3 - 2 = -5, and 5 \mid (-5).
-
"The remainder is always less than the dividend." The remainder when dividing by n is always between 0 and n - 1 inclusive. It is less than the divisor n, not the dividend. So 3 \bmod 7 = 3 (the remainder is less than the divisor but larger than the dividend is possible when the dividend is small).
-
"a \bmod n and a \pmod{n} are the same notation." They serve different roles. a \bmod n is an operation — it produces a number (the remainder). a \equiv b \pmod{n} is a relation — it states that two numbers are congruent. The parentheses and the \equiv sign distinguish the two usages.
-
"The cycle length for a^k \pmod{n} is always n." Not in general. The cycle length (called the order of a modulo n) divides \phi(n) (Euler's totient function), but it can be much smaller. For 3^k \pmod{7}, the cycle length is 6 (which happens to equal \phi(7) = 6), but for 2^k \pmod{7}, the cycle length is 3 (since 2^3 = 8 \equiv 1 \pmod{7}).
Going deeper
If you came here for the rules of congruence, the divisibility tests, and the technique for finding last digits and remainders, you have everything you need. The rest of this section is for readers who want to see the deeper algebraic structure and the theorems that power more advanced applications.
Fermat's little theorem
If p is a prime and a is any integer not divisible by p, then:
This is Fermat's little theorem, and it gives an immediate upper bound on the cycle length of powers mod a prime: the cycle length always divides p - 1. For example, p = 7 gives a^6 \equiv 1 \pmod{7} for any a not divisible by 7. You saw this in Example 1: 3^6 \equiv 1 \pmod{7}, exactly as the theorem predicts.
The theorem is proved by considering the p - 1 products a \cdot 1, a \cdot 2, \dots, a \cdot (p-1) modulo p. Since \gcd(a, p) = 1, these are all distinct residues (no two are congruent mod p), so they are a permutation of 1, 2, \dots, p - 1. Multiplying them all together: a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}. Since \gcd((p-1)!, p) = 1, divide both sides by (p-1)! to get a^{p-1} \equiv 1.
Euler's theorem and the totient function
Fermat's little theorem generalises to composite moduli. Euler's totient function \phi(n) counts the number of integers from 1 to n that are co-prime to n. For a prime p, \phi(p) = p - 1. For n = 12, the integers co-prime to 12 are 1, 5, 7, 11, so \phi(12) = 4.
Euler's theorem: if \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}.
This is the master tool for reducing large exponents modulo n. To find 7^{2026} \pmod{12}, compute \phi(12) = 4, then 2026 = 4 \times 506 + 2, so 7^{2026} \equiv 7^2 = 49 \equiv 1 \pmod{12}.
The Chinese Remainder Theorem
If m and n are co-prime, and you know x \equiv a \pmod{m} and x \equiv b \pmod{n}, then there is a unique x modulo mn satisfying both congruences simultaneously. This is the Chinese Remainder Theorem, and it was known to Indian and Chinese mathematicians centuries ago — Aryabhata's kuttaka method for solving simultaneous remainder conditions is an early instance.
The theorem means you can break a difficult modular problem into simpler pieces. To solve x \equiv 2 \pmod{3} and x \equiv 3 \pmod{5} simultaneously: the solutions mod 15 form a single residue class, and testing shows x \equiv 8 \pmod{15}.
Where this leads next
Modular arithmetic is a tool that appears throughout mathematics, from elementary divisibility to advanced cryptography.
- Number Theory Basics — the foundation that this article builds on: primes, divisibility, GCD, and the Fundamental Theorem of Arithmetic.
- Mathematical Induction — the proof technique that establishes many modular identities, including the power rule and Fermat's little theorem.
- Operations and Properties — modular arithmetic forms an algebraic structure (a ring) with the same properties of closure, commutativity, and associativity studied there.
- Number Systems — the residue classes modulo n form a finite number system, a miniature version of the integers with only n elements.
- Relations — congruence modulo n is an equivalence relation, and the residue classes are its equivalence classes. This connection links modular arithmetic to the abstract theory of relations.