Source — Euclid's Elements, encoded as an rrxiv paper

1% book09.tex --- Book IX of Euclid's Elements: Advanced Number Theory.
2%
3% All 36 propositions encoded.  Book IX continues from Book VIII with
4% propositions on squares, cubes, and the parity of products.  Two
5% propositions are particularly famous: IX.20 (there are infinitely many
6% primes) and IX.36 (every even perfect number arises from a Mersenne
7% prime).
8%
9% Wording follows Heath (1908).
10
11\section{Book IX --- Advanced Number Theory}
12\label{sec:book-IX}
13
14\begin{claim}[Proposition IX.1: Product of similar plane numbers is square]
15\label{prop:IX.1}
16If two similar plane numbers by multiplying one another make some
17number, the product will be square.
18\end{claim}
19\begin{evidence}[Proof of IX.1]
20\label{ev:IX.1}
21Similar plane numbers $ab$ and $cd$ with $a:b = c:d$ have product
22$(ab)(cd) = (ac)(bd)$, and the side $ac : bd$ is the square ratio,
23so the product is a square (VIII.26).
24\dependson{IX.1}{VIII.18}
25\dependson{IX.1}{VIII.26}
26\end{evidence}
27
28\begin{claim}[Proposition IX.2: Square product implies similar plane factors]
29\label{prop:IX.2}
30If two numbers by multiplying one another make a square number, they
31are similar plane numbers.
32\end{claim}
33\begin{evidence}[Proof of IX.2]
34\label{ev:IX.2}
35Converse of IX.1.  If $mn$ is square then $m : n$ has a mean
36proportional in integers; by VIII.20 this means $m$, $n$ are similar
37plane.
38\dependson{IX.2}{VIII.20}
39\dependson{IX.2}{IX.1}
40\end{evidence}
41
42\begin{claim}[Proposition IX.3: Cube times itself is a cube]
43\label{prop:IX.3}
44If a cube number by multiplying itself make some number, the product
45will be cube.
46\end{claim}
47\begin{evidence}[Proof of IX.3]
48\label{ev:IX.3}
49$(a^3)^2 = a^6 = (a^2)^3$.  Verified via VII.16 / VII.17.
50\dependson{IX.3}{VII.17}
51\dependson{IX.3}{def:VII.19}
52\end{evidence}
53
54\begin{claim}[Proposition IX.4: Cube times cube is cube]
55\label{prop:IX.4}
56If a cube number by multiplying a cube number make some number, the
57product will be cube.
58\end{claim}
59\begin{evidence}[Proof of IX.4]
60\label{ev:IX.4}
61$a^3 \cdot b^3 = (ab)^3$ by commutativity (VII.16).
62\dependson{IX.4}{VII.16}
63\dependson{IX.4}{IX.3}
64\end{evidence}
65
66\begin{claim}[Proposition IX.5: Cube product implies cube factor]
67\label{prop:IX.5}
68If a cube number by multiplying any number make a cube number, the
69multiplied number will also be cube.
70\end{claim}
71\begin{evidence}[Proof of IX.5]
72\label{ev:IX.5}
73If $a^3 \cdot n = m^3$ then $n = m^3 / a^3$; by VIII.25 the quotient
74of two cubes (when integer) is a cube.
75\dependson{IX.5}{VIII.25}
76\dependson{IX.5}{IX.4}
77\end{evidence}
78
79\begin{claim}[Proposition IX.6: Square root of a square product]
80\label{prop:IX.6}
81If a number by multiplying itself make a cube number, it itself will
82also be cube.
83\end{claim}
84\begin{evidence}[Proof of IX.6]
85\label{ev:IX.6}
86If $n^2 = a^3$ then $n^2 \cdot n = a^3 \cdot n$ is cubed; by VIII.25
87$n$ is cube.
88\dependson{IX.6}{IX.3}
89\dependson{IX.6}{IX.5}
90\end{evidence}
91
92\begin{claim}[Proposition IX.7: Product of a composite with any number]
93\label{prop:IX.7}
94If a composite number by multiplying any number make some number,
95the product will be solid.
96\end{claim}
97\begin{evidence}[Proof of IX.7]
98\label{ev:IX.7}
99A composite has a factorisation $ab$; multiplying by $c$ gives the
100triple product $abc$, which is solid by definition (VII.17).
101\dependson{IX.7}{VII.17}
102\dependson{IX.7}{def:VII.13}
103\dependson{IX.7}{def:VII.17}
104\end{evidence}
105
106\begin{claim}[Proposition IX.8: Geometric progression starting from unit]
107\label{prop:IX.8}
108If as many numbers as we please beginning from a unit be in continued
109proportion, the third from the unit will be square, the fourth a
110cube, and so on.
111\end{claim}
112\begin{evidence}[Proof of IX.8]
113\label{ev:IX.8}
114The sequence $1, r, r^2, r^3, \dots$ has third term a square, fourth
115a cube, sixth both square and cube, by VIII.11 / VIII.12.
116\dependson{IX.8}{VIII.11}
117\dependson{IX.8}{VIII.12}
118\end{evidence}
119
120\begin{claim}[Proposition IX.9: Sixth term from unit is square and cube]
121\label{prop:IX.9}
122If as many numbers as we please beginning from a unit be in continued
123proportion, and the number after the unit be square, all the rest
124will also be square; and if the number after the unit be cube, all
125the rest will also be cube.
126\end{claim}
127\begin{evidence}[Proof of IX.9]
128\label{ev:IX.9}
129In $1, r, r^2, r^3, \dots$, if $r$ is square then every $r^k$ is
130square; if $r$ is cube then every $r^k$ is cube --- by VIII.22 /
131VIII.23 propagated through the sequence.
132\dependson{IX.9}{VIII.22}
133\dependson{IX.9}{VIII.23}
134\dependson{IX.9}{IX.8}
135\end{evidence}
136
137\begin{claim}[Proposition IX.10: Non-square first term keeps the sequence non-square]
138\label{prop:IX.10}
139If as many numbers as we please beginning from a unit be in continued
140proportion, and the number after the unit be not square, neither will
141any other be square except the third from the unit and all those
142which leave out one.
143\end{claim}
144\begin{evidence}[Proof of IX.10]
145\label{ev:IX.10}
146Squares in $1, r, r^2, \dots$ occur exactly at even powers; if $r$
147is not square, only $r^{2k}$ terms are square.
148\dependson{IX.10}{IX.8}
149\dependson{IX.10}{IX.9}
150\end{evidence}
151
152\begin{claim}[Proposition IX.11: Term divides later term iff exponents differ]
153\label{prop:IX.11}
154If as many numbers as we please beginning from a unit be in continued
155proportion, the less measures the greater according to some one of
156the numbers which have place among the proportional numbers.
157\end{claim}
158\begin{evidence}[Proof of IX.11]
159\label{ev:IX.11}
160$r^a \mid r^b$ iff $a \le b$, and the quotient is $r^{b-a}$ --- which
161is itself a term of the sequence.
162\dependson{IX.11}{def:VII.3}
163\dependson{IX.11}{IX.8}
164\end{evidence}
165
166\begin{claim}[Proposition IX.12: Prime divisor of last term divides second]
167\label{prop:IX.12}
168If as many numbers as we please beginning from a unit be in continued
169proportion, by whatever prime numbers the last is measured, the
170second from the unit will also be measured by the same.
171\end{claim}
172\begin{evidence}[Proof of IX.12]
173\label{ev:IX.12}
174A prime dividing $r^n$ must divide $r$ (Euclid's lemma, VII.30),
175which is the second term after the unit.
176\dependson{IX.12}{VII.30}
177\dependson{IX.12}{IX.11}
178\end{evidence}
179
180\begin{claim}[Proposition IX.13: Geometric progression from prime unit]
181\label{prop:IX.13}
182If as many numbers as we please beginning from a unit be in continued
183proportion, and the number after the unit be prime, the greatest will
184not be measured by any except those which have a place among the
185proportional numbers.
186\end{claim}
187\begin{evidence}[Proof of IX.13]
188\label{ev:IX.13}
189If $r$ is prime, the divisors of $r^n$ are exactly $1, r, r^2, \dots,
190r^n$ (Euclid's lemma).  These are exactly the prefix of the sequence.
191\dependson{IX.13}{VII.30}
192\dependson{IX.13}{IX.12}
193\end{evidence}
194
195\begin{claim}[Proposition IX.14: Unique prime factorisation precursor]
196\label{prop:IX.14}
197If a number be the least that is measured by prime numbers, it will
198not be measured by any other prime number except those originally
199measuring it.
200\end{claim}
201\begin{evidence}[Proof of IX.14]
202\label{ev:IX.14}
203A least common multiple of primes equals their product; any prime
204dividing the product divides one of the factors (VII.30), hence is
205one of the originals.  This is the kernel of unique factorisation.
206\dependson{IX.14}{VII.30}
207\dependson{IX.14}{VII.34}
208\end{evidence}
209
210\begin{claim}[Proposition IX.15: Three numbers in continued proportion, coprime extremes]
211\label{prop:IX.15}
212If three numbers in continued proportion be the least of those which
213have the same ratio with them, any two whatever added together will
214be prime to the remaining number.
215\end{claim}
216\begin{evidence}[Proof of IX.15]
217\label{ev:IX.15}
218For $a, b, c$ with $a : b = b : c$ in lowest terms: by VIII.3 the
219extremes are coprime; combining with VII.28 the sums $a+b$, $b+c$,
220$a+c$ are each coprime to the third term.
221\dependson{IX.15}{VII.28}
222\dependson{IX.15}{VIII.3}
223\end{evidence}
224
225\begin{claim}[Proposition IX.16: Coprime numbers and proportion]
226\label{prop:IX.16}
227If two numbers be prime to one another, the second will not be to
228any other number as the first is to the second.
229\end{claim}
230\begin{evidence}[Proof of IX.16]
231\label{ev:IX.16}
232If $a : b = b : c$ with $\gcd(a, b) = 1$, then $b^2 = ac$, forcing
233$a \mid b^2$ which (Euclid's lemma) forces $a \mid b$ -- contradicting
234coprimality unless $a = 1$.
235\dependson{IX.16}{VII.19}
236\dependson{IX.16}{VII.30}
237\end{evidence}
238
239\begin{claim}[Proposition IX.17: Coprime sequence and extension]
240\label{prop:IX.17}
241If as many numbers as we please be in continued proportion, and the
242extremes of them be prime to one another, the last will not be to
243any other number as the first is to the second.
244\end{claim}
245\begin{evidence}[Proof of IX.17]
246\label{ev:IX.17}
247Generalisation of IX.16: a coprime-extremes proportion cannot be
248extended further while remaining a proportion of integers in the
249same ratio.
250\dependson{IX.17}{VIII.3}
251\dependson{IX.17}{IX.16}
252\end{evidence}
253
254\begin{claim}[Proposition IX.18: Existence of a third proportional]
255\label{prop:IX.18}
256Given two numbers, to investigate whether it is possible to find a
257third proportional to them.
258\end{claim}
259\begin{evidence}[Proof of IX.18]
260\label{ev:IX.18}
261A third proportional to $a$, $b$ exists iff $b^2$ is divisible by
262$a$ (i.e.\ $b^2 / a$ is an integer); apply VII.19.
263\dependson{IX.18}{VII.19}
264\dependson{IX.18}{IX.16}
265\end{evidence}
266
267\begin{claim}[Proposition IX.19: Existence of a fourth proportional]
268\label{prop:IX.19}
269Given three numbers, to investigate when it is possible to find a
270fourth proportional to them.
271\end{claim}
272\begin{evidence}[Proof of IX.19]
273\label{ev:IX.19}
274A fourth proportional to $a$, $b$, $c$ exists iff $bc / a$ is an
275integer; otherwise no integer extends the proportion.
276\dependson{IX.19}{VII.19}
277\dependson{IX.19}{IX.18}
278\end{evidence}
279
280\begin{claim}[Proposition IX.20: There are infinitely many primes]
281\label{prop:IX.20}
282Prime numbers are more than any assigned multitude of prime numbers.
283\end{claim}
284\begin{evidence}[Proof of IX.20]
285\label{ev:IX.20}
286Given primes $p_1, \dots, p_n$, form $N = p_1 p_2 \cdots p_n + 1$.
287By VII.31 $N$ has a prime divisor $q$.  If $q$ were one of the
288$p_i$, then $q$ would divide $N - p_1 \cdots p_n = 1$ (Common Notion
2893), which is impossible.  Hence $q$ is a new prime not in the
290original list; the list of primes admits no upper bound.
291\dependson{IX.20}{VII.31}
292\dependson{IX.20}{cn:3}
293\dependson{IX.20}{def:VII.11}
294\end{evidence}
295
296\begin{claim}[Proposition IX.21: Sum of evens is even]
297\label{prop:IX.21}
298If as many even numbers as we please be added together, the whole is
299even.
300\end{claim}
301\begin{evidence}[Proof of IX.21]
302\label{ev:IX.21}
303Each even number is divisible by 2; the sum is therefore divisible
304by 2 (Common Notion 2).
305\dependson{IX.21}{cn:2}
306\dependson{IX.21}{def:VII.6}
307\end{evidence}
308
309\begin{claim}[Proposition IX.22: Sum of even-many odd is even]
310\label{prop:IX.22}
311If as many odd numbers as we please be added together, and their
312multitude be even, the whole will be even.
313\end{claim}
314\begin{evidence}[Proof of IX.22]
315\label{ev:IX.22}
316Pair the odd summands: each pair has even sum (since odd + odd =
317even, by the definitions); the total of even-many pairs is even by
318IX.21.
319\dependson{IX.22}{IX.21}
320\dependson{IX.22}{def:VII.7}
321\end{evidence}
322
323\begin{claim}[Proposition IX.23: Sum of odd-many odd is odd]
324\label{prop:IX.23}
325If as many odd numbers as we please be added together, and their
326multitude be odd, the whole will also be odd.
327\end{claim}
328\begin{evidence}[Proof of IX.23]
329\label{ev:IX.23}
330Group all but one of the summands by pairs (sum of those is even,
331IX.22); add the remaining odd number; the result is even + odd =
332odd by Common Notion 2 and Definition VII.7.
333\dependson{IX.23}{IX.22}
334\dependson{IX.23}{def:VII.7}
335\end{evidence}
336
337\begin{claim}[Proposition IX.24: Difference of two evens is even]
338\label{prop:IX.24}
339If from an even number an even number be subtracted, the remainder
340will be even.
341\end{claim}
342\begin{evidence}[Proof of IX.24]
343\label{ev:IX.24}
344Two multiples of 2 differ by a multiple of 2 (Common Notion 3).
345\dependson{IX.24}{cn:3}
346\dependson{IX.24}{def:VII.6}
347\end{evidence}
348
349\begin{claim}[Proposition IX.25: Even minus odd is odd]
350\label{prop:IX.25}
351If from an even number an odd number be subtracted, the remainder
352will be odd.
353\end{claim}
354\begin{evidence}[Proof of IX.25]
355\label{ev:IX.25}
356$2k - (2m+1) = 2(k-m) - 1$, which is odd by Definition VII.7.
357\dependson{IX.25}{cn:3}
358\dependson{IX.25}{def:VII.7}
359\end{evidence}
360
361\begin{claim}[Proposition IX.26: Odd minus odd is even]
362\label{prop:IX.26}
363If from an odd number an odd number be subtracted, the remainder will
364be even.
365\end{claim}
366\begin{evidence}[Proof of IX.26]
367\label{ev:IX.26}
368$(2k+1) - (2m+1) = 2(k-m)$, even.
369\dependson{IX.26}{cn:3}
370\dependson{IX.26}{def:VII.6}
371\end{evidence}
372
373\begin{claim}[Proposition IX.27: Odd minus even is odd]
374\label{prop:IX.27}
375If from an odd number an even number be subtracted, the remainder
376will be odd.
377\end{claim}
378\begin{evidence}[Proof of IX.27]
379\label{ev:IX.27}
380$(2k+1) - 2m = 2(k-m) + 1$, odd.
381\dependson{IX.27}{cn:3}
382\dependson{IX.27}{def:VII.7}
383\end{evidence}
384
385\begin{claim}[Proposition IX.28: Odd times even is even]
386\label{prop:IX.28}
387If an odd number by multiplying an even number make some number, the
388product will be even.
389\end{claim}
390\begin{evidence}[Proof of IX.28]
391\label{ev:IX.28}
392$(2k+1) \cdot 2m = 2 m(2k+1)$, a multiple of 2.
393\dependson{IX.28}{IX.21}
394\dependson{IX.28}{def:VII.6}
395\end{evidence}
396
397\begin{claim}[Proposition IX.29: Odd times odd is odd]
398\label{prop:IX.29}
399If an odd number by multiplying an odd number make some number, the
400product will be odd.
401\end{claim}
402\begin{evidence}[Proof of IX.29]
403\label{ev:IX.29}
404$(2k+1)(2m+1) = 4km + 2k + 2m + 1$, which is odd (one more than even).
405\dependson{IX.29}{IX.23}
406\dependson{IX.29}{def:VII.7}
407\end{evidence}
408
409\begin{claim}[Proposition IX.30: Odd dividing an even number]
410\label{prop:IX.30}
411If an odd number measure an even number, it will also measure the
412half of it.
413\end{claim}
414\begin{evidence}[Proof of IX.30]
415\label{ev:IX.30}
416If $a$ (odd) divides $2b$, then since $\gcd(a, 2) = 1$, $a \mid b$
417by VII.24.
418\dependson{IX.30}{VII.24}
419\dependson{IX.30}{def:VII.6}
420\dependson{IX.30}{def:VII.7}
421\end{evidence}
422
423\begin{claim}[Proposition IX.31: Odd coprime to its double]
424\label{prop:IX.31}
425If an odd number be prime to any number, it will also be prime to
426the double of it.
427\end{claim}
428\begin{evidence}[Proof of IX.31]
429\label{ev:IX.31}
430$\gcd(a, n) = 1$ for $a$ odd implies $\gcd(a, 2n) = 1$ (since
431$\gcd(a, 2) = 1$); apply VII.24.
432\dependson{IX.31}{VII.24}
433\dependson{IX.31}{def:VII.7}
434\end{evidence}
435
436\begin{claim}[Proposition IX.32: Powers of 2 are even-times even]
437\label{prop:IX.32}
438Each of the numbers which are continually doubled beginning from a
439duad is even-times even only.
440\end{claim}
441\begin{evidence}[Proof of IX.32]
442\label{ev:IX.32}
443$2^n$ has no odd divisors greater than 1 (Euclid's lemma); hence its
444only factorisation is $2 \times 2^{n-1}$, even-times-even.
445\dependson{IX.32}{VII.30}
446\dependson{IX.32}{def:VII.8}
447\end{evidence}
448
449\begin{claim}[Proposition IX.33: Number whose half is odd]
450\label{prop:IX.33}
451If a number have its half odd, it is even-times odd only.
452\end{claim}
453\begin{evidence}[Proof of IX.33]
454\label{ev:IX.33}
455$n = 2k$ with $k$ odd is even-times-odd; it cannot be even-times-even
456because then its half would be even.
457\dependson{IX.33}{def:VII.6}
458\dependson{IX.33}{def:VII.9}
459\end{evidence}
460
461\begin{claim}[Proposition IX.34: Neither power of 2 nor twice-odd: both kinds]
462\label{prop:IX.34}
463If an even number be neither one of those which are doubled from a
464duad, nor have its half odd, it is both even-times even and
465even-times odd.
466\end{claim}
467\begin{evidence}[Proof of IX.34]
468\label{ev:IX.34}
469Such a number has the form $2^k m$ with $k \ge 2$ and $m$ odd, $m
470> 1$: it is even-times even ($2 \cdot 2^{k-1} m$) and even-times odd
471($2^k \cdot m$).
472\dependson{IX.34}{IX.32}
473\dependson{IX.34}{IX.33}
474\end{evidence}
475
476\begin{claim}[Proposition IX.35: Geometric series formula]
477\label{prop:IX.35}
478If as many numbers as we please be in continued proportion, and there
479be subtracted from the second and the last numbers equal to the
480first, then, as the excess of the second is to the first, so will the
481excess of the last be to all those before it.
482\end{claim}
483\begin{evidence}[Proof of IX.35]
484\label{ev:IX.35}
485For $a, ar, ar^2, \dots, ar^n$: the excess of the last over the
486first is $a(r^n - 1)$, and the sum of the rest is $a(1 + r + r^2 +
487\dots + r^{n-1}) = a (r^n - 1) / (r - 1)$; the ratio of excess to
488sum equals $(r - 1) = (ar - a) / a$, the excess of the second over
489the first divided by the first.
490\dependson{IX.35}{VII.11}
491\dependson{IX.35}{VII.19}
492\dependson{IX.35}{VIII.1}
493\end{evidence}
494
495\begin{claim}[Proposition IX.36: Even perfect number theorem]
496\label{prop:IX.36}
497If as many numbers as we please beginning from a unit be set out
498continuously in double proportion, until the sum of all becomes
499prime, and if the sum multiplied into the last make some number, the
500product will be perfect.
501\end{claim}
502\begin{evidence}[Proof of IX.36]
503\label{ev:IX.36}
504Let $s = 1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$ be prime (a Mersenne
505prime); set $N = s \cdot 2^{n-1}$.  The proper divisors of $N$ are
506$1, 2, 4, \dots, 2^{n-1}, s, 2s, \dots, 2^{n-2}s$, whose sum is
507$(2^n - 1) + s(2^{n-1} - 1) = s + s(2^{n-1} - 1) = s \cdot 2^{n-1}
508= N$.  So $N$ equals the sum of its proper divisors and is perfect.
509\dependson{IX.36}{IX.35}
510\dependson{IX.36}{VII.34}
511\dependson{IX.36}{def:VII.11}
512\dependson{IX.36}{def:VII.22}
513\end{evidence}
514