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.

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\).

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\).

Def. 6 (Composite number)

A number \(n \in \mathbb{N},\ n>1\), is composite if \(\exists\, a,b \in \mathbb{N}\) with \(1

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.

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.

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\)

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:

1. 28 − 15 = 13
2. 15 − 13 = 2
3. 13 − 2 = 11
4. 11 − 2 = 9
5. 9 − 2 = 7
6. 7 − 2 = 5
7. 5 − 2 = 3
8. 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.

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:

1. 84 − 30 = 54
2. 54 − 30 = 24
3. 30 − 24 = 6
4. 24 − 6 = 18
5. 18 − 6 = 12
6. 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.

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.

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.

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.

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.

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.

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.

1. Divide 119 by 34: \(119 = 3\cdot 34 + 17\). The remainder is 17.
2. 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 for primes (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.

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.

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.

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.