The Integers: Divisibility, GCD, Primes

⚡ Key Takeaways

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 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.

DefinitionDivisibility

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

1

\quad b = a \cdot k, \qquad a,b,k \in \mathbb{Z}.

Derivation hint: This is a definition — $a\mid 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 \nmid b$ . Note every integer divides $0$ (take $k=0$ ), and $0$ divides only $0$ .

DefinitionThe Division Algorithm

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

2

\quad a = bq + r, \qquad 0 \le r < b.

Derivation hint: Take $q = \lfloor a/b \rfloor$ ; the remainder $r = a - bq$ is forced into $[0,b)$ by the floor. Divisibility is the special case $r = 0$ : $b \mid a$ precisely when the remainder is zero.

DefinitionGreatest Common Divisor

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

3

\quad \gcd(a,b) = \max\{\, d \in \mathbb{Z}^{+} : d \mid a \text{ and } d \mid b \,\}.

Derivation hint: The set of common divisors is finite and nonempty (1 is always a common divisor), so a maximum exists. If $\gcd(a,b) = 1$ , the numbers are called coprime (or relatively prime). The companion quantity, the least common multiple, satisfies:

4

\quad \operatorname{lcm}(a,b) \cdot \gcd(a,b) = |a \cdot b|.

Derivation hint: Compare prime-power exponents — for each prime, $\min$ exponent (gcd) plus $\max$ exponent (lcm) equals the total of the two.

DefinitionPrime 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:

5

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

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

TheoremFundamental 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:

6

\quad n = p_1^{\,e_1} \, p_2^{\,e_2} \cdots p_k^{\,e_k}, \qquad p_1 < p_2 < \dots < p_k,\ \ e_i \ge 1.

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

TheoremBézout's Identity

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

7

\quad ax + by = \gcd(a,b).

Derivation hint: $\gcd(a,b)$ is the smallest positive value of $ax+by$ ; run the Euclidean algorithm backwards to find $x,y$ . In particular, $a$ and $b$ are coprime iff $ax + by = 1$ has an integer solution.

TheoremEuclid's Lemma

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

8

\quad p \mid ab \implies p \mid a \ \text{ or } \ p \mid b.

Derivation hint: If $p \nmid a$ then $\gcd(p,a)=1$ , so by Bézout $1 = px + ay$ ; multiply by $b$ .

ProofUniqueness 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 \cdots p_r = q_1 q_2 \cdots 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 \mid n = q_1 q_2 \cdots q_s$ , repeated use of Euclid's Lemma [8] forces $p_1 \mid 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 \cdots p_r = q_2 \cdots 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. $\blacksquare$

∎

ProofInfinitude 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 \cdots 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 \mid N$ and $p_i \mid p_1 \cdots p_n$ , so $p_i$ divides their difference $N - p_1\cdots p_n = 1$ . But no prime divides $1$ — contradiction. Therefore the list of primes can never be complete; there are infinitely many. $\blacksquare$

∎

mathematician · 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.

🧠 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 \mid b$ means every ingredient of $a$ appears in $b$ at least as many times. $4 \mid 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. $\gcd(12,18) = \gcd(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: $\operatorname{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.

Figure

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

ExampleComputing a GCD two ways

Given: Find $\gcd(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]:

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

\boxed{\gcd(84,60) = 12,\qquad \operatorname{lcm}(84,60) = 420}

ExampleBézout coefficients via back-substitution

Given: Express $\gcd(48,18)$ as $48x + 18y$ .

Step 1 — Forward (Euclidean algorithm):

$48 = 18 \cdot 2 + 12$
$18 = 12 \cdot 1 + 6$
$12 = 6 \cdot 2 + 0$ → $\gcd = 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$ . ✓

\boxed{48(-1) + 18(3) = 6 = \gcd(48,18)}

⚠️ Common mistake

"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 \mid bc$ then $a \mid b$ or $a \mid 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." $\gcd$ is defined for negatives too, since divisibility ignores sign; $\gcd(-12, 18) = 6$ . By convention the GCD itself is taken positive.

Counterexample

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

bc = 12,\qquad 4 \mid 12,\quad \text{yet}\quad 4 \nmid 2 \ \text{ and } \ 4 \nmid 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.

connection

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

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

🔬 Where this appears

⏳ History

- 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+2d,\dots

with

\gcd(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

.

open-problem

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 $\mathbb{Z}$ and similar systems. In the ring $\mathbb{Z}[\sqrt{-5}]$ one has $6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ — two genuinely different factorizations into irreducibles. The Fundamental Theorem is a gift, not a guarantee.

The Integers: Divisibility, GCD, Primes

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also