Modular Arithmetic

Definition

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value called the modulus. Two integers a and b are said to be congruent modulo n, written as a ≡ b (mod n), if their difference a - b is divisible by n.

This means that a and b leave the same remainder when divided by n.

Formal Definition

a ≡ b (mod n) ⟺ n | (a - b)

Equivalently:

a ≡ b (mod n) ⟺ a mod n = b mod n

Properties of Modular Arithmetic

Let a ≡ b (mod n) and c ≡ d (mod n). Then:

1. Addition

a + c ≡ b + d (mod n)

2. Subtraction

a - c ≡ b - d (mod n)

3. Multiplication

a × c ≡ b × d (mod n)

4. Exponentiation

a^k ≡ b^k (mod n) for any non-negative integer k

5. Division (Cancellation)

If gcd(c, n) = 1 and ac ≡ bc (mod n), then:

a ≡ b (mod n)

Equivalence Classes

Modular arithmetic partitions the integers into n equivalence classes. The equivalence class of an integer a modulo n is:

[a]_n = {a + kn : k ∈ ℤ}

The set of all equivalence classes modulo n is denoted by ℤ_n or ℤ/nℤ.

ℤ_n = {0, 1, 2, ..., n-1}

Complete Residue System

A complete residue system modulo n is a set of n integers such that every integer is congruent modulo n to exactly one element of the set.

The most common complete residue system is {0, 1, 2, ..., n-1}.

Other examples for n = 7:

{-3, -2, -1, 0, 1, 2, 3}
{7, 8, 9, 10, 11, 12, 13}

Fermat's Little Theorem

If p is a prime number and a is an integer not divisible by p, then:

a^p-1 ≡ 1 (mod p)

Equivalently:

a^p ≡ a (mod p) for all integers a

Euler's Theorem

If a and n are coprime (gcd(a, n) = 1), then:

a^φ(n) ≡ 1 (mod n)

Where φ(n) is Euler's totient function, counting integers from 1 to n that are coprime to n.

Examples

Example 1: Verify that 17 ≡ 5 (mod 6).

Solution: 17 - 5 = 12, and 12 is divisible by 6. Therefore, 17 ≡ 5 (mod 6). Both 17 and 5 leave remainder 5 when divided by 6.

Example 2: Calculate (15 + 23) mod 7.

Solution: 15 + 23 = 38. 38 ÷ 7 = 5 remainder 3. Therefore, (15 + 23) ≡ 3 (mod 7).

Alternative: 15 ≡ 1 (mod 7) and 23 ≡ 2 (mod 7), so 15 + 23 ≡ 1 + 2 ≡ 3 (mod 7).

Example 3: Find 2¹⁰⁰ mod 7 using Fermat's Little Theorem.

Solution: Since 7 is prime, 2⁶ ≡ 1 (mod 7) by Fermat's Little Theorem.

100 = 6 × 16 + 4

Therefore, 2¹⁰⁰ = (2⁶)¹⁶ × 2⁴ ≡ 1¹⁶ × 16 ≡ 16 ≡ 2 (mod 7)

Example 4: What is the last digit of 3²⁰²⁴?

Solution: The last digit is 3²⁰²⁴ mod 10.

Since φ(10) = φ(2) × φ(5) = 1 × 4 = 4, and gcd(3, 10) = 1, by Euler's theorem: 3⁴ ≡ 1 (mod 10).

2024 = 4 × 506, so 3²⁰²⁴ = (3⁴)⁵⁰⁶ ≡ 1⁵⁰⁶ ≡ 1 (mod 10).

The last digit is 1.

Chinese Remainder Theorem

Given a system of congruences with pairwise coprime moduli:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
⋮
x ≡ a_k (mod n_k)

where gcd(n_i, n_j) = 1 for all i ≠ j, there exists a unique solution modulo N = n₁ × n₂ × ... × n_k.

Applications

Cryptography: RSA encryption relies heavily on modular arithmetic.
Computer Science: Hash functions, checksums, and random number generators.
Clock Arithmetic: Time calculations wrap around every 12 or 24 hours.
Calendar Calculations: Determining days of the week for any date.
ISBN and UPC Codes: Error detection using modular checksums.
Music Theory: Musical intervals wrap around the octave.
Game Theory: Analyzing strategies in games with cyclical patterns.