28-01 — Modular Arithmetic Review

Phase: 28 — Cryptography Mathematics Subject: 28-01 Prerequisites: 00-08 (Basic Number Theory), 26-03 (Combinations — for counting arguments) Next subject: 28-02 — Classical Ciphers

Learning Objectives

By the end of this subject, you will be able to:

1. Perform modular arithmetic operations fluently and understand the ring structure of Z_n
2. Compute modular inverses using the Extended Euclidean Algorithm
3. Apply Fermat's Little Theorem and Euler's Theorem for efficient modular exponentiation
4. Solve systems of congruences using the Chinese Remainder Theorem
5. Understand the mathematical foundations that make RSA and other cryptographic systems secure

Core Content

1. Modular Arithmetic Refresher

Modular arithmetic is arithmetic on remainders. For integers $a, b, n$ with $n > 0$:

$$a \equiv b \pmod{n} \iff n \mid (a - b)$$

The set $\mathbb{Z}_n = \{0, 1, 2, ..., n-1\}$ forms a ring under addition and multiplication mod $n$.

Key properties: - $(a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n$ - $(a \cdot b) \mod n = [(a \mod n) \cdot (b \mod n)] \mod n$ - $a^k \mod n$ can be computed efficiently using modular exponentiation (square-and-multiply)

2. Modular Inverses

$a$ has a multiplicative inverse mod $n$ (written $a^{-1}$) if:

$$a \cdot a^{-1} \equiv 1 \pmod{n}$$

Existence condition: $\gcd(a, n) = 1$ (a and n are coprime).

Extended Euclidean Algorithm: Finds $x, y$ such that $ax + ny = \gcd(a, n)$. When $\gcd(a, n) = 1$, $x$ is the modular inverse of $a$ mod $n$.

3. Fermat's Little Theorem

If $p$ is prime and $p \nmid a$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

Corollary: $a^p \equiv a \pmod{p}$ for any integer $a$.

Use in cryptography: Enables fast computation of $a^b \mod p$ by reducing the exponent mod $p-1$: $$a^b \mod p = a^{b \mod (p-1)} \mod p$$

4. Euler's Theorem (Generalisation)

For any $n$ and $\gcd(a, n) = 1$:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

where $\phi(n)$ is Euler's totient function (count of integers $1 \leq k \leq n$ with $\gcd(k, n) = 1$).

For prime $p$: $\phi(p) = p - 1$, recovering Fermat's Little Theorem.

For $n = pq$ (product of two primes): $\phi(n) = (p-1)(q-1)$. This is the key to RSA security.

5. Chinese Remainder Theorem (CRT)

The CRT solves systems of congruences with coprime moduli.

Theorem: If $\gcd(m_1, m_2) = 1$, the system: $$x \equiv a_1 \pmod{m_1}$$ $$x \equiv a_2 \pmod{m_2}$$

has a unique solution mod $m_1 m_2$.

Construction: Find $M = m_1 m_2$, $M_1 = M/m_1$, $M_2 = M/m_2$. Compute $y_1 = M_1^{-1} \mod m_1$ and $y_2 = M_2^{-1} \mod m_2$. Then: $x = a_1 M_1 y_1 + a_2 M_2 y_2 \pmod{M}$.

CRT in RSA: Decrypting a ciphertext $c$ mod $n = pq$ can be done by computing $m_p = c^{d_p} \mod p$ and $m_q = c^{d_q} \mod q$, then combining via CRT. This is ~4x faster than computing $c^d \mod n$ directly.

Worked Examples

Example 1: Extended Euclidean Algorithm

Problem: Find the modular inverse of 17 mod 43.

Solution:

Apply the Extended Euclidean Algorithm to find $17x + 43y = \gcd(17, 43)$.

$43 = 2·17 + 9
17 = 1·9  + 8
 9 = 1·8  + 1
 8 = 8·1  + 0
$

Back-substitute:

$1 = 9 - 1·8
  = 9 - 1·(17 - 1·9) = 2·9 - 1·17
  = 2·(43 - 2·17) - 1·17 = 2·43 - 5·17
$

So $-5 \cdot 17 + 2 \cdot 43 = 1$, meaning $17^{-1} \equiv -5 \equiv 38 \pmod{43}$.

Answer: $17^{-1} \equiv 38 \pmod{43}$. Check: $17 \cdot 38 = 646$, $646 \div 43 = 15$ remainder $1$. ✓

Example 2: Fermat's Little Theorem

Problem: Compute $3^{100} \mod 11$.

Solution:

Since 11 is prime and $3 \nmid 11$, Fermat's Little Theorem gives $3^{10} \equiv 1 \pmod{11}$.

$100 = 10 \cdot 10$, so $3^{100} = (3^{10})^{10} \equiv 1^{10} \equiv 1 \pmod{11}$.

Answer: $3^{100} \equiv 1 \pmod{11}$.

Example 3: Chinese Remainder Theorem

Problem: Find $x$ such that $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$.

Solution:

$m_1 = 3, a_1 = 2$; $m_2 = 5, a_2 = 3$. $M = 15$. $M_1 = 5$, need $5y_1 \equiv 1 \pmod{3}$: $5 \equiv 2 \pmod{3}$, $2 \cdot 2 = 4 \equiv 1$, so $y_1 = 2$. $M_2 = 3$, need $3y_2 \equiv 1 \pmod{5}$: $3 \cdot 2 = 6 \equiv 1$, so $y_2 = 2$.

$x = a_1 M_1 y_1 + a_2 M_2 y_2 = 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 = 20 + 18 = 38 \equiv 8 \pmod{15}$.

Answer: $x \equiv 8 \pmod{15}$. Check: $8 \equiv 2 \pmod{3}$ ✓, $8 \equiv 3 \pmod{5}$ ✓.

Practice Problems

Problem 1: Find the modular inverse of 13 mod 47 using the Extended Euclidean Algorithm.

Problem 2: Compute $7^{50} \mod 13$ using Fermat's Little Theorem.

Problem 3: For $n = 91 = 7 \cdot 13$, compute $\phi(91)$.

Problem 4: Solve: $x \equiv 1 \pmod{4}$, $x \equiv 2 \pmod{7}$, $x \equiv 3 \pmod{9}$ (note: $\gcd(4,7)=1$, $\gcd(4,9)=1$, $\gcd(7,9)=1$).

Problem 5: Show that if $a^k \equiv 1 \pmod{n}$ and $a^m \equiv 1 \pmod{n}$, then $a^{\gcd(k,m)} \equiv 1 \pmod{n}$.

Summary

1. Modular arithmetic operates on remainders; $\mathbb{Z}_n$ forms a ring with efficient modular multiplication and exponentiation
2. Modular inverses exist when $\gcd(a, n) = 1$; found via Extended Euclidean Algorithm
3. Fermat's Little Theorem ($a^{p-1} \equiv 1 \pmod{p}$) enables fast modular exponentiation for prime moduli
4. Euler's Theorem generalises to $a^{\phi(n)} \equiv 1 \pmod{n}$; $\phi(pq) = (p-1)(q-1)$ is the RSA key insight
5. Chinese Remainder Theorem solves systems of congruences and enables faster RSA decryption

Pitfalls

• Confusing the condition for modular inverses. Many students think inverses only exist when the modulus is prime. In fact, $a$ has an inverse mod $n$ whenever $\gcd(a, n) = 1$, regardless of whether $n$ is prime (e.g., $3^{-1} \equiv 7 \pmod{10}$).
• Reducing the exponent incorrectly with Fermat's Little Theorem. The theorem says $a^{p-1} \equiv 1 \pmod{p}$, so exponents reduce modulo $p-1$, NOT modulo $p$. Computing $a^b \bmod p$ as $a^{b \bmod p}$ is wrong.
• Miscomputing Euler's totient for composite numbers. For $n = pq$ (distinct primes), $\phi(n) = (p-1)(q-1)$. A common error is using $(p-1)(q-1)$ when $p$ and $q$ share factors, or forgetting to account for repeated prime factors in the general totient formula.
• Forgetting the final modular reduction in CRT. After computing $x = a_1 M_1 y_1 + a_2 M_2 y_2$, you must reduce modulo $M = m_1 m_2$. The solution is $x \bmod M$, not the raw sum.
• Using the standard Euclidean Algorithm when an inverse is needed. To find $a^{-1} \bmod n$, you need the Extended Euclidean Algorithm to recover the Bezout coefficients. The standard algorithm only gives $\gcd(a, n)$.

Key Terms

• Chinese Remainder Theorem (CRT)
• Euler's theorem
• Extended Euclidean Algorithm
• Fermat's Little Theorem
• Modular inverse
• Modulo operation
• Ring $\mathbb{Z}_n$
• Totient function $\phi(n)$

Quiz

Q1: The modular inverse of $a$ mod $n$ exists if and only if:

A) $a < n$ B) $\gcd(a, n) = 1$ C) $a$ is even D) $n$ is prime

Correct: B)

• If you chose B: Correct. A modular inverse exists exactly when $a$ and $n$ are coprime.
• If you chose A: Being smaller than $n$ is not sufficient (e.g., $a = 4, n = 8$: $\gcd(4, 8) = 4 \neq 1$).
• If you chose C: Evenness is irrelevant. 2 has an inverse mod 5 ($2^{-1} \equiv 3$).
• If you chose D: If $n$ is prime, every non-zero $a$ has an inverse, but inverses also exist for composite $n$ (e.g., $3^{-1} \equiv 7 \mod 10$).

Q2: Fermat's Little Theorem states that for prime $p$ and $p \nmid a$:

A) $a^p \equiv a \pmod{p}$ B) $a^{p-1} \equiv 1 \pmod{p}$ C) $a^{p} \equiv 1 \pmod{p}$ D) $a^{p-1} \equiv 0 \pmod{p}$

Correct: B)

• If you chose B: Correct. $a^{p-1} \equiv 1 \pmod{p}$ when $p$ is prime and $p \nmid a$.
• If you chose A: This is a corollary (multiply both sides by $a$), but the main theorem is $a^{p-1} \equiv 1$.
• If you chose C: This would mean $a^p - 1$ is divisible by $p$, which is false in general (try $a=2, p=5$: $2^5 = 32$, $32-1 = 31$ not divisible by 5).
• If you chose D: $a^{p-1} \equiv 0$ would mean $p \mid a^{p-1}$, implying $p \mid a$, contradicting $p \nmid a$.

Q3: Euler's totient function $\phi(15)$ equals:

A) 8 B) 6 C) 4 D) 15

Correct: A)

• If you chose A: Correct. $15 = 3 \cdot 5$. Numbers coprime to 15: 1, 2, 4, 7, 8, 11, 13, 14. That's 8 numbers. Formula: $\phi(15) = \phi(3)\phi(5) = 2 \cdot 4 = 8$.
• If you chose B: $\phi(15) \neq 6$. You may have miscounted or used $\phi(n) = n/2$ incorrectly.
• If you chose C: $\phi(15) \neq 4$. Only 4 numbers would be wrong.
• If you chose D: That's just $n$ itself. $\phi(n) < n$ for $n > 1$.

Q4: The Chinese Remainder Theorem guarantees:

A) A solution exists for any system of congruences B) A unique solution mod $m_1 m_2$ when $\gcd(m_1, m_2) = 1$ C) A solution only when all moduli are prime D) No solution when moduli overlap

Correct: B)

• If you chose B: Correct. CRT guarantees a unique solution modulo the product of coprime moduli.
• If you chose A: Solutions exist only when moduli are pairwise coprime (or compatible when not). Not for any system.
• If you chose C: CRT works for any coprime moduli, not just primes. $x \equiv 2 \pmod{4}$, $x \equiv 3 \pmod{9}$ works fine.
• If you chose D: Overlapping moduli can have solutions if the congruences are compatible.

Q5: For $n = pq$ where $p, q$ are large primes, $\phi(n)$ equals:

A) $p + q - 1$ B) $(p-1)(q-1)$ C) $pq$ D) $p + q$

Correct: B)

• If you chose B: Correct. For $n = pq$ with distinct primes $p, q$: $\phi(n) = \phi(p)\phi(q) = (p-1)(q-1) = pq - p - q + 1$.
• If you chose A: This is close but wrong. $(p-1)(q-1) = pq - p - q + 1$, not $p + q - 1$.
• If you chose C: $\phi(n) = n$ only when $n = 1$ or $n = 2$. For $n = pq$, most numbers share a factor with $n$.
• If you chose D: This is neither $\phi(n)$ nor related to it directly.

Q6: To compute $a^b \mod n$ efficiently, we use:

A) Compute $a^b$ first, then take mod B) Square-and-multiply (modular exponentiation), reducing mod $n$ at each step C) Use a calculator D) Approximate with floating point

Correct: B)

• If you chose B: Correct. Modular exponentiation computes $(a^2 \mod n), (a^4 \mod n), (a^8 \mod n), ...$ and multiplies the relevant ones. This keeps numbers small throughout.
• If you chose A: Computing $a^b$ first is infeasible for large $b$ (e.g., $b = 10^{100}$). The intermediate number has billions of digits.
• If you chose C: A calculator overflows for large exponents. The modular reduction must happen during computation.
• If you chose D: Floating point loses precision and doesn't give exact modular results.

Q7: In RSA, the security relies on the difficulty of:

A) Computing $\phi(n)$ without knowing the prime factors of $n$ B) Computing modular inverses C) Adding large numbers D) Finding $a^{b} \mod n$

Correct: A)

• If you chose A: Correct. RSA key generation needs $\phi(n) = (p-1)(q-1)$, which requires knowing $p$ and $q$. Without factoring $n = pq$, computing $\phi(n)$ is as hard as factoring.
• If you chose B: Modular inverses are easy to compute (Extended Euclidean Algorithm). Not a security basis.
• If you chose C: Addition is trivial and not related to RSA security.
• If you chose D: Modular exponentiation is efficient (square-and-multiply). It's the one-way function, not the hard problem.

Q8: CRT speeds up RSA decryption because:

A) It avoids modular exponentiation entirely B) It computes two smaller exponentiations ($c^{d_p} \mod p$ and $c^{d_q} \mod q$) and combines them, which is ~4x faster than one large exponentiation C) It reduces the key size D) It eliminates the need for private keys

Correct: B)

• If you chose B: Correct. Computing mod $p$ and mod $q$ separately uses numbers ~half the size, and combining via CRT adds only $O(\log n)$ overhead. Total speedup is ~4x.
• If you chose A: CRT still requires modular exponentiation, just two smaller ones.
• If you chose C: CRT is a computation trick, not a key size reduction. The key size $n = pq$ is unchanged.
• If you chose D: CRT is a decryption optimisation. Private keys ($d$ or $d_p, d_q$) are still essential.

Next Steps

Continue to 28-02 — Classical Ciphers to explore the historical foundations of cryptography before diving into modern symmetric and asymmetric encryption.