Modular Arithmetic

Overview

Clock Arithmetic

Modular arithmetic is arithmetic that "wraps around" after reaching a certain value, like a clock. On a 12-hour clock, 10 + 5 = 3 (not 15). This idea is formalized using congruences and is fundamental to cryptography, hashing, and error-correcting codes.

Definition

Congruence

For integers a, b and positive integer m, we say a is congruent to b modulo m, written:

a ≡ b (mod m)

if m | (a - b), i.e., a and b have the same remainder when divided by m.

Examples: 17 ≡ 2 (mod 5) because 17 - 2 = 15 = 5 × 3. -3 ≡ 4 (mod 7) because -3 - 4 = -7 = 7 × (-1).

Theorem

Properties of Congruence

If a ≡ b (mod m) and c ≡ d (mod m), then:

Addition: a + c ≡ b + d (mod m) Subtraction: a - c ≡ b - d (mod m) Multiplication: a × c ≡ b × d (mod m) Exponentiation: aⁿ ≡ bⁿ (mod m) for n ≥ 0

Warning: Division is NOT always valid. 6 ≡ 0 (mod 6) but 6/2 ≢ 0/2 (mod 6) since 3 ≢ 0 (mod 6).

Example

Modular Arithmetic Calculations

Find 47 × 63 mod 10: 47 ≡ 7 (mod 10) 63 ≡ 3 (mod 10) 47 × 63 ≡ 7 × 3 = 21 ≡ 1 (mod 10)

Find 2¹⁰ mod 7: 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 1 (mod 7) 2¹⁰ = (2³)³ × 2¹ ≡ 1³ × 2 = 2 (mod 7).

Theorem

Fermat's Little Theorem

If p is prime and a is not divisible by p, then: aᵖ⁻¹ ≡ 1 (mod p)

Equivalently: aᵖ ≡ a (mod p) for all integers a.

Example: 2⁶ mod 7 = 64 mod 7 = 1 (since 7 is prime and gcd(2,7) = 1).

Fermat's Little Theorem is used in primality testing and RSA cryptography.

Note

Modular Inverses

The modular inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1.

Example: The inverse of 3 mod 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).

Modular inverses are essential for division in modular arithmetic and for the RSA algorithm.