🧠Thinking Like a Mathematician Unit 3 Review

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of them without leaving a remainder. It's one of the most foundational ideas in number theory, and it shows up everywhere: simplifying fractions, solving equations with integer constraints, and even in cryptography.

You'll see it written as $\gcd(a, b)$ or sometimes just $(a, b)$ for integers $a$ and $b$ .

A few baseline facts to know:

The GCD always exists for any pair of integers, except when both are zero. $\gcd(0, 0)$ is undefined.
$\gcd(a, 0) = |a|$ for any nonzero integer $a$ , since every integer divides 0.
Order doesn't matter: $\gcd(a, b) = \gcd(b, a)$ (commutativity).

Fundamental theorem of arithmetic

Every positive integer greater than 1 can be written as a unique product of prime factors (up to the order of the factors). This is the Fundamental Theorem of Arithmetic, and it's what makes the prime factorization method for finding GCDs work.

Formally, any positive integer $n$ can be expressed as:

$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$

where $p_i$ are distinct primes and $a_i$ are positive integers. Because this factorization is unique, you can compare two numbers' prime breakdowns directly to find what they share.

Euclidean algorithm

The Euclidean algorithm is the most important method for computing GCDs. It's efficient, elegant, and over 2,000 years old.

It relies on one key principle: $\gcd(a, b) = \gcd(b, \ a \bmod b)$ . You keep replacing the larger number with the remainder until the remainder hits zero. At that point, the last nonzero value is the GCD.

</>Code
function GCD(a, b):
  while b ≠ 0:
    temp = b
    b = a mod b
    a = temp
  return a

Example: Find $\gcd(48, 18)$ .

$48 \bmod 18 = 12$ → now find $\gcd(18, 12)$
$18 \bmod 12 = 6$ → now find $\gcd(12, 6)$
$12 \bmod 6 = 0$ → done

The GCD is $6$ .

This algorithm also provides the foundation for the extended Euclidean algorithm, which finds integer coefficients for Bézout's identity (covered below).

Properties of GCD

These properties come up repeatedly in proofs and problem-solving:

Positive: $\gcd(a, b) > 0$ for nonzero $a$ and $b$
Divisibility: $\gcd(a, b)$ divides both $a$ and $b$
Linear combination (Bézout's identity): There exist integers $s$ and $t$ such that $sa + tb = \gcd(a, b)$
Associativity: $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$
Scaling: $\gcd(ka, kb) = |k| \cdot \gcd(a, b)$ for any integer $k$

Calculation methods

There are several ways to compute a GCD. Which one you pick depends on the size of the numbers and whether you're working by hand or on a computer.

Prime factorization method

This approach is intuitive and works well for small numbers.

Factor each number into its prime factors.
Identify the prime factors they have in common.
For each common prime, take the lowest exponent that appears in either factorization.
Multiply those together.

Example: Find $\gcd(60, 48)$ .

$60 = 2^2 \cdot 3 \cdot 5$
$48 = 2^4 \cdot 3$
Common primes: $2$ and $3$ . Take $2^2$ (lower power) and $3^1$ .
$\gcd(60, 48) = 2^2 \cdot 3 = 12$

The downside: for large numbers, finding the prime factorization itself becomes very hard. That's why the Euclidean algorithm is preferred in practice.

Euclidean algorithm steps

Restated as a clear procedure for hand calculation:

Divide the larger number by the smaller one and note the remainder.
Replace the larger number with the smaller number.
Replace the smaller number with the remainder from step 1.
Repeat until the remainder is zero.
The last nonzero remainder is the GCD.

This method is efficient for both small and large numbers, with time complexity $O(\log(\min(a, b)))$ .

Binary GCD algorithm (Stein's algorithm)

This is an optimization of the Euclidean algorithm designed for computers. It replaces division with bitwise operations (shifts and subtractions), which are faster at the hardware level.

The core idea:

If both numbers are even, factor out 2 from both and track it: $\gcd(2a, 2b) = 2 \cdot \gcd(a, b)$ .
If one is even and one is odd, drop the factor of 2 from the even one (it can't be part of the GCD).
If both are odd, subtract the smaller from the larger. The result is even, so you can shift right.
Repeat until the two values are equal. That value, multiplied by all the 2s you factored out in step 1, is the GCD.

This avoids costly division operations entirely, making it particularly efficient for large numbers in hardware implementations.

Applications in mathematics

Diophantine equations

A linear Diophantine equation has the form $ax + by = c$ , where you need integer solutions for $x$ and $y$ .

The key result: solutions exist if and only if $\gcd(a, b)$ divides $c$ . If it doesn't, there are no integer solutions at all.

When solutions do exist, you can find a particular solution using the extended Euclidean algorithm, then derive the general solution from there.

Modular arithmetic

GCD is central to solving linear congruences of the form $ax \equiv b \pmod{m}$ .

A solution exists if and only if $\gcd(a, m)$ divides $b$ .
The number of distinct solutions modulo $m$ equals $\gcd(a, m)$ (when solutions exist).
A multiplicative inverse of $a$ modulo $m$ exists precisely when $\gcd(a, m) = 1$ .
The Chinese Remainder Theorem requires the moduli to be pairwise coprime (i.e., each pair has GCD equal to 1).

Basic definition, Greatest common divisor - Knowino

Fraction simplification

To reduce a fraction to lowest terms, divide both numerator and denominator by their GCD:

$\frac{a}{b} = \frac{a / \gcd(a,b)}{b / \gcd(a,b)}$

For example, $\frac{48}{18}$ : since $\gcd(48, 18) = 6$ , the simplified form is $\frac{8}{3}$ . This gives every rational number a unique simplified representation.

Coprime numbers

Two integers are coprime (also called relatively prime) if $\gcd(a, b) = 1$ . They share no prime factors.

Coprimality matters in several places:

Euler's totient function $\phi(n)$ counts integers from 1 to $n$ that are coprime to $n$ .
The RSA cryptosystem depends on choosing values that are coprime to certain products.
Testing coprimality is straightforward: just compute the GCD and check if it equals 1.

GCD in number theory

Bézout's identity

For any integers $a$ and $b$ , there exist integers $x$ and $y$ such that:

$ax + by = \gcd(a, b)$

This tells you that the GCD is the smallest positive value you can produce as a linear combination of $a$ and $b$ . The extended Euclidean algorithm finds the specific coefficients $x$ and $y$ . Bézout's identity is the theoretical backbone for solving Diophantine equations and working with modular inverses.

Least common multiple

The least common multiple (LCM) is tightly linked to the GCD through this relationship:

$\text{lcm}(a, b) \cdot \gcd(a, b) = |ab|$

So once you know the GCD, computing the LCM is simple:

$\text{lcm}(a, b) = \frac{|ab|}{\gcd(a, b)}$

The LCM is the smallest positive integer divisible by both $a$ and $b$ . You'll use it when adding fractions with different denominators or finding common periods.

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) guarantees that a system of simultaneous congruences has a unique solution modulo the product of the moduli, provided the moduli are pairwise coprime.

For example, the system $x \equiv 2 \pmod{3}$ , $x \equiv 3 \pmod{5}$ has a unique solution modulo 15 because $\gcd(3, 5) = 1$ . The construction of that solution uses Bézout's identity. CRT has applications in cryptography, coding theory, and fast arithmetic on large numbers.

Multiplicative functions

A function $f(n)$ is multiplicative if $f(ab) = f(a) \cdot f(b)$ whenever $\gcd(a, b) = 1$ . The coprimality condition is what makes the GCD relevant here.

Key examples include:

Euler's totient function $\phi(n)$
Möbius function $\mu(n)$

These functions are important in analytic number theory and appear in formulas involving the Riemann zeta function.

Generalizations and extensions

GCD for polynomials

The GCD concept extends naturally to polynomials. Given two polynomials, their GCD is the highest-degree polynomial that divides both of them.

You compute it using polynomial long division in the same iterative way as the Euclidean algorithm for integers. The degree of the GCD polynomial tells you about the number of common roots. This is useful for simplifying rational functions and solving polynomial equations.

GCD in algebraic structures

The GCD generalizes to unique factorization domains (UFDs), which are algebraic structures where every element factors uniquely into irreducibles (analogous to primes). Examples include the integers, polynomial rings over fields, and certain rings of algebraic integers.

In these structures, the GCD exists and is unique up to multiplication by a unit (the analogue of $\pm 1$ for integers). The specific computational methods depend on the structure you're working in.

Basic definition, Greatest common divisor/Tutorials - Knowino

GCD for more than two numbers

Finding the GCD of three or more numbers works by applying the algorithm repeatedly to pairs:

$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$

The associativity property guarantees this gives the correct result regardless of how you group the pairs. This extends to solving systems of linear Diophantine equations with multiple variables.

Least common divisor

The term "least common divisor" isn't standard in most number theory courses. What's typically meant here is the greatest lower bound in the divisibility lattice, which for positive integers is simply $1$ (since 1 divides everything). The concept becomes more meaningful in lattice theory, where GCD and LCM correspond to the meet and join operations on a divisibility poset. For this course, the important dual to GCD is the LCM, covered above.

Computational aspects

Time complexity analysis

The Euclidean algorithm runs in $O(\log(\min(a, b)))$ steps. The worst case occurs when the inputs are consecutive Fibonacci numbers, which force the maximum number of iterations.
The binary GCD algorithm has similar asymptotic complexity but tends to be faster in practice because bitwise shifts are cheaper than division on hardware.
Iterative implementations use $O(1)$ space. Recursive versions use $O(\log(\min(a, b)))$ stack space.

GCD in computer algebra systems

Software like Mathematica and SageMath treats GCD as a fundamental primitive. Their implementations typically switch between algorithms based on input size: the Euclidean algorithm for moderate numbers, and modular or subresultant techniques for large integers or polynomials. Extended versions compute Bézout coefficients alongside the GCD.

GCD in cryptography

GCD computation is woven into modern cryptographic systems. The RSA algorithm relies on the fact that factoring the product of two large primes is hard, while GCD computations are fast. During RSA key generation, you need to verify that the public exponent $e$ is coprime to $\phi(n)$ , which means checking that $\gcd(e, \phi(n)) = 1$ . Efficient GCD algorithms make these checks practical even for very large numbers.

Historical development

Ancient Greek contributions

The Euclidean algorithm first appeared in Euclid's Elements around 300 BCE, making it one of the oldest algorithms still in common use. Euclid described it in geometric terms, using line segments rather than numbers, and applied it to find common measures and develop the theory of proportions.

Medieval Islamic mathematics

Scholars like al-Khwarizmi (whose name gives us the word "algorithm") further developed GCD-related techniques, integrating them into algebraic and arithmetic treatises. This work helped preserve and extend Greek mathematical knowledge, laying the groundwork for European Renaissance mathematics.

Modern developments

Gauss's Disquisitiones Arithmeticae (1801) gave number theory, including GCD properties, a rigorous modern treatment. In 1967, Josef Stein introduced the binary GCD algorithm, optimized for computer hardware. Today, research continues into parallel and even quantum algorithms for GCD computation, driven by applications in cryptography and large-scale computation.

🧠Thinking Like a Mathematician Unit 3 Review