The number 60 is divisible by 10, and it is the product $4 \cdot 15$. Yet 10 divides neither 4 nor 15. The factors of 10, a 2 and a 5, have been split between the two numbers: the 2 sits in 4 and the 5 in 15. A number that cannot be split this way, because it has no factors to share out, can never divide a product without dividing one of the factors. Those numbers are the primes. Why should this one property of theirs force every integer to factor into primes in essentially one way?
That last claim, the fundamental theorem of arithmetic, is so familiar from school that it can seem to need no proof. Gauss thought otherwise. In the Disquisitiones Arithmeticae he stated it as a theorem, remarking that its uniqueness half "is usually assumed tacitly", and wrongly so (Gauss, 1801, art. 16; our translation).
First we define primes and prove Euclid's lemma, the property above. Then we prove that factorizations exist and that they are unique, and look at a number system in which uniqueness fails. Next we use unique factorization to compute with divisors and to prove an irrationality result. Finally we prove that the primes never run out, find them with a sieve, and count them. The running pair from the previous articles, $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$, serves as the check throughout.
The article completes Arithmetic in the Integers, the first unit of the MTH 532 Abstract Algebra notes, and covers §1.3 of the course text (Hungerford, 2014). It uses the laws of divisibility, Bezout's identity and the cancellation theorem from divisibility and the Euclidean algorithm. It is the course's home for primes and unique factorization in $\mathbb{Z}$, which later units cite and generalize.
Primes
Definition. An integer $p$ is prime if $p \neq 0, \pm 1$ and the only divisors of $p$ are $\pm 1$ and $\pm p$. An integer other than $0, \pm 1$ that is not prime is composite.
The positive primes begin 2, 3, 5, 7, 11, 13. Following the course text, the definition also counts their negatives as primes, so $-7$ is prime. This costs nothing and makes the statements about factorization uniform for negative integers. The integers $1$ and $-1$ are neither prime nor composite: they divide everything, and in the language of rings they are the units of $\mathbb{Z}$, the elements with multiplicative inverses. A composite $n$ has a divisor other than $\pm 1$ and $\pm n$, so it can be written $n = ab$ with $1 < \lvert a \rvert, \lvert b \rvert < \lvert n \rvert$.
A first consequence of the definition is that a prime shares either nothing or everything with any integer.
Lemma. If $p$ is prime and $a$ is any integer, then either $\gcd(p, a) = 1$ or $p \mid a$.
The idea: the gcd is a positive divisor of $p$, and a prime has only two.
Proof. Let $d = \gcd(p, a)$, which is defined because $p \neq 0$. Then $d$ is a positive divisor of $p$, so $d = 1$ or $d = \lvert p \rvert$. In the second case $\lvert p \rvert \mid a$, and hence $p \mid a$ (divisors come in sign pairs). $\blacksquare$
For instance, $\gcd(13, 1729) = 13$, while $\gcd(19, 1001) = 1$.
Euclid's lemma
Theorem (Euclid's lemma and its converse). Let $p$ be an integer with $p \neq 0, \pm 1$. Then $p$ is prime if and only if it has the following property: whenever $p \mid bc$ for integers $b$ and $c$, then $p \mid b$ or $p \mid c$.
The idea: a prime that does not divide $b$ shares nothing with it, so cancellation hands the divisibility to $c$. A composite $ab$ divides the product $ab$ without dividing either smaller factor.
Proof. Suppose $p$ is prime and $p \mid bc$. If $p \mid b$ there is nothing to prove. If $p \nmid b$, the lemma gives $\gcd(p, b) = 1$, and the cancellation theorem of the previous article (if $a \mid bc$ and $\gcd(a, b) = 1$ then $a \mid c$) gives $p \mid c$.
Conversely, suppose $p$ has the property but is not prime. Since $p \neq 0, \pm 1$, it is composite, so $p = ab$ with $1 < \lvert a \rvert < \lvert p \rvert$ and $1 < \lvert b \rvert < \lvert p \rvert$. Then $p \mid ab$, because $ab = p \cdot 1$, and the property gives $p \mid a$ or $p \mid b$. Suppose $p \mid a$. Since $a \neq 0$, the law of divisibility that compares sizes gives $\lvert p \rvert \le \lvert a \rvert$, contradicting $\lvert a \rvert < \lvert p \rvert$. The case $p \mid b$ is the same with $b$ in place of $a$. So $p$ is prime. $\blacksquare$
The forward direction is Proposition 30 of Book VII of Euclid's Elements (Euclid, ed. Joyce, 1996), and it is Theorem 1.5 of the course text. The opening example shows why it fails for composites: $10 \mid 4 \cdot 15$ although $10 \nmid 4$ and $10 \nmid 15$.
The theorem gives two descriptions of the same integers. The definition describes a prime by its divisors: nothing divides it except the trivial divisors. Euclid's lemma describes it by its multiples: whenever it divides a product, it divides a factor. In $\mathbb{Z}$ the two coincide, but in other rings they can differ, and ring theory gives them different names. An element with only trivial factorizations is called irreducible, and an element with the product property is called prime. In that vocabulary, the definition above defines an irreducible integer. The theorem says that in $\mathbb{Z}$ irreducibles and primes are the same thing. The same distinction returns for polynomials and for ideals.
Corollary. If $p$ is prime and $p \mid a_1 a_2 \cdots a_n$, then $p \mid a_i$ for some $i$.
The idea is to split off one factor at a time and apply Euclid's lemma to each split.
Proof. By induction on $n$. For $n = 1$ there is nothing to prove. For $n \ge 2$, write the product as $(a_1 \cdots a_{n-1}) \cdot a_n$. By Euclid's lemma, $p \mid a_n$ or $p \mid a_1 \cdots a_{n-1}$, and in the second case the induction hypothesis gives $p \mid a_i$ for some $i \le n - 1$. $\blacksquare$
Existence of prime factorizations
The fundamental theorem has two halves, and the first says that a factorization exists. A product of primes may have a single factor, so a prime is a product of primes (of one prime).
Theorem (existence). Every integer $n$ other than $0$ and $\pm 1$ is a product of primes.
The idea: a smallest integer without a factorization cannot be prime, so it splits into two smaller integers, and those do have factorizations.
Proof. First let $n > 1$. Suppose, for contradiction, that some integers greater than 1 are not products of primes. By the well-ordering principle there is a least such integer; call it $m$. Then $m$ is not prime, since a prime is a product of one prime. So it is composite: $m = ab$ with $1 < a < m$ and $1 < b < m$, where $a$ and $b$ can be taken positive because $m > 0$. Since $a$ and $b$ are greater than 1 and smaller than $m$, the minimality of $m$ says each is a product of primes, $a = p_1 \cdots p_r$ and $b = q_1 \cdots q_s$. Then $m = p_1 \cdots p_r q_1 \cdots q_s$ is a product of primes, a contradiction. So every integer greater than 1 is a product of primes.
If $n < -1$, then $-n > 1$, so $-n = p_1 p_2 \cdots p_k$ with each $p_i$ prime, and $n = (-p_1) p_2 \cdots p_k$ is a product of primes, since $-p_1$ is prime. $\blacksquare$
In particular, every integer other than $0, \pm 1$ has a prime divisor, which can be taken positive. This is Proposition 31 of Book VII of the Elements, and it is what Euclid's proof that there are infinitely many primes needs.
The proof is a disguised recursive procedure: split $n$ into two smaller factors whenever possible, and continue on each factor until nothing splits. For 1729 the procedure ends with $7 \cdot 13 \cdot 19$, and for 1001 with $7 \cdot 11 \cdot 13$. But nothing in the existence proof says that another order of splitting could not end with different primes.
Check your understanding. Split 1729 first as $91 \cdot 19$, then again as $7 \cdot 247$, and keep splitting. Do the two routes end with the same primes?
They do: $91 = 7 \cdot 13$ and $247 = 13 \cdot 19$, so both routes end at $7 \cdot 13 \cdot 19$. One example proves nothing, though. That every route agrees, for every integer, is the uniqueness theorem.
Uniqueness
Theorem (uniqueness). Suppose $p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$, where all the $p_i$ and $q_j$ are primes. Then $r = s$, and after the $q_j$ are renumbered, $p_i = \pm q_i$ for every $i$.
"Unique" can only mean unique up to the order of the factors and their signs, because $1729 = 7 \cdot 13 \cdot 19 = 19 \cdot (-7) \cdot (-13)$. The theorem says nothing worse can happen.
Here is the plan. The last prime $p_r$ on the left divides the right side, so by Euclid's lemma it matches some $q_j$, up to sign. Cancel the pair and repeat on shorter products, which is an induction on $r$.
Proof. By induction on $r$.
Case $r = 1$. Then $p_1 = q_1 (q_2 \cdots q_s)$, so $q_1$ is a divisor of the prime $p_1$. It is not $\pm 1$, since $q_1$ is prime, so $q_1 = \pm p_1$. If $s \ge 2$, canceling gives $q_2 \cdots q_s = \pm 1$, which is impossible because each $\lvert q_j \rvert \ge 2$ makes the left side at least 2 in absolute value. So $s = 1$ and $p_1 = \pm q_1$.
Inductive step. Let $r \ge 2$ and assume the theorem for products of $r - 1$ primes. The prime $p_r$ divides $p_1 \cdots p_r = q_1 \cdots q_s$, so by the corollary to Euclid's lemma it divides some $q_j$. Renumber the $q$'s so that $p_r \mid q_s$. Since $q_s$ is prime and $p_r \neq \pm 1$, $p_r = \pm q_s$; write $q_s = \varepsilon p_r$ with $\varepsilon = \pm 1$. Then $s \ge 2$, since otherwise $p_1 \cdots p_{r-1} p_r = \varepsilon p_r$ would give $p_1 \cdots p_{r-1} = \varepsilon = \pm 1$, impossible as before. Canceling the nonzero factor $p_r$ from both sides,
$$p_1 \cdots p_{r-1} = (\varepsilon q_1)\, q_2 \cdots q_{s-1}.$$
Here $\varepsilon q_1$ is prime, so the right side is a product of $s - 1$ primes, and the left a product of $r - 1$. By the induction hypothesis, $r - 1 = s - 1$ and, after renumbering $q_1, \ldots, q_{s-1}$, each $p_i$ equals $\pm q_i$ for $i \le r - 1$ (a sign absorbed into $\varepsilon q_1$ changes only the sign). Together with $p_r = \pm q_s$, this proves the theorem for $r$. $\blacksquare$
Combining existence and uniqueness, and collecting equal primes into powers:
Fundamental theorem of arithmetic. Every integer $n > 1$ can be written as
$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \qquad p_1 < p_2 < \cdots < p_k \text{ positive primes}, \quad e_i \ge 1,$$
and the primes $p_i$ and exponents $e_i$ are uniquely determined by $n$.
This is the standard form of $n$; for instance $720 = 2^4 \cdot 3^2 \cdot 5$ and $1729 = 7 \cdot 13 \cdot 19$. A negative integer is $-1$ times the standard form of its absolute value. Write $v_p(n)$ for the exponent of the prime $p$ in $n$, zero if $p$ does not appear. The theorem says that $n$ is determined by the list of numbers $v_p(n)$. Multiplication adds them, $v_p(mn) = v_p(m) + v_p(n)$, because multiplying standard forms collects the powers of each prime.
The proof of uniqueness used Euclid's lemma at exactly one point, to match $p_r$ with some $q_j$. The chain behind that step runs all the way back through the unit:
- Euclid's lemma came from the cancellation theorem;
- cancellation came from Bezout's identity;
- Bezout's identity came from the Euclidean algorithm;
- and the Euclidean algorithm came from the division algorithm.
That chain of dependence is the reason the course proves these results in this order.
Why uniqueness needs a proof
Is all this care really needed? Uniqueness is a property of $\mathbb{Z}$, not a law of logic, and it fails in number systems that look very similar. Consider the even integers $2\mathbb{Z} = \{\ldots, -4, -2, 0, 2, 4, \ldots\}$, which are closed under addition and multiplication but have no 1. Call a positive even number an E-prime if it is not the product of two even numbers. A product of two even numbers is a multiple of 4. So the E-primes are exactly the numbers $2 \times$ odd: 2, 6, 10, 14, 18, 22, 26, 30, 34, and so on. Every positive even number factors into E-primes, by the same well-ordering argument as before. But
$$60 = 2 \cdot 30 = 6 \cdot 10,$$
where 2, 30, 6 and 10 are all E-primes, and 180 has three different factorizations, $2 \cdot 90 = 6 \cdot 30 = 10 \cdot 18$, as the script for this article finds by exhaustive search.
Check your understanding. Does 36 have only one factorization into E-primes?
It has two, $36 = 2 \cdot 18 = 6 \cdot 6$, and the script finds that it is the smallest positive even number with more than one.
The uniqueness proof breaks where Euclid's lemma is used. In $2\mathbb{Z}$, the E-prime 6 "divides" $60 = 2 \cdot 30$ (because $60 = 6 \cdot 10$ with 10 even), but it divides neither 2 nor 30 within $2\mathbb{Z}$, since $30 = 6 \cdot 5$ and 5 is not even. In $\mathbb{Z}$, Euclid's lemma came from Bezout's identity, which writes 1 as a combination of two numbers. $2\mathbb{Z}$ has no 1, so the chain of results never starts. Rings in which factorizations are unique are called unique factorization domains. Later articles show that rings of polynomials over a field are among them, for the same reason as $\mathbb{Z}$: they have a division algorithm.
Reading divisibility from exponents
Uniqueness turns questions about divisibility into questions about exponents.
Proposition. Let $m$ and $n$ be positive integers. Then $m \mid n$ if and only if $v_p(m) \le v_p(n)$ for every prime $p$.
The idea: $n = mk$ adds the exponents of $k$ to those of $m$, and uniqueness lets us read exponents off unambiguously.
Proof. If $v_p(m) \le v_p(n)$ for all $p$, then $k = \prod_p p^{\,v_p(n) - v_p(m)}$ is a positive integer (a finite product, since only finitely many exponents are nonzero) with $mk = n$. Conversely, if $n = mk$, then $k$ is a positive integer and $v_p(n) = v_p(m) + v_p(k) \ge v_p(m)$ for every $p$, by uniqueness of the factorization of $n$. $\blacksquare$
Three consequences follow at once.
Divisors. The positive divisors of $n = p_1^{e_1} \cdots p_k^{e_k}$ are the numbers $p_1^{f_1} \cdots p_k^{f_k}$ with $0 \le f_i \le e_i$, and different exponent choices give different divisors. Each $f_i$ can be chosen in $e_i + 1$ ways, so $n$ has $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$ positive divisors. For $720 = 2^4 \cdot 3^2 \cdot 5$ that is $5 \cdot 3 \cdot 2 = 30$, which the script confirms by listing them. For $1729 = 7 \cdot 13 \cdot 19$ it is $2 \cdot 2 \cdot 2 = 8$, the eight divisors listed at the start of the previous article.
Greatest common divisor. A positive common divisor of $m$ and $n$ has, for each $p$, exponent at most $\min(v_p(m), v_p(n))$. The number with exactly those exponents is a common divisor divisible by all the others. By the characterization of the gcd in the previous article,
$$\gcd(m, n) = \prod_p p^{\min(v_p(m),\, v_p(n))}.$$
Least common multiple. The least common multiple $\operatorname{lcm}(m, n)$ is the smallest positive integer divisible by both $m$ and $n$. A positive common multiple has, for each $p$, exponent at least $\max(v_p(m), v_p(n))$. The number $\prod_p p^{\max(v_p(m), v_p(n))}$ is itself a common multiple that divides every other one, so it is the smallest:
$$\operatorname{lcm}(m, n) = \prod_p p^{\max(v_p(m),\, v_p(n))}.$$
Since $\min(e, f) + \max(e, f) = e + f$ for any two numbers, multiplying the two formulas gives
$$\gcd(m, n) \cdot \operatorname{lcm}(m, n) = mn.$$
For the running pair of the previous article, $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$:
| prime | 7 | 11 | 13 | 19 |
|---|---|---|---|---|
| exponent in 1729 | 1 | 0 | 1 | 1 |
| exponent in 1001 | 1 | 1 | 1 | 0 |
| min (gcd) | 1 | 0 | 1 | 0 |
| max (lcm) | 1 | 1 | 1 | 1 |
so $\gcd = 7 \cdot 13 = 91$, matching the Euclidean algorithm, and $\operatorname{lcm} = 7 \cdot 11 \cdot 13 \cdot 19 = 19019$. The check: $91 \cdot 19019 = 1{,}730{,}729 = 1729 \cdot 1001$.
The exponent formulas are convenient for numbers whose factorizations are known, but they are not a good way to compute a gcd. They require factoring both numbers, and no efficient method of factoring large integers is known. The Euclidean algorithm needs no factorization and runs in a number of steps proportional to the number of digits. The gap between these two tasks, easy gcds and hard factoring, is what the RSA cryptosystem is built on.
An irrationality proof
Proposition. $\log_2 3$ is irrational.
The idea: a fraction $m/n$ equal to $\log_2 3$ would make a power of 2 equal to a power of 3, one integer with two different prime factorizations.
Proof. Since $3 > 2 > 1$, $\log_2 3$ is positive. Suppose $\log_2 3 = m/n$ with $m$ and $n$ positive integers. Then $2^{m/n} = 3$, and raising both sides to the power $n$ gives $2^m = 3^n$. This integer is greater than 1, and $2^m$ and $3^n$ are two factorizations of it into positive primes. One uses only the prime 2 and the other only the prime 3, which contradicts uniqueness. $\blacksquare$
The value is $\log_2 3 = 1.58496\ldots$, and no fraction equals it exactly: no power of 2 is a power of 3. The classical proof that $\sqrt{2}$ is irrational is another argument of the same kind, comparing the exponents of a prime on the two sides of an equation between integers.
Check your understanding. Does the same argument prove that $\log_4 8$ is irrational?
It does not: $\log_4 8 = 3/2$. The equation $4^m = 8^n$ is $2^{2m} = 2^{3n}$, with the same prime on both sides, and $4^3 = 8^2 = 64$. The proof needed two different primes.
There are infinitely many primes
Every integer is built from primes. How many primes are there to build from?
Theorem (Euclid). For any finite list of positive primes $p_1, \ldots, p_k$, there is a prime not on the list. Hence there are infinitely many primes.
The idea: multiply the listed primes and add 1. The result leaves remainder 1 on division by every prime on the list, so its prime factors are new.
Proof. Let $N = p_1 p_2 \cdots p_k + 1$. Then $N > 1$, so by the existence theorem $N$ has a positive prime divisor $q$. If $q$ were one of the $p_i$, it would divide both $N$ and $p_1 \cdots p_k$, hence their difference, which is 1. No prime divides 1, so $q$ is not on the list. $\blacksquare$
This is Proposition 20 of Book IX of the Elements, which Euclid states as "prime numbers are more than any assigned multitude of prime numbers" (Euclid, ed. Joyce, 1996). The argument in the Elements never supposes that the primes are finite in number: from any given primes it constructs another. It is often retold as a proof by contradiction that starts from a supposed list of all the primes. That is a valid variant, but not Euclid's form of the argument.
Check your understanding. Is the product of the first $k$ primes plus 1 always prime? Try $k = 6$: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$.
It is not: $30031 = 59 \cdot 509$. The proof claims only that the prime factors of $N$ are new, and 59 and 509 are. From the list $3, 5, 7$, the construction gives $N = 106 = 2 \cdot 53$, which produces two primes not on the list. Starting from the first seven primes, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 + 1 = 510511 = 19 \cdot 97 \cdot 277$, which is composite.
Finding primes
There are infinitely many primes, but how do we recognize one?
Trial division
To decide whether $n$ is prime, it is enough to try divisors up to $\sqrt{n}$.
Theorem. Let $n > 1$. If no prime $p$ with $p \le \sqrt{n}$ divides $n$, then $n$ is prime.
The idea: if $n = ab$, the two factors cannot both exceed $\sqrt{n}$, so the smaller one, or a prime dividing it, turns up early.
Proof. Suppose $n$ is composite: $n = ab$ with $1 < a \le b < n$ (order the two factors so that $a \le b$). Then $a^2 \le ab = n$, so $a \le \sqrt{n}$. The integer $a > 1$ has a prime divisor $p$, which satisfies $p \le a \le \sqrt{n}$ and, by transitivity of divisibility, divides $n$. So a composite $n$ always has a prime divisor at most $\sqrt{n}$, which is the contrapositive of the theorem. $\blacksquare$
Since $\sqrt{1001} \approx 31.64$, testing 1001 means trying the 11 primes up to 31; the first one tried that works is 7, and $1001 = 7 \cdot 143$. For $1013$, with $\sqrt{1013} \approx 31.83$, none of the same 11 primes divides it, so 1013 is prime. Trial division is fine for numbers of a dozen digits and useless for numbers of a hundred. Testing those for primality relies instead on methods built on Fermat's little theorem.
Check your understanding. No prime below 31 divides 961. Is 961 prime?
No: $961 = 31^2$. The theorem says "$p \le \sqrt{n}$", and here $\sqrt{961} = 31$ exactly. Stopping one prime short of the square root would wrongly call 961 prime.
The sieve of Eratosthenes
To list all primes up to a bound $N$, it is faster to cross out composites than to test numbers one at a time. Write the numbers from 2 to $N$. The first number not crossed out is prime; cross out its multiples, then move to the next number not crossed out, and repeat. By the trial division theorem, every composite up to $N$ has a prime factor at most $\sqrt{N}$. So the process can stop once the primes reach $\sqrt{N}$, and whatever is left is prime. Crossing out for a prime $p$ can start at $p^2$, since any smaller multiple of $p$ has a smaller prime factor and has already been removed. Judson (2026, §2.2.3) notes that the method, the sieve of Eratosthenes, goes back to antiquity.
Up to 120, the four sieving primes cross out 59, 19, 7 and 4 numbers respectively. The $59 + 19 + 7 + 4 = 89$ composites, the 30 primes and the number 1 account for all 120 numbers.
Check your understanding. Which four numbers up to 120 does 7 cross out first?
They are 49, 77, 91 and 119: the multiples of 7 from $7^2$ on with no prime factor smaller than 7. The third is the running example's gcd, $91 = 7 \cdot 13$.
How the primes thin out
Euclid's theorem says the primes never stop, and the sieve shows them becoming sparser. Of the numbers up to 100, 25 are prime, but only 5 of the 20 numbers from 101 to 120 are. Writing $\pi(x)$ for the number of positive primes up to $x$, the script for this article counts:
| $x$ | $\pi(x)$ | $x / \ln x$ | ratio |
|---|---|---|---|
| 10 | 4 | 4.3 | 0.921 |
| 100 | 25 | 21.7 | 1.151 |
| 1,000 | 168 | 144.8 | 1.161 |
| 10,000 | 1,229 | 1,085.7 | 1.132 |
| 100,000 | 9,592 | 8,685.9 | 1.104 |
| 1,000,000 | 78,498 | 72,382.4 | 1.084 |
The prime number theorem states that the ratio $\pi(x) / (x / \ln x)$ tends to 1 as $x$ grows: near a large number $x$, roughly one integer in $\ln x$ is prime. Hadamard and, independently, de la Vallée Poussin proved it in 1896. From 1,000 on, the table shows the ratio falling toward 1, slowly. The proof uses complex analysis and lies outside this course.
Simple questions about primes remain open. Goldbach's conjecture, from a 1742 letter to Euler, says that every even integer greater than 2 is the sum of two primes. It has been verified for all even numbers up to $4 \times 10^{18}$ but not proved (Judson, 2026, §2.2.3). Whether there are infinitely many twin primes, pairs such as 41 and 43 that differ by 2, is also unknown.
Where it leads
- Primes govern modular arithmetic. $\mathbb{Z}_n$ is a field exactly when $n$ is prime, because only then does every nonzero remainder have an inverse (Units and Zero Divisors in the Integers Modulo n, Integral Domains and Fields).
- Polynomials have their own primes, the irreducible polynomials, and their own unique factorization (Irreducible Polynomials and Roots), which is the source of the finite fields beyond $\mathbb{Z}_p$.
- The distinction between irreducible and prime elements, which coincide in $\mathbb{Z}$, becomes the distinction between kinds of ideals (Ideals and Principal Ideal Domains).
- The RSA cryptosystem multiplies two large primes, which is easy, and depends on the difficulty of recovering them from the product.
What we have learned
Every integer other than 0 and $\pm 1$ factors into primes, uniquely up to order and signs. Existence needed only well-ordering; uniqueness needed Euclid's lemma, and through it the whole chain of the unit. The even integers show that the chain is not a formality. With uniqueness, gcds and lcms can be read from exponents, as $\gcd(1729, 1001) = 7 \cdot 13$ was.
The unit began by sorting integers by their remainders. The next unit makes that sorting precise and calculates with the sorted classes, starting from Equivalence Relations and Partitions, the general idea of treating different objects as the same.
References
- Euclid. Elements, Book VII, Propositions 30 and 31, and Book IX, Proposition 20. In D. E. Joyce (ed.), Euclid's Elements (1996), Clark University, online at mathcs.clarku.edu/~djoyce/elements/. record · 2 pages
- Gauss, C. F. (1801). Disquisitiones Arithmeticae, article 16. Leipzig: Gerhard Fleischer. Article 16 states that a composite number can be resolved into prime factors in only one way. record · 3 pages
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §1.3. Brooks/Cole, Cengage Learning. The course text: Euclid's lemma and its converse (Theorem 1.5 and Corollary 1.6), existence and uniqueness of factorization (Theorems 1.7 and 1.8, Corollary 1.9), and trial division (Theorem 1.10). record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §2.2.2 (prime numbers) and §2.2.3 (historical note). Free online at judsonbooks.org. record · 44 pages