Primary & Middle School Mathematics · Grades 1–9

64Arithmetic: Divisors and Prime Numbers

Arithmetic studies whole numbers and how they divide one another. Its central characters are the prime numbers, the building blocks from which every integer is assembled by multiplication. The chapter ends with the greatest common divisor, the right tool for simplifying fractions once and for all. This story continues, much further, in the High School volume and beyond.

64.1 Divisors and multiples

Definition 64.1 (Divisor, multiple)

Let $a$ and $b$ be positive integers. We say that $b$ divides $a$ (or that $b$ is a divisor of $a$ , or that $a$ is a multiple of $b$ ) when $a = b \times k$ for some integer $k$ — that is, when the division of $a$ by $b$ leaves remainder $0$ .

Example 64.2

The divisors of $24$ are $1, 2, 3, 4, 6, 8, 12, 24$ — they come in pairs whose product is $24$ : $(1,24)$ , $(2,12)$ , $(3,8)$ , $(4,6)$ . The multiples of $7$ are $7, 14, 21, 28, \dots$

Proposition 64.3 (Divisibility rules)

An integer is divisible:

by $2$ when its last digit is even ( $0, 2, 4, 6, 8$ );
by $5$ when its last digit is $0$ or $5$ ;
by $10$ when its last digit is $0$ ;
by $3$ (resp. $9$ ) when the sum of its digits is divisible by $3$ (resp. $9$ );
by $4$ when its last two digits form a number divisible by $4$ .

Proof. Admitted at this level. ∎

Example 64.4

$7\,215$ ends in $5$ : divisible by $5$ . Its digit sum is $7 + 2 + 1 + 5 = 15$ , divisible by $3$ but not $9$ : so $7\,215$ is divisible by $3$ , not by $9$ . Indeed $7\,215 = 3 \times 5 \times 481$ .

64.2 Prime numbers

Definition 64.5 (Prime number)

A prime number is an integer $\geq 2$ whose only divisors are $1$ and itself. The primes below $30$ are

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

The number $1$ is not prime (by convention), and an integer $\geq 2$ that is not prime is called composite.

Theorem 64.6 (Prime factorization)

Every integer $\geq 2$ is a product of prime numbers, and this factorization is unique up to the order of the factors.

Proof. Admitted at this level. ∎

Method 64.7 (Factoring an integer)

Divide by the smallest possible prime, repeatedly, until reaching $1$ :

try $2$ as long as the number is even;
then try $3$ , then $5$ , then $7$ , … (only primes);
stop when the quotient is $1$ ; collect the factors with exponents.

It suffices to try primes $p$ with $p^2$ not exceeding the current number: if none divides it, the number itself is prime.

Example 64.8

Factor $360$ , one division at a time:

360 = 2 \times 180, \quad 180 = 2 \times 90, \quad 90 = 2 \times 45, \quad 45 = 3 \times 15, \quad 15 = 3 \times 5,

360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5 .

The factor tree of 360: each step splits off the smallest prime factor (in red). Reading the red leaves and the final 5: 360 = 23 × 32 × 5. — The factor tree of $360$ : each step splits off the smallest prime factor (in red). Reading the red leaves and the final $5$ : $360 = 2^3 \times 3^2 \times 5$ .

Theorem 64.9 (Euclid)

There are infinitely many prime numbers.

Proof. Suppose there were only finitely many, say $p_1, p_2, \dots, p_k$ , and consider

N = p_1 \times p_2 \times \dots \times p_k + 1 .

Dividing $N$ by any $p_i$ leaves remainder $1$ , so no $p_i$ divides $N$ . But $N \geq 2$ has at least one prime divisor (Theorem 64.6) — a prime that is not in our list. Contradiction: no finite list can contain all the primes. ∎

64.3 The greatest common divisor

Definition 64.10 (GCD)

The greatest common divisor of two positive integers $a$ and $b$ , written $\gcd(a, b)$ , is the largest integer dividing both. When $\gcd(a, b) = 1$ , the integers are called coprime: they share no divisor except $1$ .

Example 64.11

Divisors of $18$ : $1, 2, 3, 6, 9, 18$ . Divisors of $24$ : $1, 2, 3, 4, 6, 8, 12, 24$ . Common divisors: $1, 2, 3, 6$ ; so $\gcd(18, 24) = 6$ . The integers $15$ and $28$ are coprime.

Proposition 64.12 (GCD from factorizations)

The GCD of two integers is the product of the primes appearing in both factorizations, each taken with the smaller of its two exponents.

Proof. Admitted at this level. ∎

Example 64.13

$360 = 2^3 \times 3^2 \times 5$ and $84 = 2^2 \times 3 \times 7$ . Common primes: $2$ (exponents $3$ and $2$ : keep $2$ ) and $3$ (exponents $2$ and $1$ : keep $1$ ). So

\gcd(360, 84) = 2^2 \times 3 = 12 .

Theorem 64.14 (Euclidean algorithm)

If $a = bq + r$ is the division of $a$ by $b$ with remainder $r$ , then

\gcd(a, b) = \gcd(b, r).

Repeating divisions until the remainder is $0$ , the GCD of $a$ and $b$ is the last nonzero remainder.

Proof. From $a = bq + r$ : any integer dividing $b$ and $r$ divides $bq + r = a$ ; and from $r = a - bq$ : any integer dividing $a$ and $b$ divides $r$ . So the pairs $(a, b)$ and $(b, r)$ have exactly the same common divisors — in particular the same greatest one. Since remainders strictly decrease, the algorithm terminates, and $\gcd(x, 0) = x$ gives the last nonzero remainder. ∎

Example 64.15

Compute $\gcd(1071, 462)$ :

\begin{align*} 1071 &= 462 \times 2 + 147, \\ 462 &= 147 \times 3 + 21, \\ 147 &= 21 \times 7 + 0 . \end{align*}

The last nonzero remainder is $21$ : $\gcd(1071, 462) = 21$ .

Method 64.16 (Simplifying a fraction completely)

To write $\dfrac ab$ in lowest terms:

compute $d = \gcd(a, b)$ , e.g. by the Euclidean algorithm;
divide numerator and denominator by $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
the resulting fraction is irreducible: its numerator and denominator are coprime.

Example 64.17

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$ , and $\gcd(22, 51) = 1$ : irreducible.

64.4 Exercises

Exercise 64.1 ★

List all the divisors of $36$ , of $45$ , and of $17$ .

Solution

Solution of Exercise 64.1.

Divisors of $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Divisors of $45$ : $1, 3, 5, 9, 15, 45$ . Divisors of $17$ : $1$ and $17$ only ( $17$ is prime).

Exercise 64.2 ★

Using the divisibility rules, determine whether $2\,346$ is divisible by $2$ , by $3$ , by $4$ , by $5$ , by $9$ .

Solution

Solution of Exercise 64.2.

$2\,346$ ends in $6$ : divisible by $2$ , not by $5$ . Digit sum $2 + 3 + 4 + 6 = 15$ : divisible by $3$ , not by $9$ . Last two digits $46$ , and $46 = 4 \times 11 + 2$ is not divisible by $4$ : $2\,346$ is not divisible by $4$ .

Exercise 64.3 ★

Give the prime factorization of $72$ , $150$ , $210$ and $121$ .

Solution

Solution of Exercise 64.3.

$72 = 2^3 \times 3^2$ ; $150 = 2 \times 3 \times 5^2$ ; $210 = 2 \times 3 \times 5 \times 7$ ; $121 = 11^2$ .

Exercise 64.4 ★

Is $101$ prime? Is $91$ ? Is $143$ ? Justify using the stopping rule of Method 64.7.

Solution

Solution of Exercise 64.4.

$101$ : test the primes $p$ with $p^2 \leq 101$ , i.e. $2, 3, 5, 7$ . None divides $101$ (odd, digit sum $2$ , does not end in $0/5$ , $101 = 7 \times 14 + 3$ ): $101$ is prime.

$91 = 7 \times 13$ : not prime.

$143 = 11 \times 13$ : not prime.

Exercise 64.5 ★

Compute $\gcd(48, 60)$ in two ways: by listing common divisors, and from the prime factorizations.

Solution

Solution of Exercise 64.5.

Common divisors of $48$ and $60$ : divisors of 48 are $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; divisors of $60$ are $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ ; the common ones are $1, 2, 3, 4, 6, 12$ , so $\gcd(48,60) = 12$ .

By factorization: $48 = 2^4 \times 3$ and $60 = 2^2 \times 3 \times 5$ ; common primes with smaller exponents: $2^2 \times 3 = 12$ .

Exercise 64.6 ★★

Use the Euclidean algorithm to compute $\gcd(255, 154)$ , then $\gcd(1053, 325)$ . Write every division line.

Solution

Solution of Exercise 64.6.

$\gcd(255, 154)$ :

\begin{align*} 255 &= 154 \times 1 + 101, \\ 154 &= 101 \times 1 + 53, \\ 101 &= 53 \times 1 + 48, \\ 53 &= 48 \times 1 + 5, \\ 48 &= 5 \times 9 + 3, \\ 5 &= 3 \times 1 + 2, \\ 3 &= 2 \times 1 + 1, \\ 2 &= 1 \times 2 + 0 . \end{align*}

Last nonzero remainder: $\gcd(255, 154) = 1$ (they are coprime).

$\gcd(1053, 325)$ :

\begin{align*} 1053 &= 325 \times 3 + 78, \\ 325 &= 78 \times 4 + 13, \\ 78 &= 13 \times 6 + 0 . \end{align*}

$\gcd(1053, 325) = 13$ .

Exercise 64.7 ★★

Make the fraction $\dfrac{588}{504}$ irreducible. (Compute the GCD by the method of your choice, then divide.)

Solution

Solution of Exercise 64.7.

Euclidean algorithm: $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 + 0$ : $\gcd(588, 504) = 84$ . Then

\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},

which is irreducible.

Exercise 64.8 ★★

A florist has $84$ roses and $126$ tulips and wants to make identical bouquets, using all the flowers, with as many bouquets as possible. How many bouquets can she make, and what does each contain?

Solution

Solution of Exercise 64.8.

The number of bouquets must divide both $84$ and $126$ ; the largest possible is $\gcd(84, 126)$ . Factorizations: $84 = 2^2 \times 3 \times 7$ , $126 = 2 \times 3^2 \times 7$ , so the GCD is $2 \times 3 \times 7 = 42$ . She can make $42$ bouquets, each containing $\frac{84}{42} = 2$ roses and $\frac{126}{42} = 3$ tulips.

Exercise 64.9 ★★

Two ferries leave the same dock at 8:00. One departs every $24$ minutes, the other every $36$ minutes. At what time do they next leave together? (Look for the smallest common multiple of $24$ and $36$ ; factorizations help.)

Solution

Solution of Exercise 64.9.

We need the least common multiple. $24 = 2^3 \times 3$ and $36 = 2^2 \times 3^2$ ; taking each prime with the larger exponent: $\lcm = 2^3 \times 3^2 = 72$ . The ferries next leave together $72$ minutes after 8:00, at 9:12.

Exercise 64.10 ★★★

Let $n$ be a positive integer.

Show that $\gcd(n, n+1) = 1$ (consecutive integers are always coprime).
Deduce that the fraction $\dfrac{n}{n+1}$ is always irreducible.

Solution

Solution of Exercise 64.10.

1. Any common divisor $d$ of $n$ and $n+1$ also divides their difference $(n+1) - n = 1$ , so $d = 1$ : $\gcd(n, n+1) = 1$ .

2. A fraction is irreducible exactly when its numerator and denominator are coprime, which is the case for $n$ and $n + 1$ by part 1.

64.5 Problem: Water jugs, cicadas and one hundred lockers

Problem 64.1

Weekend problem — the GCD decides which amounts two jugs can measure; primes protect cicadas; and the lockers that stay open are the perfect squares

Three puzzles that look like riddles and are really arithmetic: measuring water with unmarked jugs (the GCD in disguise), insect life cycles that evolved into prime numbers, and a famous corridor of one hundred lockers whose final state is decided by counting divisors. Everything runs on this chapter’s machinery: divisibility, prime factorization (Theorem 64.6) and Euclid’s algorithm (Theorem 64.14).

Part I — The water jugs. You stand at a fountain with two unmarked jugs, of $5$ L and $3$ L. Allowed moves: fill a jug to the brim, empty a jug completely, pour one jug into the other until the source is empty or the target is full.

Measure exactly $1$ L. (Describe your sequence of moves and the two jugs’ contents after each one.)
Measure exactly $4$ L — the puzzle from a famous action film. (It can be done in six moves.)
Which whole numbers of liters from $1$ to $8$ can you exhibit (in one jug, or split across both)? Complete the list, reusing your sequences.
New jugs: $6$ L and $4$ L. Try to measure $1$ L — then explain why it is hopeless: check that each of the three allowed moves keeps every jug’s content a multiple of $2$ , so every reachable amount is even.
Question 4’s argument works in general: with jugs of $a$ and $b$ liters, every reachable amount is a multiple of $\gcd(a, b)$ . Compute $\gcd(6, 4)$ and $\gcd(5, 3)$ , and say what the law predicts for each pair of jugs.

Part II — Euclid at the fountain.

Compute with Euclid’s algorithm: $\gcd(91, 65)$ and $\gcd(2\,026, 46)$ .
Explain, in your own words, why the amounts appearing in the jugs are Euclid’s remainders in disguise: with jugs of $13$ L and $5$ L, repeatedly fill the small jug and pour it into the big one (emptying the big jug whenever it fills). Which new amounts appear first — and compare them with the remainders in Euclid’s algorithm for $(13, 5)$ .
Deduce the champion’s answer: with jugs of $13$ and $5$ liters, can you measure exactly $1$ L? Justify in one line with question 5 and $\gcd(13, 5)$ .
A quick coprimality proof in the style of Exercise 64.10: show that $\gcd(n, 2n + 1) = 1$ for every positive integer $n$ . (What does a common divisor of $n$ and $2n + 1$ have to divide?)
Two buses leave the terminus together at 7:00; one departs every $12$ minutes, the other every $18$ . List the next departure times of each and find the first moment they leave together again. Verify on this example the beautiful law: (first common multiple) $\times$ $\gcd$ $=$ product of the two numbers — and test it again on $5$ and $3$ .

Part III — Cicadas, divisors and lockers.

Certain North American cicadas emerge only every $17$ years; suppose a predator’s population peaks every $4$ years. If both happen this year, in how many years will an emergence next coincide with a peak? Same question if the cicadas’ cycle were $16$ years — how often would they then be massacred? Explain in one sentence why evolution pushed the cycle to a prime length.
Using the factorization $360 = 2^3 \times 3^2 \times 5$ , count the divisors of $360$ without listing them: a divisor chooses an exponent for $2$ (four choices: $0, 1, 2, 3$ ), one for $3$ , one for $5$ . How many divisors in all?
Show that in the factorization of a perfect square $n = m^2$ , every prime carries an even exponent. Deduce, without computing any square root, that $360$ is not a perfect square.
Pair each divisor $d$ of $n$ with its partner $\frac{n}{d}$ (for $n = 36$ : $1 \leftrightarrow 36$ , $2 \leftrightarrow 18$ , $3 \leftrightarrow 12$ , $4 \leftrightarrow 9$ , $6 \leftrightarrow 6$ ). When is a divisor its own partner? Deduce the criterion: $n$ has an odd number of divisors exactly when $n$ is a perfect square. Check it on $36$ and on $360$ .
The hundred lockers. Lockers $1$ to $100$ start closed. Student $1$ toggles every locker; student $2$ toggles lockers $2, 4, 6, \dots$ ; student $k$ toggles the multiples of $k$ ; and so on up to student $100$ . Explain which students touch locker $n$ , how many times it gets toggled, and — using question 14 — exactly which lockers end up open. How many are open?

Solution

Solution of Problem 64.1.

1. Fill the $3$ and pour it into the $5$ (contents $0/3 \to 3$ in the big). Fill the $3$ again and pour into the $5$ until it is full: the big jug takes only $2$ more, leaving

3 - 2 = 1 \text{ L in the small jug.}

Moves: fill $3$ ; pour $3 \to 5$ ; fill $3$ ; pour $3 \to 5$ .

2. Fill the $5$ ; pour into the $3$ (leaves $2$ in the big); empty the $3$ ; pour the $2$ into the $3$ ; fill the $5$ ; pour into the $3$ until full — it takes $1$ , leaving $\mathbf{4}$ L in the big jug. Six moves.

3. All of them: $1$ (question 1), $2$ (after two moves of question 2), $3$ and $5$ (single fillings), $4$ (question 2), $6 = 3 + 3$ (a full small jug plus $3$ poured into the big), $7 = 5 + 2$ , $8 = 5 + 3$ (both full). Every whole amount from $1$ to $8$ L is measurable with the $5$ and the $3$ .

4. Start: both jugs hold $0$ , a multiple of $2$ . Filling sets a content to $6$ or $4$ : even. Emptying sets it to $0$ : even. Pouring moves some water between jugs whose contents were even, and the poured quantity is a difference of even numbers (space left, or amount available): all contents stay even forever. An odd target like $1$ L is unreachable.

5. $\gcd(6, 4) = 2$ : only even amounts — confirmed by question 4. $\gcd(5, 3) = 1$ : every whole amount is allowed by the law, and question 3 realized them all. The GCD is exactly the jugs’ unit of measurement.

6. $91 = 1 \times 65 + 26$ ; $65 = 2 \times 26 + 13$ ; $26 = 2 \times 13 + 0$ : $\gcd(91, 65) = 13$ . And $2\,026 = 44 \times 46 + 2$ ; $46 = 23 \times 2 + 0$ : $\gcd(2\,026, 46) = 2$ .

7. Pouring $5$ into the $13$ -jug repeatedly: after two fillings the big jug holds $10$ ; the third filling fits only $3$ , leaving $5 - 3 = 2$ in the small jug — the remainder of $13$ by $5$ was $3$ , and the amounts $3$ (space) and $2$ (leftover) are exactly Euclid’s numbers ( $13 = 2 \times 5 + 3$ , $5 = 1 \times 3 + 2$ ). Continuing, $3 - 2 = 1$ appears: the algorithm’s next remainder. The fountain performs Euclid’s divisions with water.

8. $\gcd(13, 5) = 1$ , so the law of question 5 allows every whole amount — and question 7’s cascade actually produced $1$ L. Yes.

9. A common divisor of $n$ and $2n + 1$ divides $2n + 1 - 2 \times n = 1$ : it must be $1$ . Hence $\gcd(n, 2n+1) = 1$ always.

10. Bus A: 7:12, 7:24, 7:36, 7:48, 8:00 …; bus B: 7:18, 7:36, 7:54 … First common departure: 7:36, after $36$ minutes — the first common multiple of $12$ and $18$ . Law: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times 18$ . For $5$ and $3$ : first common multiple $15$ , and $15 \times \gcd(5,3) = 15 \times 1 = 15 = 5 \times 3$ .

11. With a $17$ -year cycle: the next coincidence is the first common multiple of $17$ and $4$ ; since $\gcd(17, 4) = 1$ , that is $17 \times 4 = 68$ years — the cicadas meet the peak once in four emergences. With a $16$ -year cycle: $16$ is a multiple of $4$ , so every emergence hits a peak. A prime cycle length shares no factor with any shorter predator cycle, pushing coincidences as far apart as possible: arithmetic as camouflage.

12. Four choices of exponent for $2$ , three for $3$ , two for $5$ : $4 \times 3 \times 2 = 24$ divisors.

13. If $m = 2^{a} \times 3^{b} \times \cdots$ , then $m^2 = 2^{2a} \times 3^{2b} \times \cdots$ : every exponent is doubled, hence even. In $360 = 2^3 \times 3^2 \times 5$ , the exponents of $2$ and of $5$ are odd: $360$ is not a perfect square.

14. A divisor is its own partner exactly when $d = \frac nd$ , i.e. $n = d^2$ : only squares have such a middle divisor. For all other $n$ the divisors split into pairs, an even count. So: odd number of divisors $\Leftrightarrow$ perfect square. Check: $36$ has divisors $1, 2, 3, 4, 6, 9, 12, 18, 36$ — nine of them, odd, and $36 = 6^2$ ; while $360$ has $24$ (question 12), even, and is no square (question 13).

15. Locker $n$ is toggled once by each student $k$ whose number divides $n$ : in all, as many times as $n$ has divisors. A locker ends open when it is toggled an odd number of times — by question 14, exactly when $n$ is a perfect square. Open lockers: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$ — ten of them.