Part 1: Fundamentals
What is Modular Arithmetic?Modular arithmetic is a system where numbers "wrap around" after reaching a certain value called the modulus. The most intuitive example is a 12-hour clock: after 12 o'clock, we don't say 13 o'clock—we wrap back to 1.When we compute a mod n, we're finding the remainder when a is divided by n.
a mod n = a - n × floor(a / n)
Or equivalently: a mod n = r where a = n × q + r and 0 ≤ r < n

Part 2: Congruence Notation
The ≡ Symbol
Two numbers are congruent modulo n if they have the same remainder when divided by n. We write:
a ≡ b (mod n)

Part 3: Modular Operations
Addition
(a + b) mod n = ((a mod n) + (b mod n)) mod n

Subtraction
(a - b) mod n = ((a mod n) - (b mod n) + n) mod n
The + n handles negative intermediate results.

Multiplication
(a × b) mod n = ((a mod n) × (b mod n)) mod n

Division (Multiplicative Inverse)
Division is not straightforward in modular arithmetic. Instead of dividing by b, we multiply by the modular multiplicative inverse of b.
The inverse of a modulo n (written as a⁻¹) is a number such that:
a × a⁻¹ ≡ 1 (mod n)
Important: The inverse exists only if gcd(a, n) = 1 (they are coprime).

Part 4: Finding Modular Inverse

Extended Euclidean Algorithm (Best General Method)
The Key Insight
We want to find x such that:
a·x ≡ 1 (mod n)

This means: a·x = 1 + n·k for some integer k
Rearranging: a·x - n·k = 1 or a·x + n·y = 1
The Extended Euclidean Algorithm finds x and y!
Step-by-Step Process
Example: Find 17⁻¹ mod 43
Step 1: Apply Euclidean Algorithm (find gcd)

43 = 2 × 17 + 9
17 = 1 × 9  + 8
9  = 1 × 8  + 1
8  = 8 × 1  + 0   ← gcd = 1 (inverse exists!)

Step 2: Back-substitute to express 1 as combination of 17 and 43

1 = 9 - 1×8
1 = 9 - 1×(17 - 1×9)
1 = 2×9 - 1×17
1 = 2×(43 - 2×17) - 1×17
1 = 2×43 - 5×17

So: (-5) × 17 + 2 × 43 = 1

Step 3: Extract the inverse
From -5 × 17 ≡ 1 (mod 43)
Convert -5 to positive: -5 + 43 = 38
Answer: 17⁻¹ ≡ 38 (mod 43)
Verify: 17 × 38 = 646 = 15 × 43 + 1 ≡ 1 (mod 43) ✓

Part 5: Modular Exponentiation
Computing a^b mod n efficiently is crucial for cryptography.
result = (a ** b) % n # Extremely slow for large b
Fast Exponentiation (Binary Method)
Uses the property: a^b = a^(b/2) × a^(b/2) if b is even

Property Formula
Addition (a + b) mod n = ((a mod n) + (b mod n)) mod n
Subtraction (a - b) mod n = ((a mod n) - (b mod n) + n) mod n
Multiplication (a × b) mod n = ((a mod n) × (b mod n)) mod n
Exponentiation a^b mod n = use fast exponentiation
Reflexive a ≡ a (mod n)
Symmetric if a ≡ b then b ≡ a (mod n)
Transitive if a ≡ b and b ≡ c then a ≡ c (mod n)