Skip to content
MathAnvil
§ Arithmetic

Modular Arithmetic

§ Arithmetic

Modular Arithmetic

LK20.133 min read

Modular arithmetic is a system of arithmetic for integers where numbers wrap around when they reach a certain value called the modulus. The expression 'a mod n' represents the remainder when integer a is divided by positive integer n. For example, 17 mod 5 equals 2 because 17 divided by 5 gives quotient 3 with remainder 2.

§ 01

Why it matters

Modular arithmetic forms the backbone of cryptography and computer security systems that protect online banking and digital communications. Credit card validation algorithms use modular arithmetic to detect typing errors in 16-digit card numbers. Computer programmers rely on modular arithmetic for hash functions and random number generation. In pure mathematics, modular arithmetic appears in number theory and abstract algebra, particularly in studying divisibility patterns and solving Diophantine equations. The concept extends naturally to more advanced topics like group theory and ring theory at university level. Even simple applications like determining which day of the week a future date falls on use modular arithmetic with modulus 7. Clock arithmetic itself demonstrates modular 12 systems in everyday life.

§ 02

How to solve modular arithmetic

Modular Arithmetic (Congruences)

  • a mod n is the remainder when a is divided by n: a = n·q + r with 0 ≤ r < n.
  • a ≡ b (mod n) means (a − b) is a multiple of n — equivalently, a and b leave the same remainder when divided by n.
  • Addition and multiplication respect congruence: (a + b) mod n and (a · b) mod n can be computed by reducing each part mod n first.
  • To solve ax ≡ b (mod n) when gcd(a, n) = 1, multiply both sides by the modular inverse of a.

Example: 17 mod 5 = 2 (since 17 = 3·5 + 2). And 17 ≡ 2 (mod 5) because 17 − 2 = 15 is a multiple of 5.

§ 03

Worked examples

Beginner§ 01

Compute 25 mod 7.

Answer: 4

  1. Find the largest multiple of 7 that is ≤ 25 → 7 × 3 = 21 — We want the biggest number of the form 7·k that does not exceed 25. Dividing, 25 ÷ 7 = 3 with something left over, so 7·3 = 21.
  2. Subtract to find the remainder → 25 − 21 = 4 — The remainder is what is left after removing the multiple: 25 − 21 = 4.
  3. State the answer → 25 mod 7 = 4 — So 25 mod 7 = 4 (since 25 = 7·3 + 4).
Easy§ 02

Is 52 ≡ 28 (mod 5)?

Answer: no

  1. Compute the difference a − b → 52 − 28 = 24 — Two numbers are congruent mod n exactly when their difference is a multiple of n. So we compute 52 − 28 = 24.
  2. Check whether 24 is divisible by 5 → 24 = 5 · 4 + 4 — Dividing: 24 ÷ 5 = 4 remainder 4. The remainder is 4 ≠ 0, so the difference is not a multiple of n.
  3. Answer → No — 52 ≢ 28 (mod 5) — No: since 24 is not a multiple of 5, we have 52 ≢ 28 (mod 5).
Medium§ 03

Compute (30 × 5) mod 9.

Answer: 6

  1. Compute the product first → 30 × 5 = 150 — Do the arithmetic inside first: 30 × 5 = 150.
  2. Reduce 150 modulo 9 → 150 = 9 · 16 + 6 — Divide 150 by 9: 150 ÷ 9 = 16 remainder 6. The remainder is what we keep.
  3. State the answer → (30 × 5) mod 9 = 6 — So (30 × 5) mod 9 = 150 mod 9 = 6.
§ 04

Common mistakes

  • Computing 23 mod 6 as 5 instead of the correct answer 5 by incorrectly thinking 23 ÷ 6 = 4 remainder 1
  • Claiming 15 ≡ 8 (mod 6) when actually 15 ≡ 3 (mod 6) and 8 ≡ 2 (mod 6), so they are not congruent
  • Calculating (7 + 11) mod 4 as 2 by adding first to get 18, then finding 18 mod 4 = 2, when the correct approach gives the same result but some confuse the order of operations
§ 05

Frequently asked questions

What is the difference between mod and remainder?
The mod operation and remainder are essentially the same concept. Both give the leftover amount after division. However, in some programming contexts, mod can give negative results whilst mathematical remainder is always non-negative. In pure mathematics, 'a mod n' always gives a value between 0 and n-1 inclusive.
How do you check if two numbers are congruent modulo n?
Two numbers a and b are congruent modulo n if their difference (a - b) is divisible by n. Alternatively, compute both a mod n and b mod n separately — if these remainders are equal, then a ≡ b (mod n). For instance, 23 ≡ 8 (mod 5) because both give remainder 3.
Can the modulus be negative in modular arithmetic?
Mathematically, the modulus n is typically required to be positive. Whilst some advanced contexts allow negative moduli, standard modular arithmetic assumes n > 0. This ensures the remainder is well-defined and lies in the range 0 to n-1, making calculations consistent and predictable.
What does it mean when gcd(a,n) = 1 in modular arithmetic?
When gcd(a,n) = 1, the numbers a and n are coprime, meaning they share no common factors except 1. This condition is crucial for solving linear congruences ax ≡ b (mod n) because it guarantees that a has a modular inverse, making the equation solvable.
Why is modular arithmetic called 'clock arithmetic'?
Modular arithmetic is nicknamed 'clock arithmetic' because clocks demonstrate modular 12 systems. On a 12-hour clock, 10 + 4 = 2 (wrapping around after 12), which parallels how 10 + 4 ≡ 2 (mod 12) in modular arithmetic. The numbers cycle back to the beginning after reaching the modulus.
§ 06

See also

ExpressionIntegerMultipleRangeMeanEquation
§ 06

Related topics

Share this article