Unit 3: GCD and Primality testing

Number-theoretic algorithms rest on divisibility: how integers factor, share common divisors, and behave under the primes. This unit builds from the greatest common divisor (GCD) up to primality-flavoured classifications, treating each as a computational problem with a concrete algorithm and complexity.

I. Foundations and Conventions

Every integer > 1 has a unique prime factorisation (Fundamental Theorem of Arithmetic), and this fact underlies divisor counting, factor-finding, and the number classes below.

• GCD: The largest integer dividing both a and b. Written gcd(a, b); by convention gcd(a, 0) = a.
• Prime: An integer p > 1 whose only positive divisors are 1 and p. Smallest is 2, the only even prime.
• Prime factorisation: n = p₁^e₁ · p₂^e₂ · … · p_k^e_k, with distinct primes pᵢ and exponents eᵢ ≥ 1.
• Coprime: a and b are coprime when gcd(a, b) = 1; they share no prime factor.
• √n bound: If n has a factor > √n, its co-factor is < √n, so testing divisors up to ⌊√n⌋ suffices — the key complexity lever throughout.

II. Basic Euclidean Algorithm

A. Statement and principle

Repeatedly replacing the larger number by its remainder against the smaller preserves the GCD until a remainder of zero exposes the answer.

• Invariant: gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides a − q·b.
• Termination: The remainder strictly decreases and stays non-negative, so it reaches 0.
• Complexity: O(log(min(a, b))) divisions; worst case occurs on consecutive Fibonacci numbers.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

• Symbols: a, b are inputs; a % b is the remainder of a divided by b.
• Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6.

III. Extended Euclidean Algorithm

A. Statement and Bézout's identity

Beyond the GCD, this variant produces integer coefficients expressing that GCD as a linear combination of the inputs.

• Bézout's identity: There exist integers x, y with a·x + b·y = gcd(a, b).
• Recurrence: If gcd(b, a mod b) = b·x₁ + (a mod b)·y₁, then back-substitution gives x = y₁, y = x₁ − ⌊a/b⌋·y₁.
• Use: Computes the modular inverse — x is a⁻¹ mod b when gcd(a, b) = 1.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

• Symbols: returns (g, x, y) satisfying a·x + b·y = g.
• Example: ext_gcd(30, 12) = (6, 1, −2) since 30·1 + 12·(−2) = 6.

IV. Total Number of Divisors of a Number

A. Divisor-count formula

The count of divisors depends only on the exponents in the prime factorisation, not on the primes themselves.

• Formula: d(n) = (e₁ + 1)(e₂ + 1)…(e_k + 1) for n = ∏ pᵢ^eᵢ.
• Reason: Each prime pᵢ contributes an exponent from 0 to eᵢ, giving eᵢ + 1 independent choices.
• Complexity: O(√n) to factorise, then multiply exponent-plus-ones.

def num_divisors(n):
    count, d = 1, 2
    while d * d <= n:
        e = 0
        while n % d == 0:
            n //= d; e += 1
        count *= (e + 1); d += 1
    if n > 1: count *= 2
    return count

• Example: 72 = 2³·3², so d(72) = (3+1)(2+1) = 12.

V. Finding All Prime Factors of a Number

A. Trial-division factorisation

Dividing out each prime as it is found reduces n and guarantees the remaining factors are still prime.

• Method: Divide by 2, then odd d = 3, 5, 7, …, removing all copies of each before advancing.
• Multiplicity: Record each prime as many times as it divides — n = 2·2·3 lists 2 twice.
• Leftover: After the loop, if n > 1 it is itself a prime factor larger than √n₀.

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d); n //= d
        d += 1
    if n > 1: factors.append(n)
    return factors

• Example: 84 → [2, 2, 3, 7].

VI. Finding the Prime Factors by Taking the Square Root

A. The √n cutoff

Stopping trial division at ⌊√n⌋ is correct because a composite n must have a factor no greater than its square root.

• Justification: If n = a·b with a ≤ b, then a ≤ √n; a divisor above √n always pairs with one below.
• Effect: Reduces naïve O(n) scanning to O(√n) — for n ≈ 10¹², about 10⁶ steps instead of 10¹².
• Composite detection: If no divisor ≤ √n is found, n is prime; this is the basic primality test.

def is_prime(n):
    if n < 2: return False
    d = 2
    while d * d <= n:
        if n % d == 0: return False
        d += 1
    return True

VII. K-jagged Numbers

A. Definition by factor structure

A k-jagged number is one whose smallest prime factor equals a given bound, characterising numbers "rough" up to k.

• k-rough / k-jagged: An integer all of whose prime factors are ≥ k; equivalently its least prime factor is at least k.
• Construction: Remove any prime factor smaller than k; if any exists, the number is not k-jagged.
• Contrast with smoothness: Roughness bounds factors from below, whereas smoothness (Section X) bounds them from above.
• Example: 35 = 5·7 is 5-jagged (least prime factor 5); 30 = 2·3·5 is only 2-jagged.

VIII. Stormer Numbers

A. Definition via arctangent and largest prime factor

A Størmer number is a positive integer n for which the greatest prime factor of n² + 1 is at least 2n.

• Condition: Let P(m) be the largest prime factor of m; n is Størmer if P(n² + 1) ≥ 2n.
• Significance: They mark which arctan(1/n) terms cannot be decomposed into smaller Machin-like arctangent identities.
• Density: Størmer numbers are infinite; the first are 1, 2, 4, 5, 6, 9, 10, ….
• Example: For n = 3, n² + 1 = 10 = 2·5, and P(10) = 5 < 6 = 2n, so 3 is not a Størmer number.

IX. Frugal Numbers

A. Definition by digit economy

A frugal (economical) number has more digits than its prime factorisation written with exponents.

• Rule: n is frugal if digits(n) > digits of its factorisation (primes plus exponents, exponent 1 omitted).
• Base dependence: The comparison is base-specific; the standard case uses base 10.
• Rarity: Frugal numbers thin out but occur infinitely often; the smallest in base 10 is 125.
• Example: 125 = 5³ — the number has 3 digits, the factorisation string 53 has 2, so 125 is frugal.

X. P-smooth Numbers in Given Ranges

A. Definition and enumeration

A number is P-smooth when it has no prime factor exceeding P; counting them in a range is a filtering problem.

• Definition: n is P-smooth if P(n) ≤ P, i.e. every prime factor is ≤ P.
• Range check: For each n in [L, R], strip all primes ≤ P; the number is P-smooth iff the residue is 1.
• Sieve approach: Mark multiples of each prime ≤ P to factor a range efficiently rather than factoring each n alone.
• Example: In [1, 10], the 3-smooth numbers are 1, 2, 3, 4, 6, 8, 9 — 5, 7, 10 fail because they carry primes > 3.

XI. Lemoine's Conjecture

A. Statement about odd numbers

Lemoine's conjecture asserts a Goldbach-style decomposition for odd integers using one prime and one semiprime component.

• Statement: Every odd integer n > 5 can be written as p + 2q where p and q are primes.
• Status: Unproven but verified computationally to very large bounds; also called the Levy conjecture.
• Relation: A strong-Goldbach refinement — it constrains not just a sum of primes but the specific form p + 2q.
• Example: 11 = 5 + 2·3 = 3 + 2·2 (p = 5, q = 3 and p = 3, q = 2 both work).

XII. Problems Based on GCD and Primality Testing

A. Common problem patterns

Competitive tasks recombine the primitives above; recognising which primitive applies is the core skill.

1. GCD-driven problems: Reducing fractions, LCM via lcm(a, b) = a·b / gcd(a, b), and diophantine solvability using Bézout — a solution to ax + by = c exists iff gcd(a, b) | c.
2. Primality-driven problems: Counting divisors, testing coprimality across arrays, and factor-based classification (jagged, smooth, frugal) all reduce to O(√n) factorisation or a sieve over a range.

• GCD of an array: Fold pairwise — gcd(gcd(a, b), c); short-circuit when the running GCD reaches 1.
• Range primality: Precompute with a Sieve of Eratosthenes in O(N log log N) instead of testing each number separately.
• Modular inverse: Apply the extended Euclidean algorithm when the modulus is not prime; the inverse exists only when the value is coprime to the modulus.