1 Foundation
Glossary of Symbols
- \(\mathbb{N}\) — the set of natural numbers: \(\{1,2,3,\dots\}\).
- \(\mathbb{Z}\) — the set of integers: \(\{\dots,-3,-2,-1,0,1,2,3,\dots\}\).
- \(\in\) — “is an element of / is a member of.” Example: \(3 \in \mathbb{N}\) because 3 is a natural number; \(-5 \in \mathbb{Z}\).
- \(+\) — addition; \(-\) — subtraction. Example: \(7 - 4 = 3\).
- \(\cdot\) or juxtaposition \(ab\) — multiplication. Example: \(3\cdot 4 = 12\).
- / — division (used in explanations). Exact division is expressed with \(\mid\).
- \(=\) — equals. \(<\), \(\le\), \(>\), \(\ge\) — comparisons. Examples: \(3 < 5\), \(7 \ge 7\).
- \(\mid\) — “divides”: \(a \mid b\) if and only if (\(\iff\)) \(\exists\,k \in \mathbb{N}: b = a k\). Example: \(3 \mid 12\) because \(12 = 3\cdot 4\).
- \(\nmid\) — “does not divide.” Example: \(5 \nmid 12\) since no whole number times 5 equals 12.
- \(\exists\) — “there exists.” Example: \(\exists k \in \mathbb{N}\) such that \(12 = 3k\) (namely \(k=4\)).
- \(\Longrightarrow\) — “implies” or “if … then ….” Example: \(p \nmid n \;\Longrightarrow\; \gcd(p,n)=1\) means “If \(p\) does not divide \(n\), then the gcd of \(p\) and \(n\) is 1.”
- \(n^2\), \(n^3\) — powers: “\(n\) squared,” “\(n\) cubed.” Example: \(4^2 = 16\), \(2^3 = 8\).
- \(\gcd(a,b)\) — the greatest common divisor of \(a\) and \(b\). Example: \(\gcd(18,30)=6\).
- \(\operatorname{lcm}(a,b)\) — the least common multiple of \(a\) and \(b\). Example: \(\operatorname{lcm}(6,8)=24\).
- Letters \(a,b,c,m,n,k,q,u,v\) — stand for whole numbers (usually integers) in general statements.
How the Definitions Connect
Unit · Def. 1 → Natural Number · Def. 2
↓ classified as
↓ related by
↓ leads to
Perfect Number · Def. 12
Definition 1 (Unit)
The unit is the natural number \(1 \in \mathbb{N}\), the multiplicative identity.
Example: Multiplying by 1 leaves any number unchanged: \(1 \cdot 7 = 7\).
Try it: Multiply any number by 1. What changes?
1·7=7, 1·100=100. Nothing changes. The unit 1 leaves every number unchanged — that is what "multiplicative identity" means.
Def. 2 (Natural number)
A natural number is any element \(n \in \mathbb{N}\), i.e. a finite sum of units:
\[ n = \underbrace{1+1+\dots+1}_{n\ \text{terms}}. \]
In other words: natural numbers are the counting numbers: 1, 2, 3, 4, …
Def. 3 (Part / Divisibility)
For \(a,b \in \mathbb{N},\ a \le b\), \(a\) is a part of \(b\) if \(a \mid b\) (i.e. \(\exists\,k \in \mathbb{N}:\ b = k a\)).
Example: \(4\) is a part of \(12\) because \(12 = 3 \cdot 4\). But 5 is not a part of 12.
Def. 4 (Multiple)
For \(a,b \in \mathbb{N}\), \(a\) is a multiple of \(b\) if \(b \mid a\).
Example: 12 is a multiple of 4, since \(4 \mid 12\).
Def. 5 (Prime number)
A number \(p \in \mathbb{N},\ p>1\), is prime if its only divisors are \(1\) and \(p\).
Examples: 2, 3, 5, 7 are prime. 6 is not, because \(6 = 2 \cdot 3\).
Try it: Is 91 prime? Show your reasoning.
91 = 7 × 13. It has divisors other than 1 and itself, so 91 is composite, not prime.
Def. 6 (Composite number)
A number \(n \in \mathbb{N},\ n>1\), is composite if \(\exists\, a,b \in \mathbb{N}\) with \(1 < a < n\) such that \(n = a b\).
Examples: 4, 6, 8, 9, 10 … are composite because they can be written as a product of smaller numbers.
Def. 7 (Coprime numbers)
Numbers \(a,b \in \mathbb{N}\) are coprime if their only common divisor is \(1\).
Example: 8 and 15 are coprime, since no number greater than 1 divides both. But 8 and 12 are not, because both are divisible by 4.
Try it: Are 8 and 15 coprime?
Divisors of 8: 1,2,4,8. Divisors of 15: 1,3,5,15. Only shared divisor is 1. Yes — coprime.
Def. 8 (Even and odd)
A number \(n \in \mathbb{N}\) is even if \(2 \mid n\).
A number \(n \in \mathbb{N}\) is odd if \(2 \nmid n\), equivalently \(n = 2k + 1\) for some \(k \in \mathbb{N}\).
Examples: 2, 4, 6, 8 are even; 1, 3, 5, 7 are odd.
Try it: Is 17 odd? Express it in the form 2k+1.
17 = 2·8+1, so k=8. Yes, 17 is odd.
(b) Challenge: Write two odd numbers as \(2k+1\) and \(2m+1\), add them, and simplify. Is the sum even or odd? Which proposition does this foreshadow?
\((2k+1)+(2m+1) = 2k+2m+2 = 2(k+m+1)\). Divisible by 2, so the sum is always even. This is exactly Proposition 19: the sum of two odd numbers is even.
(c) Extension: Proposition 23 states that the sum of the first \(n\) odd numbers equals \(n^2\). Verify for \(n=1,2,3,4\), then explain geometrically why each new odd number grows a square array of dots by exactly one row and one column.
\(n=1\): \(1=1^2\). \(n=2\): \(1+3=4=2^2\). \(n=3\): \(1+3+5=9=3^2\). \(n=4\): \(1+3+5+7=16=4^2\). Geometrically: an \(n\times n\) square has \(n^2\) dots. Adding the next odd number \(2n+1\) places \(n\) dots along one new edge and \(n+1\) along the adjacent edge, forming an L-shaped border — exactly \(2n+1\) new dots — which completes an \((n+1)\times(n+1)\) square.
Def. 9 (Successor / Predecessor)
For \(a,b \in \mathbb{N}\): the successor of \(b\) is \(a=b+1\); the predecessor of \(b\) is \(a=b-1\).
Example: The successor of 7 is 8. The predecessor of 7 is 6.
Def. 10 (Square number)
A square number is any \(n \in \mathbb{N}\) of the form \(n = m^2\) with \(m \in \mathbb{N}\).
Examples: 1, 4, 9, 16, 25 … These are areas of square arrays of dots: \(3^2 = 9\) makes a 3-by-3 square.
Def. 11 (Cube number)
A cube number is any \(n \in \mathbb{N}\) of the form \(n = m^3\) with \(m \in \mathbb{N}\).
Examples: 1, 8, 27, 64 … These can be arranged into cubes: \(3^3 = 27\) little cubes make a 3-by-3-by-3 cube.
Def. 12 (Least common multiple)
The least common multiple of \(a_1, a_2, \dots, a_n \in \mathbb{N}\) is the least \(m \in \mathbb{N}\) such that \(a_i \mid m\) for all \(i\).
Function (Func.) 1
The greatest common divisor of two positive integers \(a,b\), written \(\gcd(a,b)\), is the largest positive integer that divides both \(a\) and \(b\).
Input / Output
- Input: two integers \(a,b > 0\)
- Output: the largest integer \(d\) such that \(d \mid a\) and \(d \mid b\)
Examples
- \(\gcd(18,30) = 6\)
- \(\gcd(15,28) = 1\)
Try it: Find gcd(24,36) by listing all common divisors.
Divisors of 24: 1,2,3,4,6,8,12,24. Divisors of 36: 1,2,3,4,6,9,12,18,36. Common: 1,2,3,4,6,12. Greatest: 12.
Proposition (Prop.) 1
If two numbers have no common divisor greater than 1, then the process of repeatedly subtracting the smaller from the larger eventually produces a remainder equal to 1.
Elements VII.1 Let \(A,B\) be positive integers. If no number greater than \(1\) divides both, then the process of repeatedly subtracting the smaller from the larger eventually produces a remainder equal to \(1\).
Example with 15 and 28:
- 28 − 15 = 13
- 15 − 13 = 2
- 13 − 2 = 11
- 11 − 2 = 9
- 9 − 2 = 7
- 7 − 2 = 5
- 5 − 2 = 3
- 3 − 2 = 1
The process ends at 1. Hence \(\gcd(15,28)=1\).
Proof
Let \(A > B > 0\). Subtract the smaller from the larger to obtain a remainder \(R_1\) with \(0 < R_1 < B\). Next subtract \(R_1\) from \(B\) to obtain \(R_2\), and continue in this way, always subtracting the smaller from the larger.
Suppose some number \(D > 1\) divides both \(A\) and \(B\). Then it must also divide their difference, so \(D \mid R_1\). Repeating the same reasoning at each step gives \(D \mid R_2\), and so on. Therefore \(D\) would divide the final remainder.
But the final remainder is 1, and no number greater than 1 divides 1. This is impossible. Therefore no number greater than 1 divides both \(A\) and \(B\), and the subtraction process must end at 1. Thus \(\gcd(A,B)=1\). Q.E.D.
Try it: Show that gcd(8,15)=1 using the subtraction method.
15−8=7, 8−7=1. We reached 1, so gcd(8,15)=1.
Prop. 2
If, during the subtraction process, a remainder divides the one just before it, then that remainder is the greatest common divisor of the two numbers.
Elements VII.2 Let \(A,B\) be positive integers with \(A > B\). Perform the process of repeatedly subtracting the smaller from the larger to obtain successive remainders \(R_1, R_2, \dots\). If at some step a remainder divides the one just before it, then the process stops, and that remainder is the greatest common divisor: \[ \gcd(A,B)=R_k. \]
Example with 84 and 30:
- 84 − 30 = 54
- 54 − 30 = 24
- 30 − 24 = 6
- 24 − 6 = 18
- 18 − 6 = 12
- 12 − 6 = 6
At the last step, the remainder 6 divides the previous number 12, so the process stops. Hence \(\gcd(84,30) = 6\).
Proof
Let \(A > B > 0\), and by subtracting the smaller from the larger obtain remainders \(R_1, R_2, \dots, R_{k-1}, R_k\) with \[ A = q_0 B + R_1,\; B = q_1 R_1 + R_2,\; \dots,\; R_{k-2} = q_{k-2} R_{k-1} + R_k, \] and each remainder smaller than the one before it.
Suppose \(R_{k-1} = mR_k\) for some integer \(m \ge 1\). Then from \(R_{k-2} = q_{k-2}R_{k-1} + R_k\), substituting \(R_{k-1}=mR_k\) gives \(R_{k-2} = (q_{k-2}m+1)R_k\). So \(R_k\) divides \(R_{k-2}\).
Repeating this reasoning step by step upward shows that \(R_k\) divides each of \(R_{k-3}, R_{k-4}, \dots, B\), and \(A\). Hence \(R_k\) is a common divisor of \(A\) and \(B\).
Now let \(D\) be any common divisor of \(A\) and \(B\). Then \(D\) divides \(R_1 = A - q_0B\). Similarly, \(D\) divides \(R_2 = B - q_1R_1\), and so on, until finally \(D \mid R_k\).
Thus every common divisor of \(A\) and \(B\) also divides \(R_k\). Therefore \(R_k\) is the greatest common divisor. Q.E.D.
Try it: Use subtraction on gcd(84,30). Where does it stop?
84−30=54, 54−30=24, 30−24=6, 24−6=18, 18−6=12, 12−6=6. Now 6|6, so gcd=6.
Prop. 3
If \(A\) divides \(B\), and \(B\) divides \(C\), then \(A\) also divides \(C\).
Elements VII.3 If a number \(A\) divides a number \(B\), and \(B\) divides a number \(C\), then \(A\) also divides \(C\).
Example: 2 divides 6, and 6 divides 18. Therefore 2 divides 18.
Proof
Let \(A \mid B\) and \(B \mid C\). Then there exist integers \(m,n > 0\) such that \(B = mA\) and \(C = nB\).
Substituting the first into the second gives \(C = n(mA) = (nm)A\). Therefore \(A \mid C\). Q.E.D.
Try it: If 3|12 and 12|60, what does Prop. 3 conclude? Verify.
3|60 by transitivity. Check: 60=3·20. ✓
(b) Challenge: Suppose \(a \mid b\), \(b \mid c\), and \(c \mid d\). Does it follow that \(a \mid d\)? Apply Proposition 3 twice and write out the full chain of reasoning.
Apply Prop. 3 to \(a\mid b\) and \(b\mid c\): we get \(a\mid c\). Apply Prop. 3 again to \(a\mid c\) and \(c\mid d\): we get \(a\mid d\). Transitivity chains indefinitely — any divisor at the top of a chain divides everything below it.
(c) Extension: If \(a \mid b\) and \(b \nmid c\), does it follow that \(a \nmid c\)? Prove it or find a counterexample.
False — it does not follow. Counterexample: \(a=2\), \(b=6\), \(c=4\). Then \(2\mid 6\) and \(6\nmid 4\), yet \(2\mid 4\). Proposition 3 only guarantees that if both links in a chain hold, the shortcut holds too. Breaking one link does not mean the endpoint is unreachable by another route.
Prop. 4
If \(A\) divides both \(B\) and \(C\), then \(A\) divides their difference \(B-C\).
Elements VII.4 If a number \(A\) divides a number \(B\) and also divides a number \(C\), then \(A\) divides their difference \(B-C\), provided \(B > C\).
Example: 7 divides 35 and 7 divides 21. Then 7 also divides their difference 14.
Proof
Let \(A \mid B\) and \(A \mid C\), with \(B > C\). Then there exist integers \(m,n > 0\) such that \(B=mA\) and \(C=nA\).
Subtracting, we obtain \(B-C = mA - nA = (m-n)A\). Hence \(A \mid (B-C)\). Q.E.D.
Try it: You know 6|30 and 6|18. Does 6 divide 30−18?
30−18=12=6·2. Yes, 6|12. ✓
Prop. 5
If \(A\) divides both \(B\) and \(C\), then \(A\) divides \(mB+nC\) for any integers \(m,n\).
Elements VII.5 If a number \(A\) divides a number \(B\) and also divides a number \(C\), then for any integers \(m,n\), the number \(A\) also divides the combination \(mB + nC\).
Example: 5 divides both 20 and 35. Then 5 divides \(20+35=55\), and also divides \(2\cdot 20 - 35 = 5\).
Proof
Let \(A \mid B\) and \(A \mid C\). Then there exist integers \(p,q > 0\) such that \(B = pA\) and \(C = qA\).
For any integers \(m,n\), we have \[ mB + nC = m(pA) + n(qA) = (mp+nq)A. \] Thus \(A \mid (mB+nC)\). Q.E.D.
Try it: Given 3|9 and 3|15, compute 4·9−2·15. Does 3 divide the result?
4·9−2·15=36−30=6=3·2. Yes, 3|6. ✓
Prop. 6
If \(A\) divides \(B\), then \(A\) divides every multiple of \(B\).
Elements VII.14 If a number \(A\) divides a number \(B\), then \(A\) also divides every multiple of \(B\).
Example: 6 divides 24. Then 6 also divides any multiple of 24, such as 48 or 72.
Proof
Let \(A \mid B\). Then there exists an integer \(m \ge 1\) such that \(B = mA\).
For any integer \(k \ge 1\), consider the multiple \(kB\). Substituting, \(kB = k(mA) = (km)A\). Since \(km\) is an integer, it follows that \(A \mid kB\). Q.E.D.
Try it: If 5|20, does 5 divide 4·20=80?
80=5·16. Yes — any multiple of 20 is also divisible by 5.
Prop. 7
For any positive integers \(m,n\), the product is the same whichever number multiplies the other: \(mn = nm\).
Elements VII.16 For any positive integers \(m,n\), the product is the same whichever number multiplies the other: \[ mn = nm. \]
Example: 3 rows of 4 dots makes 12 dots. 4 rows of 3 dots also makes 12 dots.
Proof
Let \(m,n\) be positive integers. Consider a rectangular array of objects arranged in \(m\) rows and \(n\) columns. Counting by rows gives a total of \(mn\), since each of the \(m\) rows contains \(n\) objects.
Likewise, counting by columns gives a total of \(nm\). Both counts describe the same collection, so \(mn = nm\). Q.E.D.
Try it: Verify 6×8=8×6 without multiplying. Imagine a dot array.
6 rows of 8 dots = 48. Rotate the array: 8 rows of 6 dots = 48. Same total.
Algorithm 1
The Euclidean Algorithm for the greatest common divisor (gcd).
Elements VII.12 To find the greatest common divisor of two numbers, repeatedly divide the larger by the smaller. Replace the larger number by the smaller, and the smaller by the remainder. Continue until the remainder is 0. The last nonzero divisor is the greatest common divisor: \[ \gcd(A,B) = \gcd(B,R) \quad \text{when } A = qB + R, \; 0 \le R < B. \]
Example: find the greatest common divisor of 119 and 34.
- Divide 119 by 34: \(119 = 3\cdot 34 + 17\). The remainder is 17.
- Now divide 34 by 17: \(34 = 2\cdot 17 + 0\). The remainder is 0.
The last nonzero divisor is 17. Thus \(\gcd(119,34) = 17\).
Proof
Let two numbers \(A,B\) be given with \(A > B > 0\). Divide \(A\) by \(B\) to obtain \(A = qB + R\) with remainder \(0 \le R < B\).
Every common divisor of \(A\) and \(B\) also divides their difference \(A - qB = R\). Therefore the common divisors of \(A\) and \(B\) are exactly the same as the common divisors of \(B\) and \(R\).
If \(R \ne 0\), repeat the division: divide \(B\) by \(R\) to obtain a new remainder. At each step, the set of common divisors does not change.
The remainders get smaller at every step, so the process cannot go on forever. It must eventually reach a remainder of 0.
At that point, the last nonzero divisor is greater than any other common divisor, so it is the greatest common divisor of the original numbers \(A\) and \(B\). Q.E.D.
Try it: Apply the Euclidean Algorithm to find gcd(56,98).
98=1·56+42; 56=1·42+14; 42=3·14+0. Last nonzero remainder: gcd(56,98)=14.
(b) Challenge: Use Algorithm 1 to find \(\gcd(252, 360)\), then express both 252 and 360 as multiples of their gcd.
360=1·252+108; 252=2·108+36; 108=3·36+0. So \(\gcd(252,360)=36\). Then \(252=36\cdot 7\) and \(360=36\cdot 10\).
(c) Extension: Why must the Euclidean Algorithm always terminate in a finite number of steps? Write a brief argument using the fact that each remainder is strictly smaller than the previous one.
At each step the remainder \(r\) satisfies \(0 \le r < \text{divisor}\). So the sequence of remainders is a strictly decreasing sequence of non-negative integers. A strictly decreasing sequence of non-negative integers must reach 0 in finitely many steps — in fact, in at most \(b\) steps where \(b\) is the smaller of the two original numbers. Therefore the algorithm always terminates.
Prop. 8
If two numbers are coprime, then a whole-number combination of them equals 1.
Let \(a,b\) be positive integers with \(\gcd(a,b)=1\). Then there exist integers \(u,v\) such that \[ ua + vb = 1. \]
Proof
Apply Algorithm 1 to \(a,b\). Each remainder can be expressed as a linear combination of \(a\) and \(b\). Back-substituting step by step shows that the last nonzero remainder, which is 1 (since \(\gcd(a,b)=1\)), can be written in the form \(ua+vb\).
Therefore there exist integers \(u,v\) with \(ua+vb=1\). Q.E.D.
Try it: Find integers u,v such that 3u+5v=1 (Bézout coefficients).
u=2, v=−1: 3·2+5·(−1)=6−5=1. ✓
Prop. 9
If a prime \(p\) does not divide \(n\), then \(\gcd(p,n) = 1\).
Elements VII.29 If a prime number \(p\) does not divide a number \(n\), then the only common divisor of \(p\) and \(n\) is \(1\). In other words: \[ p \nmid n \;\;\Longrightarrow\;\; \gcd(p,n) = 1. \]
Example: let \(p=7\) and \(n=20\). The prime 7 does not divide 20. The only number that divides both is 1.
Proof
Let \(p\) be prime, and suppose \(p\) does not divide \(n\). Imagine that some number \(d\) greater than 1 divides both \(p\) and \(n\).
Because \(d\) divides \(p\) and \(p\) is prime, the only possibilities are \(d=1\) or \(d=p\). But we assumed \(d > 1\), so \(d\) must equal \(p\).
This would mean that \(p\) divides \(n\), which contradicts our assumption. Therefore no number greater than 1 divides both \(p\) and \(n\). So their greatest common divisor is 1. Q.E.D.
Try it: Does 7 divide 22? What is gcd(7,22)?
7∤22 (22=3·7+1). By Prop. 9, gcd(7,22)=1.
(b) Challenge: Use Prop. 9 together with Prop. 10 (Euclid's Lemma) to prove: if \(p=5\) is prime and \(5 \mid nm\) where \(5 \nmid n\), then \(5 \mid m\). Write out each step by name.
Step 1 — Prop. 9: since \(p=5\) is prime and \(5\nmid n\), we have \(\gcd(5,n)=1\). Step 2 — Prop. 10 (Euclid's Lemma): if a prime \(p\) divides a product \(nm\) and \(\gcd(p,n)=1\), then \(p\mid m\). Therefore \(5\mid m\). These two propositions together are the key engine behind unique prime factorisation.
(c) Extension: Proposition 9 specifically requires \(p\) to be prime. Find a counterexample with a composite number: give a composite \(c\) and a number \(n\) such that \(c\nmid n\) yet \(\gcd(c,n)>1\).
Take \(c=6\), \(n=4\). Then \(6\nmid 4\), but \(\gcd(6,4)=2>1\). The composite number 6 shares the factor 2 with 4 even though 6 does not divide 4. Primeness is essential: a prime's only proper divisor is 1, so the only way \(d>1\) can divide both \(p\) and \(n\) is \(d=p\), forcing \(p\mid n\). No such argument works for composites.
Prop. 10
Euclid's Lemma. If a prime \(p\) divides the product \(mn\), then \(p\) divides \(m\) or \(p\) divides \(n\).
Elements VII.30 Let \(p\) be a prime number and let \(m,n\) be positive integers. If \(p\) divides the product \(mn\), then \(p\) divides \(m\) or \(p\) divides \(n\): \[ p \mid mn \;\Longrightarrow\; (\,p \mid m\,)\ \text{or}\ (\,p \mid n\,). \]
For example, take \(p=5\). If \(5\) divides the product \(12 \cdot 25\), then it must divide one of the two numbers. Indeed, \(5\) divides 25.
Proof
Suppose a prime \(p\) divides the product \(mn\). If \(p\) also divides \(m\), the statement is true and we are done. So let us assume that \(p\) does not divide \(m\).
In that case, \(p\) and \(m\) have no common divisor greater than 1 (by Proposition 8). This means their greatest common divisor is 1.
From Prop. 8, there are whole numbers \(u\) and \(v\) such that \[ up + vm = 1. \] (This is a general fact: whenever two numbers have gcd = 1, a combination of them can be written to equal 1.)
Multiply this equation by \(n\): \[ unp + vmn = n. \] Since \(p\) divides both terms on the left (\(unp\) and \(vmn\)), it must also divide their sum. Therefore \(p\) divides \(n\).
So if a prime divides a product, it must divide one of the two numbers. Q.E.D.
Try it: 5 divides the product 3×25. Which factor does 5 divide?
5|25 since 25=5·5. (5 does not divide 3.)
Prop. 11
If two numbers have no common divisor greater than 1, then their least common multiple is their product: \(\operatorname{lcm}(m,n) = mn\).
Elements VII.20 If two numbers \(m,n\) have no common divisor greater than \(1\), then their least common multiple is their product: \[ \gcd(m,n)=1 \;\Longrightarrow\; \operatorname{lcm}(m,n)=mn. \]
Example: take \(m=8\) and \(n=15\). No number greater than 1 divides both. Their product is \(8\cdot 15 = 120\). Since both 8 and 15 divide 120, and any other common multiple must also be divisible by 120, the least common multiple is 120.
Proof
Suppose \(\gcd(m,n)=1\). Then the product \(mn\) is clearly a common multiple, since \(m \mid mn\) and \(n \mid mn\).
Let \(L\) be any common multiple of \(m\) and \(n\). Then \(L = ma = nb\) for some whole numbers \(a\) and \(b\). We will show that \(mn \mid L\).
Since \(\gcd(m,n)=1\), Prop. 8 gives whole numbers \(u,v\) such that \[ um + vn = 1. \]
Multiply by \(a\): \[ uam + van = a. \] Now \(m \mid uam\) trivially. And since \(L = ma\) and \(n \mid L\), it follows that \(n \mid ma\), so \(n \mid van\).
Therefore both terms on the left are divisible by \(n\), which means \(n \mid a\). So \(a = nk\) for some whole number \(k\).
Substituting back, \(L = ma = m(nk) = (mn)k\). Thus \(mn \mid L\).
Every common multiple of \(m\) and \(n\) is divisible by \(mn\), and since \(mn\) itself is a common multiple, it is the least such. Hence \(\operatorname{lcm}(m,n) = mn\). Q.E.D.
Try it: gcd(8,9)=1. Find lcm(8,9) using Prop. 11.
Since 8 and 9 are coprime, lcm(8,9)=8·9=72.
Function 2
Elements VII.34 For any two positive integers \(m,n\), the least common multiple can be found from their product and their greatest common divisor: \[ \operatorname{lcm}(m,n) = \frac{mn}{\gcd(m,n)}. \]
Example: take \(m=18\) and \(n=24\). Their product is \(18\cdot 24 = 432\). Their greatest common divisor is \(\gcd(18,24) = 6\). Divide the product by the gcd: \(432 \div 6 = 72\). Both 18 and 24 divide 72, so \(\operatorname{lcm}(18,24) = 72\).
Proof
Let \(d = \gcd(m,n)\). Write \(m = d m_1\) and \(n = d n_1\), where \(\gcd(m_1,n_1)=1\).
Then the product is \(mn = d^2 m_1 n_1\). Divide by \(d\): \[ \frac{mn}{d} = d m_1 n_1. \]
This number is divisible by both \(m = d m_1\) and \(n = d n_1\), since \(dm_1 \mid d m_1 n_1\) and \(dn_1 \mid d m_1 n_1\).
By Proposition 11, the least common multiple of \(m_1\) and \(n_1\) is \(m_1 n_1\). Therefore the least common multiple of \(m\) and \(n\) is \[ d \cdot m_1 n_1 = \frac{mn}{d}. \]
Hence \[ \operatorname{lcm}(m,n) = \frac{mn}{\gcd(m,n)}. \] Q.E.D.
Try it: Find lcm(12,18) using the formula lcm=mn/gcd.
gcd(12,18)=6. lcm=12·18/6=216/6=36.
2 Proportion
Glossary of Symbols
- \(\dfrac{a}{b} = \dfrac{c}{d}\) — equality of ratios; the ratio of \(a\) to \(b\) equals the ratio of \(c\) to \(d\). Equivalent to \(ad = bc\) (with \(b,d \neq 0\)). Example: \(2/3 = 4/6\) since \(2\cdot 6 = 3\cdot 4\).
- \(a:b = c:d\) — colon notation for equal ratios; interchangeable with fraction notation. Example: \(2:4 = 3:6\).
- \(a:b = b:c\) — three numbers in continued proportion (with \(b\) the mean proportional). Equivalent to \(b^2 = ac\). Example: \(2:6 = 6:18\) and \(6^2 = 2\cdot 18\).
- \(a:b = b:c = c:d\) — four numbers in continued proportion, i.e. a geometric progression of four terms. Example: \(1:2 = 2:4 = 4:8\).
- \(x^2\) — square of \(x\), i.e. \(x\cdot x\). Example: \(5^2 = 25\).
- \(x^3\) — cube of \(x\), i.e. \(x\cdot x \cdot x\). Example: \(3^3 = 27\).
- \(a, ar, ar^2, ar^3, \ldots\) — a geometric progression with first term \(a\) and common ratio \(r\). Example: \(2, 6, 18, 54,\ldots\) with \(a=2\), \(r=3\).
- \(\dfrac{a}{b}=\dfrac{c}{d} \;\Longrightarrow\; \dfrac{a}{c}=\dfrac{b}{d}\) — alternation (alternendo); from equal ratios, the alternated ratios are equal (Prop. 15).
- \(\dfrac{a}{b}=\dfrac{c}{d} \;\Longrightarrow\; \dfrac{b}{a}=\dfrac{d}{c}\) — inversion (invertendo); from equal ratios, the inverted ratios are equal (Prop. 16).
Prop. 12
Proportional numbers remain proportional when multiplied by the same factor.
Elements VIII.1 If four numbers are proportional, then their like multiples are also proportional. That is, if \[ \frac{a}{b} = \frac{c}{d}, \] then for any positive integer \(k\), \[ \frac{ka}{kb} = \frac{kc}{kd}. \]
Suppose \(2:4 = 3:6\). If we double every number, we get \(4:8 = 6:12\). The equality of ratios stays true after multiplying all numbers by the same factor.
Proof
Let \(\tfrac{a}{b} = \tfrac{c}{d}\). By definition of proportion, \(ad = bc\).
Multiply each of \(a,b,c,d\) by the same positive integer \(k\). Then \[ (ka)(kd) = k^2 (ad), \qquad (kb)(kc) = k^2 (bc). \]
Since \(ad = bc\), it follows that \((ka)(kd) = (kb)(kc)\). Therefore \(\tfrac{ka}{kb} = \tfrac{kc}{kd}\).
Thus, if four numbers are proportional, their like multiples are also proportional. Q.E.D.
Try it: Is 2:6=6:18 a valid proportion? Check by cross-multiplication.
2·18=36 and 6·6=36. Equal, so yes — a valid proportion.
(b) Challenge: The alternendo rule (Prop. 15) says: if \(a:b=c:d\) then \(a:c=b:d\). Starting from \(3:6=5:10\), verify the original proportion and the alternendo result by cross-multiplication.
Original \(3:6=5:10\): cross-multiply \(3\cdot 10=30\) and \(6\cdot 5=30\). ✓ Alternendo gives \(3:5=6:10\): cross-multiply \(3\cdot 10=30\) and \(5\cdot 6=30\). ✓ Swapping "outer" and "inner" terms preserves the equality of ratios.
(c) Extension: A perfect fifth in music is the ratio \(3:2\). Starting from 1, form a continued proportion with ratio \(3:2\): the terms are \(1, \tfrac{3}{2}, \tfrac{9}{4}\). Why are these not whole numbers? What does this tell you about why a piano cannot be perfectly in tune in every key?
The continued proportion \(1:\tfrac{3}{2}=\tfrac{3}{2}:\tfrac{9}{4}\) uses non-integer terms because 3 and 2 are coprime — no power of \(\tfrac{3}{2}\) is also a power of 2. After 12 perfect fifths the ratio reached is \(\tfrac{3^{12}}{2^{19}}=\tfrac{531441}{524288}\approx 1.0136\), which is not 1. So 12 fifths do not return exactly to the starting pitch — the slight gap is called the Pythagorean comma. Equal temperament resolves it by slightly shrinking each fifth, sacrificing exact integer ratios for universal playability.
Algo. 2
Elements VIII.2 Given two numbers, to find a third so that the three are in continued proportion. That is, given \(a\) and \(b\), find \(c\) such that \[ \frac{a}{b} = \frac{b}{c}. \]
Suppose the first two numbers are \(a = 2\) and \(b = 6\). To extend the sequence, we want a third number \(c\) so that \(2:6 = 6:c\).
Cross-multiplying gives \(2c = 36\), so \(c = 18\). Thus the three numbers \(2,6,18\) are in continued proportion. In modern terms, this is just a geometric progression.
Proof
Let two numbers \(a,b\) be given. We seek a number \(c\) such that \(\tfrac{a}{b} = \tfrac{b}{c}\).
By the definition of proportion, this condition is equivalent to \[ ac = b^2. \]
Solve for \(c\): let \(c = \tfrac{b^2}{a}\). Then indeed \(ac = b^2\), so \(\tfrac{a}{b} = \tfrac{b}{c}\).
Therefore the three numbers \(a,b,c\) are in continued proportion. Q.E.D.
Try it: Construct a continued proportion between 4 and 16.
We need x: 4:x=x:16, so x²=64, x=8. Proportion: 4, 8, 16.
Prop. 13
Elements VIII.4 If there are three numbers in continued proportion, then it is possible to find as many more as one wishes in the same continued proportion. That is, if \[ \frac{a}{b} = \frac{b}{c}, \] then further numbers \(d,e,\dots\) can be found so that \[ \frac{b}{c} = \frac{c}{d} = \frac{d}{e} = \dots \]
Suppose we already have three numbers in continued proportion: \(2,6,18\). Then we can continue: after \(18\), the next is \(54\), then \(162\), and so on. Each step multiplies by the same ratio, here by \(3\).
In modern words, once you have a geometric progression, you can keep extending it by multiplying again by the same ratio.
Proof
Let \(a,b,c\) be in continued proportion, so that \(a:b = b:c\). Then by the definition of proportion, \[ b^2 = ac. \]
To find a fourth proportional, take \(d\) such that \(b:c = c:d\). This means \(bd = c^2\). Then the four numbers \(a,b,c,d\) are in continued proportion.
Repeating this step shows that a fifth proportional \(e\) may be constructed so that \(c:d = d:e\), and so on indefinitely.
Therefore, if three numbers are in continued proportion, more numbers in the same continued proportion can always be produced. Q.E.D.
Try it: Extend the proportion 1:2:4 by one more term.
Ratio is 2. Next term: 4·2=8. Four-term proportion: 1, 2, 4, 8.
Prop. 14
Elements VIII.6 If four numbers are proportional, then the products of corresponding multiples of them are also proportional. That is, if \[ \frac{a}{b} = \frac{c}{d}, \] then for any positive integers \(m,n\), \[ \frac{ma}{nb} = \frac{mc}{nd}. \]
Suppose \(2:4 = 3:6\). Multiply the first pair by \(2\) and the second pair by \(3\). Then we have \(4:12 = 6:18\).
The proportion is preserved even after multiplying the numbers by other whole numbers.
Proof
Let \(\tfrac{a}{b} = \tfrac{c}{d}\). Then by the definition of proportion, \[ ad = bc. \]
Multiply \(a\) and \(c\) by \(m\), and \(b\) and \(d\) by \(n\). We obtain \[ (ma)(nd) = mn(ad), \quad (nb)(mc) = mn(bc). \]
Since \(ad = bc\), it follows that \((ma)(nd) = (nb)(mc)\). Therefore \(\tfrac{ma}{nb} = \tfrac{mc}{nd}\).
Hence, proportionality is preserved when the terms are multiplied by like or unlike factors. Q.E.D.
Try it: In the proportion 2:4=4:8, multiply means by 3: is 2:12=4:24 still valid?
2·24=48 and 12·4=48. Yes, the proportion holds.
Prop. 15
Elements VIII.7 If four numbers are proportional, then the first is to the third as the second is to the fourth. That is, if \[ \frac{a}{b} = \frac{c}{d}, \] then \[ \frac{a}{c} = \frac{b}{d}. \]
Suppose \(2:4 = 3:6\). Then comparing the first terms to the third terms and the second to the fourth, we get \(2:3 = 4:6\). In other words, once two ratios are equal, you may “alternate” them and the equality of ratios is preserved.
Proof
Let \(\tfrac{a}{b} = \tfrac{c}{d}\). By the definition of proportion, \(ad = bc\).
Since \(ad = bc\) with \(a,c,d,b > 0\), divide both sides by \(cd\) to obtain \[ \frac{a}{c} = \frac{b}{d}. \]
Therefore, from equal ratios the alternated ratios are also equal. Q.E.D.
Try it: In 2:4=6:12, apply alternendo to get the alternate proportion.
Alternendo: 2:6=4:12. Check: 2·12=24=6·4. ✓
Prop. 16
Elements VIII.8 If four numbers are proportional, then they will also be proportional when inverted. That is, if \[ \frac{a}{b} = \frac{c}{d}, \] then \[ \frac{b}{a} = \frac{d}{c}. \]
Suppose \(2:4 = 3:6\). Then it also follows that \(4:2 = 6:3\). In other words, if two ratios are equal, then their “turned upside down” versions are also equal.
Proof
Let \(\tfrac{a}{b} = \tfrac{c}{d}\). By the definition of proportion, \(ad = bc\).
Dividing both sides by \(ab\), we obtain \[ \frac{d}{b} = \frac{c}{a}. \] Rearranging gives \[ \frac{b}{a} = \frac{d}{c}. \]
Therefore, if four numbers are proportional, their inverted ratios are also equal. Q.E.D.
Try it: In 2:4=6:12, apply invertendo.
Invertendo: 4:2=12:6. Both ratios equal 2. ✓
Prop. 17
Elements VIII.22 If three numbers are in continued proportion, and the first is a square number, then the third is also a square number. That is, if \[ \frac{a}{b} = \frac{b}{c} \] and \(a = x^2\) for some integer \(x\), then \(c = y^2\) for some integer \(y\).
Suppose \(a = 4\), which is a square, and let the numbers be in continued proportion: \(4 : 12 = 12 : 36\). Here the third number is \(36\), which is also a square (\(6^2\)). In general, whenever the first number in a chain of three proportional numbers is square, the third will also be square.
Proof
Suppose \(a,b,c\) are in continued proportion, so that \(a:b=b:c\). Reduce the ratio \(a:b\) to lowest terms \(p:q\) with \(\gcd(p,q)=1\). Then there exists an integer \(s\) such that \[ a = p^2 s,\quad b = p q s,\quad c = q^2 s. \]
If \(a\) is a square, say \(a=x^2\), then \(p^2 s = x^2\). Because \(p^2\) is a square, this means \(s\) must also be a square, say \(s=z^2\).
Substituting back, \(c = q^2 s = q^2 z^2 = (qz)^2\), which is a square.
Therefore, if the first of three continued proportionals is square, then the third is also square. Q.E.D.
Try it: In the continued proportion 1:2:4:8, is the first term (1) a square? What about the fourth (8)?
1=1². By Prop. 17, the fourth must also be a square. But 8 is not a perfect square! Check: Prop. 17 requires a 3-term proportion a:b=b:c. The 4-term case gives d=q³s — a cube, not a square (see Prop. 18). Try instead 1:3:9: first=1², fourth would need a 4-term version.
Prop. 18
Elements VIII.23 If four numbers are in continued proportion, and the first is a cube, then the fourth is also a cube. That is, if \[ \frac{a}{b}=\frac{b}{c}=\frac{c}{d} \] and \(a=x^3\) for some integer \(x\), then there exists an integer \(y\) with \(d=y^3\).
Think of a geometric progression with four terms: \(a, ar, ar^2, ar^3\). If the first term \(a\) is a cube, say \(x^3\), then the fourth term is \(ar^3 = x^3 r^3 = (xr)^3\), which is also a cube.
Example: \(1, 2, 4, 8\) are in continued proportion (each step doubles). The first is \(1=1^3\), and the fourth \(8=2^3\) is a cube as well.
Proof
Let \(a,b,c,d\) be in continued proportion, so \(a:b=b:c=c:d\). Then \(b\) is a mean proportional between \(a\) and \(c\), and \(c\) is a mean proportional between \(b\) and \(d\); hence \[ b^2=ac \quad\text{and}\quad c^2=bd. \]
Reduce the ratio \(a:b\) to lowest terms \(p:q\) (with \(p,q\) having no common divisor greater than \(1\)). Since \(a:b=b:c=c:d=p:q\), there exist integers \(t,u,v\) such that \[ a=pt,\quad b=qt;\qquad b=pu,\quad c=qu;\qquad c=pv,\quad d=qv. \] From \(b=qt=pu\) and the coprimeness of \(p,q\), it follows that \(t= p\,s\) and \(u= q\,s\) for some integer \(s\). Likewise, from \(c=qu=pv\) and \(\gcd(p,q)=1\), we obtain \(v= q^2 s\).
Substituting back gives the canonical form for four numbers in continued proportion: \[ a=p^3 s,\qquad b=p^2 q\,s,\qquad c=p q^2 s,\qquad d=q^3 s. \]
Now suppose \(a=x^3\). From \(a=p^3 s=x^3\) it follows that \(s\) is a cube (since \(p^3\) is a cube). Write \(s=z^3\). Then \[ d=q^3 s = q^3 z^3 = (qz)^3, \] which is a cube. Therefore, if the first of four continued proportionals is a cube, the fourth is also a cube. Q.E.D.
Try it: In 1:2:4:8, is 1 a cube? What does Prop. 18 predict about 8?
1=1³. Prop. 18 predicts the fourth term is also a cube. 8=2³. ✓
3 CULMINATION
Glossary of Symbols
- \(2n\) — general form of an even number (twice an integer). Example: \(2\cdot 7 = 14\).
- \(2n+1\) — general form of an odd number (one more than twice an integer). Example: \(2\cdot 5 + 1 = 11\).
- \(\displaystyle \sum\) — summation symbol; denotes the sum of a sequence of terms. Example: \(\displaystyle \sum_{i=1}^{n} (2i-1) = 1+3+5+\cdots+(2n-1)\).
- \(\cdots\) — ellipsis; indicates continuation of a visible pattern in a sum or product. Examples: \(1+3+5+\cdots+(2n-1)\), \(p_1p_2\cdots p_k\).
- \(a_1,a_2,\ldots,a_n\) — subscript notation for a list or sequence of numbers. Example: primes listed as \(p_1,p_2,\ldots,p_k\).
- \(p_1,p_2,\ldots,p_k\) — a finite list of prime numbers (used in Prop. 25). Example: \(p_1=2, p_2=3, p_3=5\).
- \(p_1p_2\cdots p_k\) — product of the listed primes (juxtaposition denotes multiplication). Example: \(2\cdot 3 \cdot 5 = 30\).
- \(a+ar+\cdots+ar^{\,n-1}\) — geometric progression of \(n\) terms with first term \(a\) and ratio \(r\). Equivalent summation: \(\displaystyle \sum_{j=0}^{n-1} ar^{\,j}\).
- \(\displaystyle a+ar+\cdots+ar^{\,n-1}=\frac{ar^{\,n}-a}{r-1}\) — sum of a geometric progression for \(r\neq 1\) (Prop. 27).
- \(2^{k}\), \(2^{k}-1\) — powers of two and the associated Mersenne numbers (used in Prop. 28). Example: \(2^{5}=32\), \(2^{5}-1=31\).
- \(N = 2^{\,k-1}(2^{k}-1)\) — Euclid’s formula for even perfect numbers when \(2^{k}-1\) is prime (Prop. 28). Example: for \(k=3\), \(N=2^{2}(2^{3}-1)=4\cdot 7=28\).
- \(<\), \(\le\), \(>\), \(\ge\) — inequalities: less than, less than or equal, greater than, greater than or equal. Example: \(1<a\le b<n\).
Prop. 19
The sum of two odd numbers is even.
Elements IX.1 If two odd numbers are added together, then the sum is even. That is, if \(a=2m+1\) and \(b=2n+1\), then \[ a+b=2(m+n+1), \] which is even.
Odd numbers are “one more than an even.” For example, \(3=2\cdot1+1\) and \(5=2\cdot2+1\). If you add them, \(3+5=8\), which is even. This always happens: the extra “+1” from each odd number makes a pair, which turns the sum into an even.
Proof
Let two odd numbers be \(a=2m+1\) and \(b=2n+1\) for some integers \(m,n\).
Then their sum is \[ a+b = (2m+1)+(2n+1) = 2(m+n+1). \]
Since \(a+b\) is twice an integer, it is even. Therefore the sum of two odd numbers is even. Q.E.D.
Try it: Show that 7+9=16 is even, using Prop. 19.
7 and 9 are both odd. By Prop. 19, their sum 16 is even. Indeed 16=2·8.
Prop. 20
The sum of an even number and an odd number is odd.
Elements IX.2 If an even number is added to an odd number, then the sum is odd. That is, if \(a=2m\) and \(b=2n+1\), then \[ a+b = 2m + (2n+1) = 2(m+n) + 1, \] which is odd.
Think of an even as “made of pairs,” and an odd as “pairs plus one.” Adding them together still leaves one unpaired unit. For example, \(8\) (even) + \(5\) (odd) = \(13\) (odd).
Proof
Let the even number be \(a=2m\) and the odd number be \(b=2n+1\), for some integers \(m,n\).
Then \[ a+b = 2m + (2n+1) = 2(m+n) + 1. \]
Since \(a+b\) is one more than twice an integer, it is odd. Therefore the sum of an even number and an odd number is odd. Q.E.D.
Try it: Is 6+7 even or odd? Which proposition applies?
6 is even, 7 is odd. By Prop. 20, sum=13 is odd. Check: 13=2·6+1.
Prop. 21
The sum of even numbers is even.
Elements IX.3 If even numbers are added together, their sum is even. That is, if \(a=2m\) and \(b=2n\), then \[ a+b = 2m+2n = 2(m+n), \] which is even.
Even numbers are “made of pairs.” Adding two collections of pairs just makes a bigger collection of pairs. For example, \(8+6=14\), and both numbers (and their sum) are even.
Proof
Let the even numbers be \(a=2m\) and \(b=2n\), for some integers \(m,n\).
Then \[ a+b = 2m+2n = 2(m+n). \]
Since \(a+b\) is twice an integer, it is even. Therefore the sum of even numbers is even. Q.E.D.
Try it: Is 14+8 even? Apply Prop. 21.
Both are even. By Prop. 21, 14+8=22 is even. 22=2·11. ✓
Prop. 22
The sum of an odd number of odd numbers is odd.
Elements IX.23 If an odd number of odd numbers are added together, the sum is odd. That is, for integers \(n_1,\dots,n_{2k+1}\), \[ (2n_1+1) + (2n_2+1) + \cdots + (2n_{2k+1}+1) \;=\; 2\Big(n_1+\cdots+n_{2k+1}+k\Big) + 1, \] which is odd.
Think of odd numbers as “pairs plus one.” When you add an odd count of them, those extra ones cannot all pair up—one remains. Example: \(3+5+7=15\) (odd), or \(1+1+1=3\) (odd). With an odd count of odds, the total is always odd.
Proof
Let there be \(2k+1\) odd numbers, written as \(2n_1+1,\,2n_2+1,\,\dots,\,2n_{2k+1}+1\).
Their sum is \[ \sum_{i=1}^{2k+1} (2n_i+1) \;=\; 2\sum_{i=1}^{2k+1} n_i \;+\; \underbrace{(1+\cdots+1)}_{2k+1\ \text{times}} \;=\; 2\left(\sum_{i=1}^{2k+1} n_i + k\right) + 1. \]
Since the sum is one more than twice an integer, it is odd. Therefore, the sum of an odd number of odd numbers is odd. Q.E.D.
Try it: Add 1+3+5+7+9 (five odd numbers). Is the result odd?
1+3+5+7+9=25. Five is an odd count of odd numbers, so by Prop. 22 the sum is odd. 25 is odd. ✓
Prop. 23
The sum of the first n odd numbers equals a square.
Elements IX.24 The sum of the first \(n\) odd numbers is the square of \(n\). That is, \[ 1 + 3 + 5 + \cdots + (2n-1) = n^2. \]
If you stack dots into growing squares, each new odd number makes the next bigger square. For example:
- \(1 = 1^2\)
- \(1+3=4=2^2\)
- \(1+3+5=9=3^2\)
- \(1+3+5+7=16=4^2\)
Every time you add the next odd number, the figure becomes a larger square. So the sum of the first \(n\) odd numbers is always \(n^2\).
Proof
We prove by induction on \(n\).
Base case: For \(n=1\), the sum is \(1\), and \(1^2=1\).
Inductive step: Assume \[ 1+3+5+\cdots+(2n-1) = n^2. \] Add the next odd number \((2(n+1)-1) = 2n+1\) to both sides: \[ \big(1+3+\cdots+(2n-1)\big) + (2n+1) = n^2 + (2n+1). \] By the induction hypothesis, the left-hand side is the sum of the first \(n+1\) odd numbers. The right-hand side simplifies to \[ n^2 + 2n + 1 = (n+1)^2. \]
Therefore, the sum of the first \(n+1\) odd numbers is \((n+1)^2\). By induction, the result holds for all \(n\).
Thus, \[ 1+3+5+\cdots+(2n-1) = n^2. \] Q.E.D.
Try it: What is 1+3+5+7 using the formula for the sum of the first n odd numbers?
n=4. Sum=4²=16. Verify: 1+3+5+7=16. ✓
Prop. 24
For every integer \(n>1\), either \(n\) is prime, or there exist primes \(p_1,\dots,p_k\) with \(n = p_1p_2\cdots p_k\).
Numbers either are prime (like \(2,3,5,13\)) or can be built by multiplying primes (like \(60=2\cdot2\cdot3\cdot5\)). This statement says every number bigger than \(1\) fits one of those two descriptions.
Proof
Suppose, for contradiction, that there exists an integer \(n>1\) which is neither prime nor a product of primes. Among all such numbers, choose the least and call it \(n\).
Since \(n\) is not prime, it is composite: there exist integers \(a,b\) with \(1<a\le b<n\) and \(n=ab\).
By the minimal choice of \(n\), each of \(a\) and \(b\) (being smaller than \(n\)) must be either prime or a product of primes. In either case, \(a\) is a product of primes, and \(b\) is a product of primes. Therefore their product \(n=ab\) is a product of primes.
This contradicts the assumption that \(n\) is neither prime nor a product of primes. Hence no such \(n\) exists. Therefore every integer \(n>1\) is prime or a product of primes. Q.E.D.
Try it: Express 60 as a product of primes.
60=2·30=2·2·15=2·2·3·5=2²·3·5. Every factor is prime.
(b) Challenge: Express 360 as a product of primes. How many prime factors does it have, counting multiplicity?
\(360=2\cdot 180=2\cdot 2\cdot 90=2\cdot 2\cdot 2\cdot 45=2^3\cdot 3^2\cdot 5\). Counting with multiplicity: \(3+2+1=6\) prime factors.
(c) Extension: Proposition 24 guarantees that every \(n>1\) is prime or a product of primes, but it says nothing about uniqueness. Is there another way to write \(12\) as a product of primes? If you cannot find one, explain why uniqueness might hold and who first stated it rigorously.
Every attempt gives the same primes: \(12=2\cdot 6=2\cdot 2\cdot 3=4\cdot 3=2^2\cdot 3\). Reordering or regrouping never changes which primes appear or how many times. Uniqueness follows from Euclid's Lemma (Prop. 10): if a prime divides a product, it must divide one of the factors, preventing any "other" factorisation from using different primes. Euclid proved existence here; the uniqueness result — the Fundamental Theorem of Arithmetic — was first stated explicitly by Gauss in the Disquisitiones Arithmeticae (1801).
Prop. 25
Every composite number is measured by some prime number.
Elements IX.14 If a number is composite, then there exists a prime number that divides it. That is, for any composite \(n\), there is a prime \(p\) with \(p \mid n\).
Take \(n=84\). Since \(84=6\cdot 14\) is composite, some prime must divide it. Indeed, \(2\mid 84\) and \(3\mid 84\) and \(7\mid 84\). This proposition says: that always happens for every composite number— at least one prime will measure it.
Proof
Suppose, for contradiction, that there exists a composite number measured by no prime. Among all such numbers, let \(n\) be the least.
Being composite, \(n=ab\) with integers \(a,b\) satisfying \(1<a\le b<n\). By minimality of \(n\), each of \(a\) and \(b\) is measured by some prime (for otherwise a smaller counterexample would exist).
Let \(p\) be a prime that divides \(a\). Then \(p\mid a\) and \(n=ab\), so by the laws of divisibility, \(p\mid ab\). By Euclid’s Lemma (Book VII.30), from \(p\mid ab\) it follows that \(p\mid a\) or \(p\mid b\). We already have \(p\mid a\), hence in any case \(p\mid n\).
This contradicts the choice of \(n\) as a composite number measured by no prime. Therefore every composite number is measured by some prime. Q.E.D.
Try it: Find a prime that divides 91.
Test primes: 91÷7=13. So 7|91 and 7 is prime. (Also 13|91 and 13 is prime.)
Prop. 26
There are infinitely many prime numbers.
Elements IX.20 Prime numbers are more than any assigned multitude of prime numbers. That is, given any finite list of primes, there exists another prime not in the list.
Suppose you think you have all the primes: \(2,3,5,7,11\). Multiply them together and add \(1\): \(2\cdot3\cdot5\cdot7\cdot11+1=2311\). This new number is not divisible by any of the primes in your list. So if it is prime, it’s a new prime. If it is composite, its prime divisors are new primes not in the list. Either way, your list was incomplete. Therefore primes never run out.
Proof
Suppose finitely many primes exist, say \(p_1,p_2,\dots,p_k\).
Consider the number \[ N = p_1p_2\cdots p_k + 1. \] Then \(N\) is greater than 1, so it is either prime or composite.
If \(N\) is prime, then it is a prime not among the \(p_i\), contradicting the completeness of the list. If \(N\) is composite, then it has a prime divisor \(q\). But none of \(p_1,\dots,p_k\) divide \(N\) (each leaves remainder 1 when dividing \(N\)). Therefore \(q\) is not among the \(p_i\), again contradicting completeness.
Hence no finite list of primes is complete. Therefore there are infinitely many prime numbers. Q.E.D.
Try it: Form 2·3·5·7+1=211. Is 211 prime?
Test divisibility by primes up to √211≈14.5: 2,3,5,7,11,13 — none divide 211. So 211 is prime — a prime not in our starting list {2,3,5,7}.
Prop. 27
Sum of a geometric progression (Euclid’s form)
Elements IX.35 If as many numbers as we please are in continued proportion, and numbers equal to the first are subtracted from the second and from the last, then as the excess of the second is to the first, so is the excess of the last to the sum of all the preceding numbers.
In modern symbols: for \(a, ar, ar^2, \dots, ar^{n-1}\) with \(r>1\), \[ \frac{ar - a}{a} \;=\; \frac{ar^{\,n-1} - a}{a + ar + \cdots + ar^{\,n-2}}. \] Hence \[ (r-1)\big(a + ar + \cdots + ar^{\,n-1}\big) \;=\; ar^{\,n} - a, \] so \[ a + ar + \cdots + ar^{\,n-1} \;=\; \frac{ar^{\,n} - a}{\,r-1\,}. \]
Take a geometric progression like \(3, 6, 12, 24\). Subtract the first term (3) from the second to get \(3\), and from the last to get \(21\). Euclid says the ratio \(3:3\) equals \(21:\)(sum of the earlier terms \(3+6+12=21\)). Because these ratios match, multiplying through gives the well-known formula for the sum of a geometric progression.
Proof
Let there be numbers in continued proportion \(a, ar, ar^2, \dots, ar^{\,n-1}\) with ratio \(r>1\). Subtract the first number \(a\) from the second and from the last; the excesses are \(ar-a\) and \(ar^{\,n-1}-a\).
Since the numbers are in continued proportion, the ratio of the second to the first equals the ratio of the last to the sum of all those before it. By subtracting equal numbers (namely \(a\)) from the corresponding terms of equal ratios, it follows that \[ \frac{ar-a}{a} \;=\; \frac{ar^{\,n-1}-a}{a + ar + \cdots + ar^{\,n-2}}. \]
Cross-multiplying yields \[ (ar-a)\big(a + ar + \cdots + ar^{\,n-2}\big) \;=\; a\big(ar^{\,n-1}-a\big). \] Adding \(ar^{\,n-1}-a\) to both sides gives \[ (r-1)\big(a + ar + \cdots + ar^{\,n-1}\big) \;=\; ar^{\,n} - a. \] Dividing by \(r-1\) completes the construction of the sum: \[ a + ar + \cdots + ar^{\,n-1} \;=\; \frac{ar^{\,n} - a}{\,r-1\,}. \] Q.E.D.
Try it: Sum the geometric series 2+4+8+16+32.
a=2, r=2, n=5. Sum = a(rⁿ−1)/(r−1) = 2(32−1)/1 = 62.
Prop. 28
On perfect numbers
Elements IX.36 If as many numbers as we please beginning from a unit are set out continuously in double proportion (that is, in powers of 2), until the sum of all becomes prime, and if the sum multiplied by the last term makes some number, then the product is perfect.
In modern symbols: if \(2^k-1\) is prime, then \[ N = 2^{k-1}(2^k-1) \] is a perfect number, i.e. equal to the sum of its proper divisors.
Start with powers of 2: \(1,2,4,8,\dots\). Add them up until the total is prime. For example:
- \(1+2+4=7\) (prime). Multiply by the last term \(4\): \(7\cdot 4=28\). The number 28 is perfect, since its divisors add to 28.
- \(1+2+4+8+16=31\) (prime). Multiply by the last term \(16\): \(31\cdot 16=496\). The number 496 is also perfect.
In general, whenever \(2^k-1\) is prime, the formula produces a perfect number.
Proof
Suppose \(2^k - 1\) is prime. Let \[ N = (2^k - 1)\,2^{k-1}. \]
The sum of all divisors of \(N\) factors as \[ (1+2+4+\cdots+2^{k-1})(1+(2^k-1)). \] The first parenthesis equals \(2^k-1\). The second equals \(2^k\).
Hence the sum of all divisors of \(N\) is \((2^k-1)\,2^k\).
The sum of the proper divisors is therefore \[ (2^k-1)\,2^k - N = (2^k-1)\,2^k - (2^k-1)\,2^{k-1}. \]
Simplify: \[ (2^k-1)\,(2^k - 2^{k-1}) = (2^k-1)\,2^{k-1} = N. \]
Thus the sum of the proper divisors of \(N\) equals \(N\) itself. So \(N\) is a perfect number. Q.E.D.
Try it: Verify that \(N=28\) is a perfect number.
Use \(k=3\): \(2^3-1=7\) is prime. \(N=2^2\cdot 7=28\). Proper divisors: 1, 2, 4, 7, 14. Sum: \(1+2+4+7+14=28=N\). ✓
(b) Challenge: The next perfect number after 28 is 496. Use the formula \(N=2^{k-1}(2^k-1)\) to find the value of \(k\) that gives 496, and verify that \(2^k-1\) is prime.
Try \(k=5\): \(2^5-1=31\) (prime). \(N=2^4\cdot 31=16\cdot 31=496\). Proper divisors: 1, 2, 4, 8, 16, 31, 62, 124, 248. Sum: \(1+2+4+8+16+31+62+124+248=496\). ✓
(c) Extension: The formula requires \(2^k-1\) to be prime. Show that if \(k\) is composite — say \(k=4\) — then \(2^k-1\) is also composite, so the formula cannot yield a perfect number. What does this tell you about the necessary condition on \(k\)?
For \(k=4\): \(2^4-1=15=3\cdot 5\). Not prime. The algebraic reason: if \(k=ab\) with \(a,b>1\), then \(2^k-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+1)\). The factor \(2^a-1>1\) shows \(2^k-1\) is composite. Therefore \(k\) must be prime for \(2^k-1\) to have any chance of being prime. (Prime \(k\) is necessary but not sufficient: \(k=11\) gives \(2^{11}-1=2047=23\cdot 89\), composite.)