The Integers: Divisibility, GCD, Primes

One-line statement: The integers form a system where every number factors uniquely into primes, and divisibility, the greatest common divisor (GCD), and primality are the foundational tools for studying that structure. Key result in words: Every integer greater than 1 is either prime or can be written as a product of primes in exactly one way (up to order) — the Fundamental Theorem of Arithmetic. Where it applies: Number theory, cryptography (RSA), error-correcting codes, computer algebra, scheduling/cyclic problems, music theory. Who/when: Studied since Euclid (c. 300 BCE); systematized by Gauss (1801) in Disquisitiones Arithmeticae.

The integers $Z = {\dots, - 2, - 1, 0, 1, 2, \dots}$ are the whole numbers together with their negatives. Divisibility asks whether one integer fits evenly into another, and from this single relation grows the whole edifice of elementary number theory: the greatest common divisor measures the largest shared factor of two numbers, while prime numbers are the indivisible atoms from which every other integer is built. The central, almost miraculous fact is that this factorization into primes is unique — a result so fundamental it is named the Fundamental Theorem of Arithmetic. A surprising fact: although there are infinitely many primes (proved by Euclid over two thousand years ago), no one has ever found a simple formula that generates all of them, and their detailed distribution remains one of mathematics' deepest mysteries.

The Core Insight

Multiplication of integers can be "reversed" by asking what divides what. The primes are exactly the numbers that cannot be broken down further, and every integer is a unique product of primes. This means questions about integers — their common factors, their multiples, their structure — can always be reduced to questions about primes. The GCD and the Euclidean algorithm give us a fast, mechanical way to extract that shared prime content without ever having to factor.

Formal Statement

Divisibility

Let $a, b \in Z$ . We say $a$ divides $b$ , written $a ∣ b$ , if there exists an integer $k$ such that:

b = a \cdot k, a, b, k \in Z .

⟳This is a definition —

a ∣ b

literally means "

b

is an integer multiple of

a

Here $a$ is a divisor (or factor) of $b$ , and $b$ is a multiple of $a$ . If no such $k$ exists, we write $a ∤ b$ . Note every integer divides $0$ (take $k = 0$ ), and $0$ divides only $0$ .

The Division Algorithm

For any integers $a$ and $b$ with $b > 0$ , there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

a = b q + r, 0 \leq r < b .

⟳Take

q = ⌊ a / b ⌋

; the remainder

r = a - b q

is forced into

[0, b)

by the floor.

Divisibility is the special case $r = 0$ : $b ∣ a$ precisely when the remainder is zero.

Greatest Common Divisor

The greatest common divisor of integers $a$ and $b$ (not both zero), written $g cd (a, b)$ , is the largest positive integer $d$ dividing both:

g cd (a, b) = max {d \in Z^{+} : d ∣ a and d ∣ b} .

⟳The set of common divisors is finite and nonempty (1 is always a common divisor), so a maximum exists.

If $g cd (a, b) = 1$ , the numbers are called coprime (or relatively prime). The companion quantity, the least common multiple, satisfies:

lcm (a, b) \cdot g cd (a, b) = ∣ a \cdot b ∣.

⟳Compare prime-power exponents — for each prime,

min

exponent (gcd) plus

max

exponent (lcm) equals the total of the two.

Prime and Composite

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ itself. An integer $n > 1$ that is not prime is composite. The number $1$ is a unit — by convention neither prime nor composite. The primes begin:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots

⟳List integers; strike out those with a proper divisor (the Sieve of Eratosthenes).

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as a product of primes, and this factorization is unique apart from the order of the factors:

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}, p_{1} < p_{2} < \dots < p_{k}, e_{i} \geq 1.

⟳Existence by strong induction (split any composite); uniqueness from Euclid's Lemma below.

Bézout's Identity

For any integers $a, b$ (not both zero), there exist integers $x, y$ such that:

a x + b y = g cd (a, b) .

⟳

g cd (a, b)

is the smallest positive value of

a x + b y

; run the Euclidean algorithm backwards to find

x, y

In particular, $a$ and $b$ are coprime iff $a x + b y = 1$ has an integer solution.

Euclid's Lemma

If a prime $p$ divides a product $ab$ , then $p$ divides at least one of the factors:

p ∣ ab ⟹ p ∣ a or p ∣ b .

⟳If

p ∤ a

then

g cd (p, a) = 1

, so by Bézout

1 = p x + a y

; multiply by

b

Why It Holds / Derivation

Uniqueness of Prime Factorization

We prove the uniqueness half of the Fundamental Theorem; existence is a routine induction.

Step 1 — Setup. Suppose, for contradiction, some integer has two genuinely different prime factorizations. By the well-ordering principle, let

n

be the smallest such integer:

n = p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s},

where each

p_{i}, q_{j}

is prime, and the two lists are not the same (up to reordering). Step 2 — Apply Euclid's Lemma. Since

p_{1} ∣ n = q_{1} q_{2} \dots q_{s}

, repeated use of Euclid's Lemma [8] forces

p_{1} ∣ q_{j}

for some

j

. But

q_{j}

is prime, so its only divisors are

1

and itself; hence

p_{1} = q_{j}

. Step 3 — Cancel. Reorder so that

q_{j} = q_{1}

, and divide both factorizations by

p_{1} = q_{1}

\frac{n}{p _{1}} = p_{2} \dots p_{r} = q_{2} \dots q_{s} .

Step 4 — Contradiction. The number

n / p_{1}

is smaller than

n

, yet it still has two distinct factorizations. This contradicts the minimality of

n

. Therefore no such

n

exists, and prime factorization is unique.

■

Infinitude of Primes — Euclid's Argument

Step 1. Suppose there were only finitely many primes:

p_{1}, p_{2}, \dots, p_{n}

. Step 2. Form the number

N = p_{1} p_{2} \dots p_{n} + 1

. Step 3.

N > 1

, so by the Fundamental Theorem it has some prime divisor

p

. That

p

must be one of our list, say

p = p_{i}

. Step 4. Then

p_{i} ∣ N

and

p_{i} ∣ p_{1} \dots p_{n}

, so

p_{i}

divides their difference

N - p_{1} \dots p_{n} = 1

. But no prime divides

1

— contradiction.

Therefore the list of primes can never be complete; there are infinitely many. $■$

Euclid of Alexandria | c. 300 BCE

Euclid compiled the Elements, the most influential mathematics text in history. Books VII–IX develop number theory from scratch: the Euclidean algorithm for GCD appears as Proposition VII.2, Euclid's Lemma as VII.30, and the infinitude of primes as the celebrated IX.20. His method — proving general truths by rigorous deduction rather than checking examples — set the template for all later mathematics. Remarkably, the algorithm he describes for computing the GCD is still, in essence, the fastest practical method used by computers today, over two millennia later.

Building Intuition

Think of each integer as built from a "recipe" of prime ingredients. The number $12 = 2^{2} \cdot 3$ means "two pinches of 2 and one pinch of 3." With this picture:

Divisibility is containment of recipes: $a ∣ b$ means every ingredient of $a$ appears in $b$ at least as many times. $4 ∣ 12$ because $4 = 2^{2}$ and $12$ has two $2$ 's to spare.
GCD is the overlap of two recipes — take the minimum count of each shared prime. $g cd (12, 18) = g cd (2^{2} \cdot 3, 2 \cdot 3^{2}) = 2^{1} \cdot 3^{1} = 6$ .
LCM is the union — take the maximum count of each prime: $lcm (12, 18) = 2^{2} \cdot 3^{2} = 36$ .

The primes are the ingredients that cannot themselves be made from smaller ingredients. The Euclidean algorithm is a shortcut that finds the overlap without ever opening the recipe boxes — it works purely by repeated division.

The Euclidean algorithm computing gcd(48, 18) by repeated division

Worked Examples

Computing a GCD two ways

Given: Find

g cd (84, 60)

. Method A — Prime factorization.

$84 = 2^{2} \cdot 3 \cdot 7$
$60 = 2^{2} \cdot 3 \cdot 5$
Shared primes with minimum exponents: $2^{2} \cdot 3 = 12$ .

Method B — Euclidean algorithm.

$84 = 60 \cdot 1 + 24$
$60 = 24 \cdot 2 + 12$
$24 = 12 \cdot 2 + 0$ → stop. Last nonzero remainder is $12$ .

Both agree. We can also find the LCM via equation [4]:

lcm (84, 60) = \frac{84 \cdot 60}{12} = \frac{5040}{12} = 420.

g cd (84, 60) = 12, lcm (84, 60) = 420

Bézout coefficients via back-substitution

Given: Express

g cd (48, 18)

48 x + 18 y

. Step 1 — Forward (Euclidean algorithm):

$48 = 18 \cdot 2 + 12$
$18 = 12 \cdot 1 + 6$
$12 = 6 \cdot 2 + 0$ → $g cd = 6$ .

Step 2 — Back-substitute. Start from the line giving the GCD:

6 = 18 - 12 \cdot 1.

Replace

12

using

12 = 48 - 18 \cdot 2

6 = 18 - (48 - 18 \cdot 2) \cdot 1 = 18 - 48 + 36 = 3 \cdot 18 - 1 \cdot 48.

Step 3 — Read off coefficients:

x = - 1, y = 3

. Check:

48 (- 1) + 18 (3) = - 48 + 54 = 6

. ✓

48 (- 1) + 18 (3) = 6 = g cd (48, 18)

Common Misconceptions

"1 is prime." It is not. Including

1

as prime would destroy the uniqueness in the Fundamental Theorem, since you could insert any number of

1

's:

6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3

. The number

1

is a unit, sitting in its own category. "If $a ∣ b c$ then $a ∣ b$ or $a ∣ c$ ." This is true only when

a

is prime (Euclid's Lemma). For composite

a

it can fail. "GCD only makes sense for positive numbers."

g cd

is defined for negatives too, since divisibility ignores sign;

g cd (- 12, 18) = 6

. By convention the GCD itself is taken positive.

For the failed divisibility claim above, take $a = 4$ , $b = 2$ , $c = 6$ :

b c = 12, 4 ∣ 12, yet 4 ∤ 2 and 4 ∤ 6.

Here

4

is composite, so Euclid's Lemma does not apply — the factor of

4

is "split across"

b

and

c

(one factor of

2

in each). This is exactly why primality is the crucial hypothesis.

Connections

Divisibility and the GCD are the gateway to several neighbouring areas:

Modular Arithmetic is built directly on the Division Algorithm — remainders modulo $n$ partition $Z$ into classes, and coprimality (GCD $= 1$ ) is exactly the condition for an element to have a multiplicative inverse mod $n$ .
Linear Diophantine Equations $a x + b y = c$ have integer solutions if and only if $g cd (a, b) ∣ c$ — a direct consequence of Bézout's Identity [7].
Rational Numbers in lowest terms are precisely fractions $a / b$ with $g cd (a, b) = 1$ ; the GCD is what "reduces" a fraction.
Abstract Algebra and Rings generalizes $Z$ to unique factorization domains, asking which other number systems preserve the Fundamental Theorem (surprisingly, not all do).

Real-World Applications

RSA cryptography. Internet security rests on the difficulty of factoring a large composite $n = pq$ into its two prime factors. Encryption uses GCD/coprimality conditions and modular inverses computed by the extended Euclidean algorithm.
Reducing fractions in software. Computer algebra systems (Mathematica, SymPy) and even spreadsheet engines call the Euclidean algorithm constantly to keep rationals in lowest terms.
Gear ratios and engineering. When two gears with $a$ and $b$ teeth mesh, the pattern repeats after $lcm (a, b)$ teeth; choosing coprime tooth counts ( $g cd = 1$ ) spreads wear evenly — the "hunting tooth" design.
Error-correcting codes. Cyclic redundancy checks (CRCs) and Reed–Solomon codes used in CDs, QR codes, and deep-space transmission rely on divisibility of polynomials, the exact analogue of integer divisibility.
Cryptographic hashing & random number generators. Linear congruential generators require carefully chosen coprime parameters to achieve full period.
Music theory. The 12-tone scale and rhythmic cycles (polyrhythms like 3-against-4) are governed by LCM and GCD of period lengths.
Scheduling and calendars. Determining when periodic events coincide (planetary alignments, bus timetables, the Metonic cycle relating lunar and solar years) is an LCM computation.

Historical Development

c. 300 BCE — Euclid's Elements. Books VII–IX present the Euclidean algorithm, Euclid's Lemma, and the proof that primes are infinite. The foundation is laid.
c. 250 CE — Diophantus of Alexandria. His Arithmetica studies integer and rational solutions of equations, giving the name to "Diophantine" problems.
c. 1000 CE — Islamic mathematicians. Ibn al-Haytham and others investigate perfect numbers and what is now called Wilson's theorem.
1640 — Fermat. States his "Little Theorem" and the two-squares theorem, igniting modern number theory through his famous marginal notes.
1742 — Goldbach's letter to Euler. Conjectures every even number $> 2$ is a sum of two primes — still unproven.
1801 — Gauss, Disquisitiones Arithmeticae. Gives the first fully rigorous statement and proof of the Fundamental Theorem of Arithmetic and systematizes congruences. Modern number theory begins.
1837 — Dirichlet. Proves infinitely many primes occur in every arithmetic progression $a, a + d, a + 2 d, \dots$ with $g cd (a, d) = 1$ .
1859 — Riemann. Connects the distribution of primes to the zeros of the zeta function, formulating the Riemann Hypothesis.
1896 — Hadamard & de la Vallée Poussin. Independently prove the Prime Number Theorem, describing how primes thin out: roughly $n / ln n$ primes below $n$ .

Subtleties & Limits

The atoms (primes) are understood individually, but their collective behaviour hides famous unsolved problems:

Goldbach's Conjecture (1742): Is every even integer $> 2$ the sum of two primes? Verified to enormous bounds by computer, still unproven.
Twin Prime Conjecture: Are there infinitely many primes $p$ such that $p + 2$ is also prime ( $3, 5$ ; $11, 13$ ; $17, 19$ ; …)? Yitang Zhang's 2013 breakthrough proved infinitely many prime pairs differ by some bounded gap, but the gap-2 case remains open.
The Riemann Hypothesis: A conjecture about the zeta function that, if true, would pin down the distribution of primes with astonishing precision. It is one of the Clay Millennium Prize Problems.

Also worth noting: unique factorization is special to $Z$ and similar systems. In the ring $Z [- 5]$ one has $6 = 2 \cdot 3 = (1 + - 5) (1 - - 5)$ — two genuinely different factorizations into irreducibles. The Fundamental Theorem is a gift, not a guarantee.