CS 121 › Lesson 5 of 12

Number Theory & Modular Arithmetic

Lesson 5 · OKSTEM College · AS Computer Science

Divisibility & Modular Arithmetic

We say a divides b (written a | b) if there exists an integer k such that b = ak. Modular arithmetic works with remainders: a ≡ b (mod m) means m | (a−b).

12 ≡ 2 (mod 5)   because 5 | (12−2)
7 ≡ 1 (mod 3)    because 3 | (7−1)
−3 ≡ 2 (mod 5)   because 5 | (−3−2) = −5

Modular arithmetic is behind hash tables (index = key mod size), cyclic error-detection codes, and public-key cryptography.

GCD & the Euclidean Algorithm

The greatest common divisor gcd(a,b) is the largest integer dividing both a and b. The Euclidean algorithm computes it efficiently.

gcd(a, b) = gcd(b, a mod b)   while b ≠ 0

gcd(48, 18):
  gcd(48, 18) = gcd(18, 12)
  gcd(18, 12) = gcd(12, 6)
  gcd(12, 6)  = gcd(6, 0) = 6

The Euclidean algorithm runs in O(log min(a,b)) steps — very efficient even for large integers.

Prime Numbers & Unique Factorization

An integer p ≥ 2 is prime if its only divisors are 1 and itself. The Fundamental Theorem of Arithmetic: every integer ≥ 2 has a unique prime factorization.

360 = 2³ · 3² · 5
1001 = 7 · 11 · 13

Trial division up to √n suffices to test primality.

Modular Inverse & Applications

The modular inverse of a (mod m) is a number a′ such that a · a′ ≡ 1 (mod m). It exists iff gcd(a,m)=1. Used in RSA encryption.

Find the inverse of 3 mod 7: need 3x ≡ 1 (mod 7).
Try x=5: 3·5=15=2·7+1 ⇒ 15 ≡ 1 (mod 7). ✓
So 3−1 ≡ 5 (mod 7).

Practice Problems

1. Compute gcd(252, 105) using the Euclidean algorithm.

gcd(252, 105): 252 = 2·105 + 42
gcd(105, 42): 105 = 2·42 + 21
gcd(42, 21): 42 = 2·21 + 0
gcd = 21

2. What is 17 mod 5? Is 17 ≡ 2 (mod 5) true?

17 = 3·5 + 2, so 17 mod 5 = 2.
17 ≡ 2 (mod 5) is True — 5 | (17−2) = 15. ✓

Knowledge Check

a ≡ b (mod m) means

Congruence is not equality — 12 ≡ 2 (mod 5) but 12 ≠ 2.
Correct — their difference is a multiple of m.
Congruence is about divisibility of differences, not factorization.
The roles of the variables are different.
Recap: a ≡ b (mod m) ⇔ m | (a−b) ⇔ a and b have the same remainder when divided by m.

The Euclidean algorithm computes

LCM is related but the algorithm directly gives GCD.
Correct — gcd(a,b) = gcd(b, a mod b) until b = 0.
Primality testing is a different algorithm.
Extended Euclidean gives the inverse; plain Euclidean gives GCD.
Recap: Euclidean algorithm — repeatedly replace (a,b) with (b, a mod b) until the remainder is 0. The last non-zero remainder is the GCD.

A prime number has exactly

Every integer is divisible by 1 as well.
Correct — primes have exactly 2 positive divisors.
Perfect squares have an odd count; primes always have exactly 2.
2 is prime and is even.
Recap: p is prime ⇔ p ≥ 2 and its only positive divisors are 1 and p. Note: 1 is NOT prime (has only one divisor).

The modular inverse of a (mod m) exists when

Primality of a is not the condition.
Correct — a and m must be coprime (no common factor > 1).
If m is prime, all a from 1 to m−1 have inverses, but the condition is still gcd=1.
a < m is neither necessary nor sufficient.
Recap: a−1 mod m exists ⇔ gcd(a,m)=1. If gcd > 1, no inverse exists. Used in RSA: choose e with gcd(e, φ(n))=1.

Hash tables commonly use modular arithmetic to

Sorting is unrelated to modular arithmetic.
Correct — mod wraps large keys into the range [0, size−1].
Encryption uses more complex modular math (RSA, etc.), not just key%size.
Duplicates are handled by the collision resolution strategy, not mod itself.
Recap: index = hash(key) % table_size. Mod ensures the result is always a valid index regardless of how large the hash value is.

← PreviousNext →