Back to the on-screen lesson ·
Euclid's lemma out of Bézout in four lines, the fundamental theorem it makes true, and what goes wrong in a system where it fails.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to prove Euclid's lemma from Bézout's identity, prove the existence and the uniqueness halves of the fundamental theorem of arithmetic separately, read divisibility, greatest common divisors and least common multiples off two factorisations as comparisons of exponents, and give an example of a number system in which factorisation is not unique.
Lesson 3 ended with a pattern: because $\gcd(a, b) = 1$ there are integers with $ax + by = 1$, and multiplying that identity by something settles a divisibility question.
That pattern, applied once, gives Euclid's lemma — and Euclid's lemma is the whole of this lesson. Factorising numbers is arithmetic you have done for years; what you have not seen is any reason the answer should be the only one. The reason is Bézout.
A prime is an integer above $1$ whose only positive divisors are $1$ and itself. An integer above $1$ that is not prime is composite. $1$ is neither, by decision rather than by accident — see the misconceptions below.
A prime factorisation of $n$ is an expression $n = p_1^{e_1} \cdots p_k^{e_k}$ with the $p_i$ distinct primes and each $e_i \ge 1$. The exponent $e_i$ is the multiplicity of $p_i$ in $n$.
It is often convenient to write $n = \prod_p p^{v_p(n)}$ over all primes, with $v_p(n) = 0$ for all but finitely many. $v_p$ is the $p$-adic valuation, and it turns statements about divisibility into inequalities between exponents.
Euclid's lemma. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
Proof: suppose $p \nmid a$. The only divisors of $p$ are $1$ and $p$, and $p$ does not divide $a$, so $\gcd(p, a) = 1$. Bézout gives $px + ay = 1$; multiply by $b$ to get $pbx + aby = b$. Then $p$ divides the first term, and divides $ab$ hence the second, so $p \mid b$.
Four lines, and every one of them needs a hypothesis: primality gives the gcd, the gcd gives the identity, the identity gives the divisibility.
Fundamental theorem of arithmetic. Every integer $n > 1$ is a product of primes, and the product is unique up to the order of the factors.
Existence is strong induction: $n$ is prime, or $n = ab$ with both factors smaller and above $1$, and each of those factors is a product of primes. Uniqueness is Euclid's lemma applied repeatedly, cancelling a matched pair each time.
Existence is the easy half and uniqueness is the half that matters. There are number systems where factorisations exist and are not unique — in $\mathbb{Z}[\sqrt{-5}]$, $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ with all four factors irreducible — and in such a system nearly every argument in this course breaks. What holds it together here is that the integers have a division algorithm, which gives Bézout, which gives Euclid's lemma.
What it buys. Writing $a = \prod p^{\alpha_p}$ and $b = \prod p^{\beta_p}$: $a \mid b$ exactly when $\alpha_p \le \beta_p$ for every $p$; $\gcd$ takes the minimum exponent and $\operatorname{lcm}$ the maximum, so $\gcd \cdot \operatorname{lcm} = ab$; and $\sqrt{2}$ is irrational, because $a^2 = 2b^2$ would put an even exponent of $2$ on one side and an odd one on the other.
Another way: steps
Another way: example
$360 = 2^3 \cdot 3^2 \cdot 5$ and $84 = 2^2 \cdot 3 \cdot 7$. Minimum exponents: $2^2 \cdot 3 = 12$, so $\gcd = 12$. Maximum exponents: $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$, so $\operatorname{lcm} = 2520$. And $12 \cdot 2520 = 30240 = 360 \cdot 84$, as the min-plus-max identity requires.
The fundamental theorem is taught early enough that it usually arrives without an argument, and it is worth seeing what would go wrong without one.
Consider the set $H = \{1, 5, 9, 13, 17, \ldots\}$ of numbers that are $1$ modulo $4$. It is closed under multiplication, so it has its own arithmetic. Call an element of $H$ irreducible if it is not a product of two smaller elements of $H$. Then $9$, $21$, $33$ and $77$ are all irreducible in $H$ — and $$693 = 9 \cdot 77 = 21 \cdot 33.$$ Two genuinely different factorisations into irreducibles, in a perfectly reasonable system. Nothing about the idea of factorisation forces uniqueness; a specific theorem does, and the specific theorem is Euclid's lemma. In $H$ it fails: $9 \mid 21 \cdot 33$ while $9$ divides neither.
This also settles the status of $1$. If $1$ were prime, $12 = 2^2 \cdot 3 = 1 \cdot 2^2 \cdot 3 = 1^2 \cdot 2^2 \cdot 3$ would be three factorisations, and the theorem would be false as stated. Excluding $1$ is not a convention about a borderline case; it is what makes the sentence true. The same consideration is why the empty product is taken to be $1$: it lets the theorem cover $n = 1$ with no special case.
The modern statement of the underlying idea separates two words that agree for integers and disagree elsewhere. An element is irreducible when it has no non-trivial factorisation, and prime when it satisfies Euclid's lemma. Prime always implies irreducible; the converse is what the integers have and $H$ does not.
Using Euclid's lemma for a composite. $6 \mid 4 \cdot 3$, and $6$ divides neither. The lemma is about primes, and every argument that quietly applies it to a composite divisor is unsound even when its conclusion happens to be true.
Treating existence as the theorem. That every number factorises is easy and was never in doubt. The content is that the factorisation is the only one, and that is what a proof has to establish.
Trial division past the square root. If no prime up to $\sqrt n$ divides $n$, then $n$ is prime; continuing is wasted work, because a composite has a factor on each side of $\sqrt n$.
Reading $\gcd \cdot \operatorname{lcm} = ab$ as a coincidence. It is the identity $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$, one prime at a time. It also fails for three numbers, where the naive extension is simply false.
Believing factorisation is a practical method. For gcds it is not; Euclid's algorithm is. For numbers of a few hundred digits, no known method factorises at all, which is the assumption a great deal of cryptography rests on.
Suppose $\sqrt{2} = a/b$ with $a, b$ positive integers. Then $a^2 = 2b^2$.
Clear the fraction rather than arguing about lowest terms.
In $a^2$ the exponent of $2$ is even, being twice its exponent in $a$. In $2b^2$ it is odd, being twice its exponent in $b$ plus one.
Unique factorisation is what lets the two sides be compared prime by prime.
An even number cannot equal an odd one, so no such $a, b$ exist. The same argument shows $\sqrt{n}$ is irrational whenever $n$ is not a perfect square.
Nothing about the argument was special to $2$.
Claim: if $p$ is prime and $p \mid a^2$, then $p \mid a$. Write $a^2 = a \cdot a$.
A square is a product like any other.
By Euclid's lemma $p$ divides one of the two factors, and both factors are $a$.
One application, and the case split collapses.
So $p \mid a$. The composite version is false: $4 \mid 6^2$ and $4 \nmid 6$, which is worth checking against, because the claim feels as though it should hold for any divisor.
The counterexample is what keeps the hypothesis visible.
Take any prime $p$ and compare exponents: $v_p(a) + v_p(b) = v_p(ab)$, which is even.
Unique factorisation turns the claim into arithmetic on exponents.
Coprimality means at most one of $v_p(a)$, $v_p(b)$ is non-zero, so one of the two is $0$ and the other is the whole even sum.
This is where the hypothesis enters, and it is the only place.
So every exponent in $a$ is even, and likewise in $b$, which is what it means for each to be a perfect square.
Factorise $40$ into primes. Give the exponent of $2$, of $3$ and of $5$.
| Value | |
|---|---|
| Exponent of $2$ | |
| Exponent of $3$ | |
| Exponent of $5$ |
Match each number to its prime factorisation.
| $2^{2}$ | $2^{3} \cdot 3^{2}$ | $2^{5} \cdot 3$ | |
|---|---|---|---|
| $4$ | |||
| $72$ | |||
| $96$ |
Given $108 = 2^{2} \cdot 3^{3}$ and $70 = 2 \cdot 5 \cdot 7$, what is $\gcd(108, 70)$?
Answer:
Is this true: every integer above $1$ has a prime factor?
Build the proof that a prime factorisation is unique up to the order of its factors.
This task has no paper form; do it on a device.
To what exponent does the prime $5$ appear in the factorisation of $25!$? (Do not compute the factorial.)
exponent a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Factorise $112$ into primes. Give the exponent of $2$, of $3$ and of $5$.
| Value | |
|---|---|
| Exponent of $2$ | |
| Exponent of $3$ | |
| Exponent of $5$ |
You can factorise an integer, compare two factorisations prime by prime, and prove that the factorisation is the only one. Say in your own words why the uniqueness half is the half that needs a theorem, and what that theorem is. Next: what a factorisation tells you about the divisors it generates.
9. Your turn: show that if $\gcd(a, b) = 1$ and $ab$ is a perfect square, then $a$ and $b$ are both perfect squares, step 3