---
title: "Arithmetic: Divisors and Prime Numbers"
book: "Primary & Middle School Mathematics"
subject: math
language: en
chapter: 64
exercises: 10
source: https://one-course.com/books/math/1/en/chapter/64-arithmetic-divisors-and-prime-numbers
---

# Chapter 64 — Arithmetic: Divisors and Prime Numbers

Arithmetic studies whole numbers and how they divide one another. Its central characters are the [prime numbers](#def-g9-arith-prime), the building blocks from which every integer is assembled by multiplication. The chapter ends with the [greatest common divisor](#def-g9-arith-gcd), the right tool for simplifying [fractions](https://one-course.com/books/math/1/en/chapter/63-fractions-and-powers#def-g9-fractions-fraction) 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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) $0$.

**Example 64.2.**

The [divisors](#def-g9-arith-divisor) of $24$ are $1, 2, 3, 4, 6, 8, 12, 24$ — they come in pairs whose [product](https://one-course.com/books/math/1/en/chapter/10-multiplication-first-steps#def-g2-mult-def) is $24$: $(1,24)$, $(2,12)$, $(3,8)$, $(4,6)$. The [multiples](https://one-course.com/books/math/1/en/chapter/32-division-and-multiples#def-g5-division-multiple) of $7$ are $7, 14, 21, 28, \dots$

**Proposition 64.3 (Divisibility rules).**

An integer is [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible):

- by $2$ when its last digit is [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) ( $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](https://one-course.com/books/math/1/en/chapter/2-addition-first-steps#def-g1-addition-def) of its digits is [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $3$ (resp. $9$ );
- by $4$ when its last two digits form a number [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $4$ .

**Proof.** *Admitted at this level.* ∎

**Example 64.4.**

$7\,215$ ends in $5$: [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $5$. Its digit [sum](https://one-course.com/books/math/1/en/chapter/2-addition-first-steps#def-g1-addition-def) is $7 + 2 + 1 + 5 = 15$, [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $3$ but not $9$: so $7\,215$ is [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-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](#def-g9-arith-divisor) 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](https://one-course.com/books/math/1/en/chapter/10-multiplication-first-steps#def-g2-mult-def) of [prime numbers](#def-g9-arith-prime), 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$:

1. try $2$ as long as the number is [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) ;
2. then try $3$ , then $5$ , then $7$ , … (only primes);
3. stop when the [quotient](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) is $1$ ; collect the factors with [exponents](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) .

It suffices to try primes $p$ with $p^2$ not exceeding the current number: if none [divides](#def-g9-arith-divisor) 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,
$$

so

$$
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.](https://one-course.com/images/onecourse/chapters/math-1/g9-arith/fig-aae7345aa9ba.svg)

*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](#def-g9-arith-prime).

**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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) $1$, so no $p_i$ [divides](#def-g9-arith-divisor) $N$. But $N \geq 2$ has at least one prime [divisor](#def-g9-arith-divisor) ([Theorem 64.6](#thm-g9-arith-factorization)) — 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](#def-g9-arith-divisor) except $1$.

**Example 64.11.**

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

**Proposition 64.12 (GCD from factorizations).**

The GCD of two integers is the [product](https://one-course.com/books/math/1/en/chapter/10-multiplication-first-steps#def-g2-mult-def) of the primes appearing in *both* factorizations, each taken with the *smaller* of its two [exponents](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def).

**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](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) $3$ and $2$: keep $2$) and $3$ ([exponents](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) $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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) $r$, then

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

Repeating divisions until the [remainder](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) is $0$, the GCD of $a$ and $b$ is the *last nonzero [remainder](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder)*.

**Proof.** From $a = bq + r$: any integer dividing $b$ and $r$ [divides](#def-g9-arith-divisor) $bq + r = a$; and from $r = a - bq$: any integer dividing $a$ and $b$ [divides](#def-g9-arith-divisor) $r$. So the pairs $(a, b)$ and $(b, r)$ have exactly the same common [divisors](#def-g9-arith-divisor) — in particular the same greatest one. Since [remainders](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) strictly decrease, the algorithm terminates, and $\gcd(x, 0) = x$ gives the last nonzero [remainder](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) is $21$: $\gcd(1071, 462) = 21$.

**Method 64.16 (Simplifying a fraction completely).**

To write $\dfrac ab$ in lowest terms:

1. compute $d = \gcd(a, b)$ , e.g. by the Euclidean algorithm;
2. divide [numerator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) and [denominator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) by $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
3. the resulting [fraction](https://one-course.com/books/math/1/en/chapter/63-fractions-and-powers#def-g9-fractions-fraction) is *irreducible* : its [numerator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) and [denominator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) are [coprime](#def-g9-arith-gcd) .

**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](#def-g9-arith-divisor) of $36$, of $45$, and of $17$.

**Solution of Exercise 64.1.**

[Divisors](#def-g9-arith-divisor) of $36$: $1, 2, 3, 4, 6, 9, 12, 18, 36$. [Divisors](#def-g9-arith-divisor) of $45$: $1, 3, 5, 9, 15, 45$. [Divisors](#def-g9-arith-divisor) of $17$: $1$ and $17$ only ($17$ is prime).

**Exercise 64.2 ★.**

Using the [divisibility](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) rules, determine whether $2\,346$ is [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $2$, by $3$, by $4$, by $5$, by $9$.

**Solution of Exercise 64.2.**

$2\,346$ ends in $6$: [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $2$, not by $5$. Digit [sum](https://one-course.com/books/math/1/en/chapter/2-addition-first-steps#def-g1-addition-def) $2 + 3 + 4 + 6 = 15$: [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $3$, not by $9$. Last two digits $46$, and $46 = 4 \times 11 + 2$ is not [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $4$: $2\,346$ is not [divisible](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible) by $4$.

**Exercise 64.3 ★.**

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

**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](#met-g9-arith-factorization).

**Solution of Exercise 64.4.**

$101$: test the primes $p$ with $p^2 \leq 101$, i.e. $2, 3, 5, 7$. None [divides](#def-g9-arith-divisor) $101$ ([odd](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd), digit [sum](https://one-course.com/books/math/1/en/chapter/2-addition-first-steps#def-g1-addition-def) $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](#def-g9-arith-divisor), and from the prime factorizations.

**Solution of Exercise 64.5.**

Common [divisors](#def-g9-arith-divisor) of $48$ and $60$: [divisors](#def-g9-arith-divisor) of 48 are $1, 2, 3, 4, 6, 8,
12, 16, 24, 48$; [divisors](#def-g9-arith-divisor) 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](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def): $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 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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder): $\gcd(255, 154) = 1$ (they are [coprime](#def-g9-arith-gcd)).

$\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](https://one-course.com/books/math/1/en/chapter/63-fractions-and-powers#def-g9-fractions-fraction) $\dfrac{588}{504}$ irreducible. (Compute the GCD by the method of your choice, then divide.)

**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 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](#def-g9-arith-divisor) of $24$ and $36$; factorizations help.)

**Solution of Exercise 64.9.**

We need the least common [multiple](#def-g9-arith-divisor). $24 = 2^3 \times 3$ and $36 = 2^2 \times 3^2$; taking each prime with the *larger* [exponent](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def): $\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.

1. Show that $\gcd(n, n+1) = 1$ (consecutive integers are always [coprime](#def-g9-arith-gcd) ).
2. Deduce that the [fraction](https://one-course.com/books/math/1/en/chapter/63-fractions-and-powers#def-g9-fractions-fraction) $\dfrac{n}{n+1}$ is always irreducible.

**Solution of Exercise 64.10.**

*1.* Any common [divisor](#def-g9-arith-divisor) $d$ of $n$ and $n+1$ also [divides](#def-g9-arith-divisor) their [difference](https://one-course.com/books/math/1/en/chapter/3-subtraction-first-steps#ex-g1-subtraction-difference) $(n+1) - n = 1$, so $d = 1$: $\gcd(n, n+1) = 1$.

*2.* A [fraction](https://one-course.com/books/math/1/en/chapter/63-fractions-and-powers#def-g9-fractions-fraction) is irreducible exactly when its [numerator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) and [denominator](https://one-course.com/books/math/1/en/chapter/24-first-fractions#def-g4-fractions-def) are [coprime](#def-g9-arith-gcd), 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](#def-g9-arith-prime), and a famous corridor of one hundred lockers whose final state is decided by counting [divisors](#def-g9-arith-divisor). Everything runs on this chapter’s machinery: [divisibility](https://one-course.com/books/math/1/en/chapter/37-whole-numbers#def-g6-wholes-divisible), prime factorization ([Theorem 64.6](#thm-g9-arith-factorization)) and Euclid’s algorithm ([Theorem 64.14](#thm-g9-arith-euclidalgo)).

**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.

1. Measure exactly $1$ L. (Describe your sequence of moves and the two jugs’ contents after each one.)
2. Measure exactly $4$ L — the puzzle from a famous action film. (It can be done in six moves.)
3. 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.
4. 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](#def-g9-arith-divisor) of $2$ , so every reachable amount is [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) .
5. Question 4’s argument works in general: with jugs of $a$ and $b$ liters, every reachable amount is a [multiple](#def-g9-arith-divisor) 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.**

6. Compute with Euclid’s algorithm: $\gcd(91, 65)$ and $\gcd(2\,026, 46)$ .
7. Explain, in your own words, why the amounts appearing in the jugs are Euclid’s [remainders](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) 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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-remainder) in Euclid’s algorithm for $(13, 5)$ .
8. 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)$ .
9. A quick coprimality proof in the style of [Exercise 64.10](#exo-g9-arith-10) : show that $\gcd(n, 2n + 1) = 1$ for every positive integer $n$ . (What does a common [divisor](#def-g9-arith-divisor) of $n$ and $2n + 1$ have to divide?)
10. 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](#def-g9-arith-divisor) ) $\times$ $\gcd$ $=$ [product](https://one-course.com/books/math/1/en/chapter/10-multiplication-first-steps#def-g2-mult-def) of the two numbers — and test it again on $5$ and $3$ .

**Part III — Cicadas, [divisors](#def-g9-arith-divisor) and lockers.**

11. 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.
12. Using the factorization $360 = 2^3 \times 3^2 \times 5$ , count the [divisors](#def-g9-arith-divisor) of $360$ without listing them: a [divisor](#def-g9-arith-divisor) chooses an [exponent](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) for $2$ (four choices: $0, 1, 2, 3$ ), one for $3$ , one for $5$ . How many [divisors](#def-g9-arith-divisor) in all?
13. Show that in the factorization of a perfect square $n = m^2$ , every prime carries an *[even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd)* [exponent](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) . Deduce, without computing any square root, that $360$ is not a perfect square.
14. Pair each [divisor](#def-g9-arith-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](#def-g9-arith-divisor) its own partner? Deduce the criterion: $n$ has an *[odd](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd)* number of [divisors](#def-g9-arith-divisor) exactly when $n$ is a perfect square. Check it on $36$ and on $360$ .
15. 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](https://one-course.com/books/math/1/en/chapter/32-division-and-multiples#def-g5-division-multiple) 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 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](#def-g9-arith-divisor) of $2$. Filling sets a content to $6$ or $4$: [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd). Emptying sets it to $0$: [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd). Pouring moves some water between jugs whose contents were [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd), and the poured quantity is a [difference](https://one-course.com/books/math/1/en/chapter/3-subtraction-first-steps#ex-g1-subtraction-difference) of [even numbers](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) (space left, or amount available): all contents stay [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) forever. An [odd](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) target like $1$ L is unreachable.

**5.** $\gcd(6, 4) = 2$: only [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) 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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-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](https://one-course.com/books/math/1/en/chapter/17-sharing-and-division#def-g3-division-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](#def-g9-arith-divisor) of $n$ and $2n + 1$ [divides](#def-g9-arith-divisor) $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](#def-g9-arith-divisor) of $12$ and $18$. Law: $36 \times \gcd(12, 18) = 36 \times 6 = 216 = 12 \times
18$. For $5$ and $3$: first common [multiple](#def-g9-arith-divisor) $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](#def-g9-arith-divisor) 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](#def-g9-arith-divisor) 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](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) for $2$, three for $3$, two for $5$: $4 \times 3 \times 2 = 24$ [divisors](#def-g9-arith-divisor).

**13.** If $m = 2^{a} \times 3^{b} \times \cdots$, then $m^2 = 2^{2a} \times 3^{2b} \times \cdots$: every [exponent](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) is doubled, hence [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd). In $360 = 2^3 \times 3^2 \times 5$, the [exponents](https://one-course.com/books/math/1/en/chapter/56-powers#def-g8-powers-def) of $2$ and of $5$ are [odd](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd): $360$ is not a perfect square.

**14.** A [divisor](#def-g9-arith-divisor) is its own partner exactly when $d = \frac nd$, i.e. $n = d^2$: only squares have such a middle [divisor](#def-g9-arith-divisor). For all other $n$ the [divisors](#def-g9-arith-divisor) split into pairs, an [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) count. So: [odd number](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) of [divisors](#def-g9-arith-divisor) $\Leftrightarrow$ perfect square. Check: $36$ has [divisors](#def-g9-arith-divisor) $1, 2, 3, 4, 6, 9, 12, 18, 36$ — nine of them, [odd](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd), and $36 = 6^2$; while $360$ has $24$ (question 12), [even](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd), and is no square (question 13).

**15.** Locker $n$ is toggled once by each student $k$ whose number [divides](#def-g9-arith-divisor) $n$: in all, as many times as $n$ has [divisors](#def-g9-arith-divisor). A locker ends *open* when it is toggled an [odd number](https://one-course.com/books/math/1/en/chapter/14-numbers-up-to-10-000#def-g3-numbers-evenodd) 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.