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

1% book07.tex --- Book VII of Euclid's Elements: Number Theory Foundations.
2%
3% All 39 propositions encoded. Book VII switches from continuous
4% magnitudes to discrete numbers: the Euclidean algorithm (VII.1, VII.2),
5% Euclid's lemma (VII.30), and the unique-factorisation precursor
6% (VII.31, VII.32) all live here.  The proofs are inductive in spirit but
7% framed as classical reductios.
8%
9% Wording follows Heath (1908).
10
11\section{Book VII --- Number Theory Foundations}
12\label{sec:book-VII}
13
14\begin{claim}[Proposition VII.1: Coprime detection by anthyphairesis]
15\label{prop:VII.1}
16Two unequal numbers being set out, and the less being continually
17subtracted in turn from the greater, if the number which is left
18never measures the one before it until a unit is left, the original
19numbers will be prime to one another.
20\end{claim}
21\begin{evidence}[Proof of VII.1]
22\label{ev:VII.1}
23Suppose for contradiction some number $d > 1$ measures both inputs.
24At each subtraction step the divisor and remainder differ from the
25previous pair by a common multiple of $d$; so $d$ persists through
26the algorithm and ultimately measures the unit, which is impossible.
27\dependson{VII.1}{def:VII.1}
28\dependson{VII.1}{def:VII.11}
29\end{evidence}
30
31\begin{claim}[Proposition VII.2: Greatest common measure]
32\label{prop:VII.2}
33Given two numbers not prime to one another, to find their greatest
34common measure.
35\end{claim}
36\begin{evidence}[Proof of VII.2]
37\label{ev:VII.2}
38Run the anthyphairesis (Euclidean algorithm).  Since the numbers are
39not prime to one another, the procedure terminates at a non-unit
40remainder $d$; that $d$ measures both inputs, and any other common
41measure also divides $d$ by the same persistence argument as VII.1.
42\dependson{VII.2}{VII.1}
43\dependson{VII.2}{def:VII.3}
44\end{evidence}
45
46\begin{claim}[Proposition VII.3: Greatest common measure of three numbers]
47\label{prop:VII.3}
48Given three numbers not prime to one another, to find their greatest
49common measure.
50\end{claim}
51\begin{evidence}[Proof of VII.3]
52\label{ev:VII.3}
53Find the gcd of two of them by VII.2; then find the gcd of that
54result with the third.  The final number measures all three and is
55greatest by the same persistence argument.
56\dependson{VII.3}{VII.2}
57\end{evidence}
58
59\begin{claim}[Proposition VII.4: Any number is a part or parts of a greater]
60\label{prop:VII.4}
61Any number is either a part or parts of any number, the less of the
62greater.
63\end{claim}
64\begin{evidence}[Proof of VII.4]
65\label{ev:VII.4}
66Either the less divides the greater (a part, Definition VII.3) or it
67does not (parts, Definition VII.4).  The Euclidean algorithm
68terminates, so the case analysis is exhaustive.
69\dependson{VII.4}{VII.2}
70\dependson{VII.4}{def:VII.3}
71\dependson{VII.4}{def:VII.4}
72\end{evidence}
73
74\begin{claim}[Proposition VII.5: Equal parts of equals are equal parts of the sum]
75\label{prop:VII.5}
76If a number be a part of a number, and another be the same part of
77another, the sum will also be the same part of the sum that the one
78is of the other.
79\end{claim}
80\begin{evidence}[Proof of VII.5]
81\label{ev:VII.5}
82$a = b/n$ and $c = d/n$ give $a + c = (b + d)/n$ by gathering $n$
83copies of $a + c$ together.
84\dependson{VII.5}{cn:2}
85\dependson{VII.5}{def:VII.3}
86\end{evidence}
87
88\begin{claim}[Proposition VII.6: Same parts of parts]
89\label{prop:VII.6}
90If a number be parts of a number, and another be the same parts of
91another, the sum will also be the same parts of the sum that the one
92is of the other.
93\end{claim}
94\begin{evidence}[Proof of VII.6]
95\label{ev:VII.6}
96Same argument as VII.5 with $p/q$ fractions; each fractional piece
97sums separately by VII.5 and then by VII.5 again on the multiples.
98\dependson{VII.6}{VII.5}
99\end{evidence}
100
101\begin{claim}[Proposition VII.7: Difference of equal parts]
102\label{prop:VII.7}
103If a number be the same part of a number that a subtracted number is
104of a subtracted number, the remainder will also be the same part of
105the remainder that the whole is of the whole.
106\end{claim}
107\begin{evidence}[Proof of VII.7]
108\label{ev:VII.7}
109If $a = b/n$ and $a' = b'/n$ then $a - a' = (b - b')/n$ by Common
110Notion 3 applied to each of the $n$ pieces.
111\dependson{VII.7}{cn:3}
112\dependson{VII.7}{def:VII.3}
113\end{evidence}
114
115\begin{claim}[Proposition VII.8: Difference of equal parts (generalised)]
116\label{prop:VII.8}
117If a number be the same parts of a number that a subtracted number
118is of a subtracted number, the remainder will also be the same parts
119of the remainder that the whole is of the whole.
120\end{claim}
121\begin{evidence}[Proof of VII.8]
122\label{ev:VII.8}
123Same as VII.7 but for $p/q$ fractions; combine VII.7 with VII.6.
124\dependson{VII.8}{VII.6}
125\dependson{VII.8}{VII.7}
126\end{evidence}
127
128\begin{claim}[Proposition VII.9: Symmetric form of parts]
129\label{prop:VII.9}
130If a number be a part of a number, and another be the same part of
131another, alternately, whatever part or parts the first is of the
132third, the same part or the same parts will the second also be of
133the fourth.
134\end{claim}
135\begin{evidence}[Proof of VII.9]
136\label{ev:VII.9}
137The "part of a part" relation is symmetric across the alternation by
138construction; apply VII.5 / VII.6 on a per-piece basis to confirm.
139\dependson{VII.9}{VII.5}
140\dependson{VII.9}{VII.6}
141\end{evidence}
142
143\begin{claim}[Proposition VII.10: Alternation of parts]
144\label{prop:VII.10}
145If a number be parts of a number, and another be the same parts of
146another, alternately, whatever parts or part the first is of the
147third, the same parts or the same part will the second also be of
148the fourth.
149\end{claim}
150\begin{evidence}[Proof of VII.10]
151\label{ev:VII.10}
152Same scheme as VII.9 with $p/q$ fractions.
153\dependson{VII.10}{VII.9}
154\end{evidence}
155
156\begin{claim}[Proposition VII.11: Subtraction in a proportion]
157\label{prop:VII.11}
158If, as whole is to whole, so is a number subtracted to a number
159subtracted, the remainder will also be to the remainder as whole is
160to whole.
161\end{claim}
162\begin{evidence}[Proof of VII.11]
163\label{ev:VII.11}
164Discrete analogue of V.19: subtract equimultiples on antecedents and
165consequents and the proportion is preserved.
166\dependson{VII.11}{VII.7}
167\dependson{VII.11}{VII.8}
168\end{evidence}
169
170\begin{claim}[Proposition VII.12: Sum of antecedents to sum of consequents]
171\label{prop:VII.12}
172If there be as many numbers as we please in proportion, then, as one
173of the antecedents is to one of the consequents, so will all the
174antecedents be to all the consequents.
175\end{claim}
176\begin{evidence}[Proof of VII.12]
177\label{ev:VII.12}
178Discrete analogue of V.12: each pair contributes the same multiple
179or part, so the sum does too.
180\dependson{VII.12}{VII.5}
181\dependson{VII.12}{VII.6}
182\end{evidence}
183
184\begin{claim}[Proposition VII.13: Alternation]
185\label{prop:VII.13}
186If four numbers be proportional, they will also be proportional
187alternately.
188\end{claim}
189\begin{evidence}[Proof of VII.13]
190\label{ev:VII.13}
191Discrete analogue of V.16, deduced from VII.9 / VII.10 (the parts
192versions of alternation).
193\dependson{VII.13}{VII.9}
194\dependson{VII.13}{VII.10}
195\end{evidence}
196
197\begin{claim}[Proposition VII.14: Ex aequali for numbers]
198\label{prop:VII.14}
199If there be as many numbers as we please, and others equal to them
200in multitude, which taken two and two are in the same ratio, they
201will also be in the same ratio ex aequali.
202\end{claim}
203\begin{evidence}[Proof of VII.14]
204\label{ev:VII.14}
205Discrete analogue of V.22: chain alternation (VII.13) through the
206intermediate ratios.
207\dependson{VII.14}{VII.13}
208\end{evidence}
209
210\begin{claim}[Proposition VII.15: Multiplying preserves ratio with unit]
211\label{prop:VII.15}
212If a unit measure any number, and another number measure any other
213number the same number of times, then, alternately, the unit will
214measure the third number the same number of times as the second
215measures the fourth.
216\end{claim}
217\begin{evidence}[Proof of VII.15]
218\label{ev:VII.15}
219Discrete analogue of V.7 / V.16 applied to the unit; the unit
220relations transfer through the equimultiples.
221\dependson{VII.15}{VII.13}
222\dependson{VII.15}{def:VII.1}
223\end{evidence}
224
225\begin{claim}[Proposition VII.16: Commutativity of multiplication]
226\label{prop:VII.16}
227If two numbers by multiplying one another make certain numbers, the
228numbers so produced will be equal to one another.
229\end{claim}
230\begin{evidence}[Proof of VII.16]
231\label{ev:VII.16}
232$a \cdot b$ counts the units in a $b$-many sum of $a$'s; $b \cdot a$
233counts the units in an $a$-many sum of $b$'s.  Both equal $ab$ by
234VII.5 applied to the unit.
235\dependson{VII.16}{VII.5}
236\dependson{VII.16}{VII.15}
237\dependson{VII.16}{def:VII.15}
238\end{evidence}
239
240\begin{claim}[Proposition VII.17: Distributivity over equal multiples]
241\label{prop:VII.17}
242If a number by multiplying two numbers make certain numbers, the
243numbers so produced will have the same ratio as the numbers
244multiplied.
245\end{claim}
246\begin{evidence}[Proof of VII.17]
247\label{ev:VII.17}
248$c \cdot a : c \cdot b = a : b$ by gathering the $c$ copies of each
249side; the equimultiples test of definition V.5 (in its discrete
250specialisation, VII.20) reduces to the test on $(a, b)$.
251\dependson{VII.17}{VII.16}
252\dependson{VII.17}{def:VII.20}
253\end{evidence}
254
255\begin{claim}[Proposition VII.18: Multiplication on the consequent]
256\label{prop:VII.18}
257If two numbers by multiplying any number make certain numbers, the
258numbers so produced will have the same ratio as the multipliers.
259\end{claim}
260\begin{evidence}[Proof of VII.18]
261\label{ev:VII.18}
262$a \cdot c : b \cdot c = a : b$ by VII.16 (swap to put $c$ on the
263left) and VII.17.
264\dependson{VII.18}{VII.16}
265\dependson{VII.18}{VII.17}
266\end{evidence}
267
268\begin{claim}[Proposition VII.19: Equal products iff proportional numbers]
269\label{prop:VII.19}
270If four numbers be proportional, the number produced from the first
271and fourth will be equal to the number produced from the second and
272third; and if the number produced from the first and fourth be equal
273to that produced from the second and third, the four numbers will be
274proportional.
275\end{claim}
276\begin{evidence}[Proof of VII.19]
277\label{ev:VII.19}
278Discrete analogue of VI.16: cross-multiplication preserves and
279detects proportionality.  Use VII.17 in one direction and the
280converse argument (proportion from equal products via VII.14) in the
281other.
282\dependson{VII.19}{VII.14}
283\dependson{VII.19}{VII.17}
284\dependson{VII.19}{VII.18}
285\end{evidence}
286
287\begin{claim}[Proposition VII.20: Least numbers in a ratio measure the others]
288\label{prop:VII.20}
289The least numbers of those which have the same ratio with them
290measure those which have the same ratio the same number of times,
291the greater the greater and the less the less.
292\end{claim}
293\begin{evidence}[Proof of VII.20]
294\label{ev:VII.20}
295Given $a : b = p : q$ with $p$, $q$ least in their ratio, by VII.2
296$\gcd(a, b) \cdot p = a$ and $\gcd(a, b) \cdot q = b$, so $p$, $q$
297each measure $a$, $b$ the same number of times $\gcd(a, b)$.
298\dependson{VII.20}{VII.2}
299\dependson{VII.20}{VII.19}
300\end{evidence}
301
302\begin{claim}[Proposition VII.21: Numbers prime to one another are least in their ratio]
303\label{prop:VII.21}
304Numbers prime to one another are the least of those which have the
305same ratio with them.
306\end{claim}
307\begin{evidence}[Proof of VII.21]
308\label{ev:VII.21}
309If two coprime numbers $a$, $b$ had smaller numbers $c$, $d$ with
310$a : b = c : d$, then by VII.20 $c$, $d$ would measure $a$, $b$ a
311common number of times; the common measure would contradict
312coprimality.
313\dependson{VII.21}{VII.20}
314\dependson{VII.21}{def:VII.12}
315\end{evidence}
316
317\begin{claim}[Proposition VII.22: Least in a ratio are coprime]
318\label{prop:VII.22}
319The least numbers of those which have the same ratio with them are
320prime to one another.
321\end{claim}
322\begin{evidence}[Proof of VII.22]
323\label{ev:VII.22}
324Converse of VII.21: any common measure of the least pair would
325generate a strictly smaller pair in the same ratio, contradicting
326minimality.
327\dependson{VII.22}{VII.20}
328\dependson{VII.22}{VII.21}
329\end{evidence}
330
331\begin{claim}[Proposition VII.23: Coprime to a product]
332\label{prop:VII.23}
333If two numbers be prime to one another, the number which measures
334the one of them will be prime to the remaining number.
335\end{claim}
336\begin{evidence}[Proof of VII.23]
337\label{ev:VII.23}
338If $a$, $b$ are coprime and $d \mid a$, any common divisor of $d$ and
339$b$ would divide both $a$ and $b$, contradicting coprimality.
340\dependson{VII.23}{VII.2}
341\dependson{VII.23}{def:VII.12}
342\end{evidence}
343
344\begin{claim}[Proposition VII.24: Coprime preserved under multiplication]
345\label{prop:VII.24}
346If two numbers be prime to any number, their product also will be
347prime to the same.
348\end{claim}
349\begin{evidence}[Proof of VII.24]
350\label{ev:VII.24}
351If $\gcd(a, c) = 1$ and $\gcd(b, c) = 1$, then any prime dividing
352$ab$ and $c$ must divide $a$ or $b$ (using the descent from
353VII.23) and would contradict one of the hypotheses.
354\dependson{VII.24}{VII.23}
355\end{evidence}
356
357\begin{claim}[Proposition VII.25: Coprime preserved under squaring]
358\label{prop:VII.25}
359If two numbers be prime to one another, the product of one of them
360into itself will be prime to the remaining one.
361\end{claim}
362\begin{evidence}[Proof of VII.25]
363\label{ev:VII.25}
364Specialise VII.24 with $b = a$.
365\dependson{VII.25}{VII.24}
366\end{evidence}
367
368\begin{claim}[Proposition VII.26: Product of coprime pairs is coprime]
369\label{prop:VII.26}
370If two numbers be prime to two numbers, both to each, their products
371also will be prime to one another.
372\end{claim}
373\begin{evidence}[Proof of VII.26]
374\label{ev:VII.26}
375$\gcd(ab, cd) = 1$ when $\gcd(a, c) = \gcd(a, d) = \gcd(b, c) =
376\gcd(b, d) = 1$: apply VII.24 twice.
377\dependson{VII.26}{VII.24}
378\end{evidence}
379
380\begin{claim}[Proposition VII.27: Coprime preserved under arbitrary powers]
381\label{prop:VII.27}
382If two numbers be prime to one another, and each by multiplying
383itself make a certain number, the products will be prime to one
384another; and if the original numbers by multiplying the products
385make certain numbers, these will be prime to one another.
386\end{claim}
387\begin{evidence}[Proof of VII.27]
388\label{ev:VII.27}
389Iterate VII.25: $\gcd(a, b) = 1$ implies $\gcd(a^n, b^m) = 1$ for
390all $n$, $m$.
391\dependson{VII.27}{VII.25}
392\dependson{VII.27}{VII.26}
393\end{evidence}
394
395\begin{claim}[Proposition VII.28: Sum coprime iff each summand coprime to a third]
396\label{prop:VII.28}
397If two numbers be prime to one another, the sum will also be prime
398to each of them; and if the sum of two numbers be prime to either of
399them, the original numbers will also be prime to one another.
400\end{claim}
401\begin{evidence}[Proof of VII.28]
402\label{ev:VII.28}
403Any common divisor of $a + b$ and $a$ would also divide $b$ (by
404Common Notion 3), contradicting $\gcd(a, b) = 1$.  Converse runs the
405same way.
406\dependson{VII.28}{cn:3}
407\dependson{VII.28}{def:VII.12}
408\end{evidence}
409
410\begin{claim}[Proposition VII.29: Prime is coprime to anything it does not measure]
411\label{prop:VII.29}
412Any prime number is prime to any number which it does not measure.
413\end{claim}
414\begin{evidence}[Proof of VII.29]
415\label{ev:VII.29}
416The only divisors of a prime are 1 and itself; if the prime does not
417divide the other number, the only common divisor is 1.
418\dependson{VII.29}{def:VII.11}
419\dependson{VII.29}{def:VII.12}
420\end{evidence}
421
422\begin{claim}[Proposition VII.30: Euclid's lemma]
423\label{prop:VII.30}
424If two numbers by multiplying one another make some number, and any
425prime number measure the product, it will also measure one of the
426original numbers.
427\end{claim}
428\begin{evidence}[Proof of VII.30]
429\label{ev:VII.30}
430If a prime $p \mid ab$ but $p \nmid a$, then by VII.29 $p$ is
431coprime to $a$; by VII.24 (taking $b$ as the multiplicand) $p$ must
432divide $b$.
433\dependson{VII.30}{VII.24}
434\dependson{VII.30}{VII.29}
435\end{evidence}
436
437\begin{claim}[Proposition VII.31: Every number has a prime divisor]
438\label{prop:VII.31}
439Any composite number is measured by some prime number.
440\end{claim}
441\begin{evidence}[Proof of VII.31]
442\label{ev:VII.31}
443Descend through divisors: a composite has a proper divisor, that
444divisor is either prime or composite; if composite, repeat.  The
445descent must terminate (numbers are bounded below by 2), so a prime
446divisor exists.
447\dependson{VII.31}{def:VII.11}
448\dependson{VII.31}{def:VII.13}
449\end{evidence}
450
451\begin{claim}[Proposition VII.32: Every number is prime or has a prime divisor]
452\label{prop:VII.32}
453Any number either is prime or is measured by some prime number.
454\end{claim}
455\begin{evidence}[Proof of VII.32]
456\label{ev:VII.32}
457Case split: if the number is prime, done; otherwise apply VII.31.
458\dependson{VII.32}{VII.31}
459\end{evidence}
460
461\begin{claim}[Proposition VII.33: Reduction to least numbers in same ratio]
462\label{prop:VII.33}
463Given as many numbers as we please, to find the least of those which
464have the same ratio with them.
465\end{claim}
466\begin{evidence}[Proof of VII.33]
467\label{ev:VII.33}
468Divide each given number by their common gcd (VII.3); the quotients
469are pairwise coprime (VII.22) and least in the original ratio.
470\dependson{VII.33}{VII.3}
471\dependson{VII.33}{VII.22}
472\end{evidence}
473
474\begin{claim}[Proposition VII.34: Least common multiple of two numbers]
475\label{prop:VII.34}
476Given two numbers, to find the least number which they measure.
477\end{claim}
478\begin{evidence}[Proof of VII.34]
479\label{ev:VII.34}
480$\mathrm{lcm}(a, b) = ab / \gcd(a, b)$: multiply $a$ by $b$ then
481divide by the gcd (VII.2).
482\dependson{VII.34}{VII.2}
483\dependson{VII.34}{VII.20}
484\end{evidence}
485
486\begin{claim}[Proposition VII.35: Common multiple is a multiple of the lcm]
487\label{prop:VII.35}
488If two numbers measure any number, the least number measured by them
489will also measure the same.
490\end{claim}
491\begin{evidence}[Proof of VII.35]
492\label{ev:VII.35}
493Let $L = \mathrm{lcm}(a, b)$ and suppose $a, b \mid n$.  Divide $n$
494by $L$ with remainder; the remainder $r$ is measured by both $a$ and
495$b$ (Common Notion 3 on the equimultiples) and is less than $L$.  By
496minimality of $L$, $r = 0$.
497\dependson{VII.35}{VII.34}
498\dependson{VII.35}{cn:3}
499\end{evidence}
500
501\begin{claim}[Proposition VII.36: Least common multiple of three numbers]
502\label{prop:VII.36}
503Given three numbers, to find the least number which they measure.
504\end{claim}
505\begin{evidence}[Proof of VII.36]
506\label{ev:VII.36}
507Compute $\mathrm{lcm}(a, b)$ by VII.34, then $\mathrm{lcm}$ of that
508with $c$.  By VII.35 the result is the least common multiple of all
509three.
510\dependson{VII.36}{VII.34}
511\dependson{VII.36}{VII.35}
512\end{evidence}
513
514\begin{claim}[Proposition VII.37: Number measures iff it is a quotient]
515\label{prop:VII.37}
516If a number be measured by any number, the number which is measured
517will have a part called by the same name as the measuring number.
518\end{claim}
519\begin{evidence}[Proof of VII.37]
520\label{ev:VII.37}
521$a \mid b$ means $b = ka$ for some $k$; then $b / k = a$, i.e.\ the
522$k$-th part of $b$ is $a$.
523\dependson{VII.37}{def:VII.3}
524\end{evidence}
525
526\begin{claim}[Proposition VII.38: Quotient existence]
527\label{prop:VII.38}
528If a number have any part whatever, it will be measured by a number
529called by the same name as the part.
530\end{claim}
531\begin{evidence}[Proof of VII.38]
532\label{ev:VII.38}
533Converse of VII.37: if $b/k = a$ then $a \mid b$ with quotient $k$.
534\dependson{VII.38}{VII.37}
535\end{evidence}
536
537\begin{claim}[Proposition VII.39: Least number with prescribed parts]
538\label{prop:VII.39}
539To find the number which is the least that will have given parts.
540\end{claim}
541\begin{evidence}[Proof of VII.39]
542\label{ev:VII.39}
543Take the lcm (VII.34, VII.36) of the prescribed denominators; that
544is the smallest number containing all the prescribed parts.
545\dependson{VII.39}{VII.34}
546\dependson{VII.39}{VII.36}
547\end{evidence}
548