Number theory basics: divisibility, gcd and modular arithmetic

Computers do arithmetic on whole numbers of fixed size, and when a result is too large it wraps around, like a clock passing twelve. Hash tables place keys in buckets by taking remainders. Check digits on bank cards and ISBNs catch typing errors using remainders. And the cryptography that secures every web connection rests on arithmetic with remainders of very large numbers. This lesson develops the small core of number theory that computing needs: divisibility, the division algorithm, greatest common divisors and Euclid's algorithm, modular arithmetic, inverses, and fast exponentiation. MATH-351 goes much deeper into the theory, including quadratic reciprocity and the distribution of primes; here we keep to what Lesson 12 needs.

Divisibility and the division algorithm

For integers \(a\) and \(b\), we say \(a\) divides \(b\), written \(a \mid b\), if \(b = ak\) for some integer \(k\). So \(3 \mid 12\), \(-3 \mid 12\), \(7 \nmid 12\), and every integer divides 0. Three facts follow at once from the definition. If \(a \mid b\) and \(b \mid c\) then \(a \mid c\). If \(a \mid b\) and \(a \mid c\) then \(a \mid (bx + cy)\) for all integers \(x, y\). And if \(a \mid b\) with \(b \ne 0\), then \(|a| \le |b|\).

Division algorithm. For any integer \(a\) and positive integer \(d\), there are unique integers \(q\) and \(r\) with \(a = qd + r\) and \(0 \le r < d\). Here \(q\) is the quotient and \(r\) the remainder, written \(a \bmod d\). For example \(47 = 6 \cdot 7 + 5\) and \(-47 = -7 \cdot 7 + 2\), so \(-47 \bmod 7 = 2\). Existence: take \(r\) to be the smallest nonnegative number of the form \(a - qd\); if \(r \ge d\) then \(r - d\) would be a smaller one. Uniqueness: if \(qd + r = q'd + r'\) with both remainders in \([0, d)\), then \(d\) divides \(r - r'\), which lies strictly between \(-d\) and \(d\), so \(r = r'\).

Note that programming languages disagree on negative operands. In Python, -47 % 7 is 2, matching the mathematical convention, while in C and Java it is -5, because those languages round the quotient toward zero. This difference has caused real bugs, for example in code that maps negative hash values to bucket numbers.

Number bases come from repeated division. To write 2026 in binary, divide by 2 repeatedly and read the remainders from last to first: 2026 = 11111101010 in base 2. The same method gives hexadecimal, base 16, with digits 0 to 9 and A to F; 2026 is 7EA in hexadecimal, since \(7 \cdot 256 + 14 \cdot 16 + 10 = 2026\).

Primes

A prime is an integer \(p \ge 2\) whose only positive divisors are 1 and \(p\); other integers \(n \ge 2\) are composite. Every integer \(n \ge 2\) has a prime factor: its smallest divisor greater than 1 must be prime, since any divisor of it would be a smaller divisor of \(n\). A composite number \(n\) has a prime factor at most \(\sqrt{n}\), because if \(n = ab\) with \(1 < a \le b\), then \(a^2 \le ab = n\). So to test whether \(n\) is prime by trial division, it is enough to try divisors up to \(\sqrt{n}\).

Euclid's theorem (around 300 BCE, in the Elements). There are infinitely many primes. Proof: given any finite list of primes \(p_1, \dots, p_k\), let \(N = p_1 p_2 \cdots p_k + 1\). Dividing \(N\) by any \(p_i\) leaves remainder 1, so no \(p_i\) divides \(N\). But \(N \ge 2\) has a prime factor, which is therefore a prime not on the list. No finite list contains all primes.

The sieve of Eratosthenes, from the third century BCE, lists all primes up to \(N\): write the numbers from 2 to \(N\), and repeatedly take the smallest number not yet crossed out, declare it prime, and cross out its multiples. Only primes up to \(\sqrt{N}\) need to be sieved with. The Fundamental Theorem of Arithmetic says that every integer \(n \ge 2\) is a product of primes in exactly one way, apart from the order of the factors; for example \(360 = 2^3 \cdot 3^2 \cdot 5\). Existence follows by strong induction, and uniqueness depends on Euclid's lemma below.

Greatest common divisors and Euclid's algorithm

The greatest common divisor \(\gcd(a, b)\) of integers \(a\) and \(b\), not both 0, is the largest integer dividing both. Two integers are coprime, or relatively prime, if their gcd is 1. The definition suggests factoring both numbers, but factoring is slow for large numbers. Euclid's algorithm, also in the Elements and one of the oldest algorithms still in daily use, avoids factoring entirely.

Key lemma. If \(a = qb + r\), then \(\gcd(a, b) = \gcd(b, r)\). Proof: any common divisor of \(a\) and \(b\) divides \(r = a - qb\), and any common divisor of \(b\) and \(r\) divides \(a = qb + r\). So the two pairs have the same common divisors and the same greatest one.

Euclid's algorithm. To find \(\gcd(a, b)\) with \(a \ge b > 0\), replace \((a, b)\) by \((b, a \bmod b)\) and repeat until the second number is 0; the first number is then the gcd. The remainders strictly decrease, so the algorithm stops. It is also fast. Two steps at least halve the larger number: if \(r_1 = a \bmod b\) and \(r_2 = b \bmod r_1\), then \(r_2 < a/2\). So the number of steps is at most about twice the number of binary digits. In 1844 Gabriel Lamé showed that the worst inputs are consecutive Fibonacci numbers, linking this lesson back to Lesson 5; his analysis is often called the first analysis of an algorithm's running time.

Bézout's identity. For integers \(a, b\) not both zero, there are integers \(x, y\) with \(ax + by = \gcd(a, b)\). Moreover \(\gcd(a, b)\) is the smallest positive integer of the form \(ax + by\). The extended Euclidean algorithm computes \(x\) and \(y\) by keeping track, at every step, of how each remainder is written as a combination of \(a\) and \(b\), as in the example. The identity is named after Étienne Bézout, who proved a version for polynomials in the eighteenth century; the integer case was known earlier to Claude-Gaspard Bachet in 1624.

Euclid's lemma. If a prime \(p\) divides a product \(ab\), then \(p \mid a\) or \(p \mid b\). Proof: suppose \(p \nmid a\). Then \(\gcd(p, a) = 1\), since the only positive divisors of \(p\) are 1 and \(p\). By Bézout, \(px + ay = 1\) for some integers, and multiplying by \(b\) gives \(pbx + aby = b\). The prime \(p\) divides both terms on the left, so \(p \mid b\). The lemma is exactly what makes prime factorizations unique: if two factorizations of the same number existed, a prime in the first would divide the product of the second and so equal one of its primes, which could then be cancelled.

Modular arithmetic

Fix a positive integer \(m\), the modulus. Integers \(a\) and \(b\) are congruent modulo \(m\), written \(a \equiv b \pmod{m}\), if \(m \mid (a - b)\), equivalently if they leave the same remainder on division by \(m\). The notation is due to Carl Friedrich Gauss, in his Disquisitiones Arithmeticae of 1801. Congruence modulo \(m\) is an equivalence relation, with \(m\) classes, represented by \(0, 1, \dots, m - 1\); the set of classes is written \(\mathbb{Z}_m\).

Congruence respects addition and multiplication: if \(a \equiv a'\) and \(b \equiv b' \pmod{m}\), then \(a + b \equiv a' + b'\) and \(ab \equiv a'b' \pmod{m}\). For the product, \(ab - a'b' = a(b - b') + b'(a - a')\), and both terms are multiples of \(m\). This lets us reduce at every step of a calculation and keep the numbers small. For example, the last digit of \(7^{100}\) is \(7^{100} \bmod 10\). The powers of 7 modulo 10 are 7, 9, 3, 1 and then repeat with period 4, so \(7^{100} = (7^4)^{25} \equiv 1\) and the last digit is 1. The same rule explains divisibility tests: since \(10 \equiv 1 \pmod 9\), a number is congruent to its digit sum modulo 9.

Division is the subtle operation. An inverse of \(a\) modulo \(m\) is an integer \(a^{-1}\) with \(a a^{-1} \equiv 1 \pmod{m}\). Theorem: \(a\) has an inverse modulo \(m\) if and only if \(\gcd(a, m) = 1\). If the gcd is 1, Bézout gives \(ax + my = 1\), so \(ax \equiv 1\) and \(x\) is an inverse. If the gcd is \(g > 1\), then every \(ax + my\) is a multiple of \(g\) and can never equal 1. For example, modulo 26, the inverse of 7 is 15, since \(7 \cdot 15 = 105 = 4 \cdot 26 + 1\); but 13 has no inverse modulo 26. When \(m = p\) is prime, every nonzero class has an inverse, so \(\mathbb{Z}_p\) is a field, a number system with all four operations, which is why primes are preferred in hashing and cryptography.

Linear congruences can now be solved. To solve \(7x \equiv 3 \pmod{26}\), multiply both sides by the inverse 15: \(x \equiv 45 \equiv 19 \pmod{26}\). Check: \(7 \cdot 19 = 133 = 5 \cdot 26 + 3\). The Chinese remainder theorem, which goes back to Sunzi in the third to fifth century, says that when \(m\) and \(n\) are coprime, the pair of conditions \(x \equiv a \pmod m\) and \(x \equiv b \pmod n\) has exactly one solution modulo \(mn\); MATH-351 proves it and explores its uses.

Fast exponentiation and Fermat's little theorem

Cryptography needs \(a^e \bmod m\) for numbers with hundreds of digits. Multiplying \(a\) by itself \(e\) times is hopeless when \(e\) has 600 digits. Repeated squaring does it in about \(2 \log_2 e\) multiplications, reducing modulo \(m\) after each one. Write \(e\) in binary; square repeatedly to get \(a, a^2, a^4, a^8, \dots\), and multiply together the powers corresponding to the 1 bits. For example, \(3^{13} = 3^8 \cdot 3^4 \cdot 3^1\) because \(13 = 1101_2\). Modulo 7: \(3^1 \equiv 3\), \(3^2 \equiv 2\), \(3^4 \equiv 4\), \(3^8 \equiv 2\), so \(3^{13} \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7\).

Fermat's little theorem (Pierre de Fermat, stated in a letter of 1640). If \(p\) is prime and \(p \nmid a\), then \(a^{p-1} \equiv 1 \pmod{p}\). Proof: the numbers \(a, 2a, \dots, (p-1)a\) are nonzero modulo \(p\) and different from each other, since \(ia \equiv ja\) would give \(i \equiv j\) after multiplying by \(a^{-1}\). So modulo \(p\) they are \(1, 2, \dots, p - 1\) in some order. Multiplying them all together, \(a^{p-1}(p-1)! \equiv (p-1)! \pmod p\), and \((p-1)!\) is invertible because each factor is, so \(a^{p-1} \equiv 1\). Euler generalized it in 1763: if \(\gcd(a, m) = 1\) then \(a^{\varphi(m)} \equiv 1 \pmod m\), where \(\varphi(m)\), Euler's totient, counts the integers in \(1, \dots, m\) coprime to \(m\). For two distinct primes, \(\varphi(pq) = (p-1)(q-1)\), by counting the multiples of \(p\) and of \(q\) and removing them. This is the fact on which RSA, in Lesson 12, is built.

def ext_gcd(a, b):
    # returns (g, x, y) with a*x + b*y = g = gcd(a, b)
    old_r, r, old_x, x, old_y, y = a, b, 1, 0, 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y

def inverse(a, m):
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        return None
    return x % m

def power_mod(a, e, m):
    result, base = 1, a % m
    while e:
        if e & 1:
            result = result * base % m
        base = base * base % m
        e >>= 1
    return result

def sieve(n):
    is_p = [True] * (n + 1); is_p[0] = is_p[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_p[p]:
            for k in range(p * p, n + 1, p):
                is_p[k] = False
    return [p for p in range(n + 1) if is_p[p]]

def euclid_steps(a, b):
    steps = 0
    while b:
        a, b = b, a % b; steps += 1
    return steps

print("ext_gcd(252, 198) =", ext_gcd(252, 198))
print("inverse of 7 mod 26:", inverse(7, 26), " inverse of 13 mod 26:", inverse(13, 26))
print("solve 7x = 3 (mod 26): x =", inverse(7, 26) * 3 % 26)
print("3^13 mod 7 =", power_mod(3, 13, 7), " matches pow:", pow(3, 13, 7))
print("last digit of 7^100:", power_mod(7, 100, 10))
print("primes up to 60:", sieve(60))
print("Fermat check, a^(p-1) mod p for p = 101:", {power_mod(a, 100, 101) for a in range(1, 101)})
print("561 = 3*11*17, yet 2^560 mod 561 =", power_mod(2, 560, 561))
print("2026 in binary:", bin(2026), " in hex:", hex(2026), " -47 % 7 =", -47 % 7)
print("Euclid steps on Fibonacci pair (F30, F29):", euclid_steps(832040, 514229))
print("pow with exponent -1 gives inverses too:", pow(7, -1, 26))

ext_gcd(252, 198) = (18, 4, -5)
inverse of 7 mod 26: 15  inverse of 13 mod 26: None
solve 7x = 3 (mod 26): x = 19
3^13 mod 7 = 3  matches pow: 3
last digit of 7^100: 1
primes up to 60: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
Fermat check, a^(p-1) mod p for p = 101: {1}
561 = 3*11*17, yet 2^560 mod 561 = 1
2026 in binary: 0b11111101010  in hex: 0x7ea  -47 % 7 = 2
Euclid steps on Fibonacci pair (F30, F29): 28
pow with exponent -1 gives inverses too: 15

The line about 561 is a warning. Fermat's theorem says primes pass the test \(a^{n-1} \equiv 1 \pmod n\), but some composites pass it too, for every \(a\) coprime to \(n\). These are the Carmichael numbers, the smallest being \(561 = 3 \cdot 11 \cdot 17\), and in 1994 Alford, Granville and Pomerance proved there are infinitely many. Practical primality tests, such as the Miller–Rabin test, strengthen Fermat's condition so that every composite fails for most bases, and they can certify primes with hundreds of digits in a fraction of a second. In 2002 Agrawal, Kayal and Saxena found a deterministic polynomial-time primality test, settling a long-open question. Factoring, by contrast, has no known fast algorithm, and that gap between testing and factoring is what Lesson 12 exploits.