Skip to content
MathAnvil
§ Arithmetic

Modular Arithmetic

§ Arithmetic

Modular Arithmetic

LK20.133 min read

Modular arithmetic deals with remainders after division, focusing on what's left over when one integer is divided by another. The notation a mod n represents the remainder when a is divided by n, always yielding a value between 0 and n-1. Two numbers are congruent modulo n if they leave the same remainder when divided by n, written as a ≡ b (mod n).

§ 01

Why it matters

Modular arithmetic powers modern cryptography, with RSA encryption relying on calculations modulo large prime numbers exceeding 1024 bits. Computer hash functions use modular operations to distribute data evenly across memory locations, while error-correcting codes in CDs and digital communications depend on arithmetic modulo specific numbers. Clock calculations naturally use modular arithmetic — adding 8 hours to 7 PM gives 3 AM because (7 + 8) mod 12 = 3. Credit card validation employs the Luhn algorithm, which uses modular arithmetic to detect typing errors in 16-digit card numbers. In advanced mathematics, modular arithmetic appears in number theory, abstract algebra, and discrete mathematics courses, providing the foundation for understanding cyclic groups and finite fields used in coding theory.

§ 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 36 mod 3.

Answer: 0

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

Is 17 ≡ 13 (mod 4)?

Answer: yes

  1. Compute the difference a − b → 17 − 13 = 4 — Two numbers are congruent mod n exactly when their difference is a multiple of n. So we compute 17 − 13 = 4.
  2. Check whether 4 is divisible by 4 → 4 = 4 · 1 — Dividing: 4 ÷ 4 = 1 remainder 0. The remainder is 0, so the difference is a multiple of n.
  3. Answer → Yes — 17 ≡ 13 (mod 4) — Yes: since 4 is a multiple of 4, we have 17 ≡ 13 (mod 4).
Medium§ 03

Compute (2 × 2) mod 13.

Answer: 4

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

Common mistakes

  • Confusing 23 mod 5 with 23 ÷ 5, writing 4.6 instead of the correct remainder 3
  • Computing (7 × 8) mod 6 as 56 mod 6 = 2, but forgetting that 7 mod 6 = 1 and 8 mod 6 = 2, so the answer is (1 × 2) mod 6 = 2
  • Writing 15 ≡ 7 (mod 4) as false because 15 - 7 = 8, but failing to recognize that 8 is divisible by 4, making the congruence true
§ 05

Frequently asked questions

What is the difference between mod and remainder?
In modular arithmetic, 'mod' always gives a non-negative result between 0 and n-1. For positive numbers, mod and remainder are identical: 17 mod 5 = 2. However, some programming languages handle negative numbers differently, while mathematical modular arithmetic ensures the result stays within the standard range 0 to n-1.
How do you check if two numbers are congruent?
Two numbers a and b are congruent modulo n if their difference is divisible by n. Calculate a - b and check if it's a multiple of n. For example, 23 ≡ 8 (mod 5) because 23 - 8 = 15, and 15 ÷ 5 = 3 with no remainder.
Why does modular arithmetic work with addition and multiplication?
Modular arithmetic preserves addition and multiplication because remainders behave predictably. If a ≡ c (mod n) and b ≡ d (mod n), then (a + b) ≡ (c + d) (mod n) and (a × b) ≡ (c × d) (mod n). This property allows complex calculations by reducing each step modulo n.
What does it mean when gcd(a, n) = 1 in modular arithmetic?
When gcd(a, n) = 1, the numbers a and n are relatively prime, meaning they share no common factors except 1. This guarantees that a has a modular inverse modulo n, allowing equations like ax ≡ b (mod n) to have unique solutions within the range 0 to n-1.
How is modular arithmetic used in everyday technology?
Modular arithmetic appears in credit card checksums, where the Luhn algorithm uses mod 10 calculations to detect errors. Digital clocks use mod 12 or mod 24 arithmetic. Computer hash tables employ modular arithmetic to distribute data efficiently, and internet security relies on modular exponentiation with numbers containing hundreds of digits.
§ 06

See also

IntegerMultipleRangeMean
§ 06

Related topics

Share this article