Part I · Numbers Chapter 4 of 60
Divisibility and Euclid's algorithm
Puzzles about a calendar, a long number, tiles, jugs and coins, and one answer to all of them: the greatest common divisor, and a way to find it that is more than two thousand years old.
Builds on: 3 · Prime numbers
You will learn
- understand why divisibility tests work, and invent new ones
- find the gcd and lcm by factorization and by Euclid's algorithm, even for large numbers
- solve equations ax + by = c in integers, and puzzles about jugs and coins
At the end of the last chapter we got stuck on the fraction $\frac{391}{527}$. We'd like to simplify it, but by what? Neither number is divisible by $2$, $3$ or $5$, and breaking them into prime factors takes a while. For numbers with several hundred digits it takes hopelessly long, even for a computer. We need a way to find a common divisor without factorizing the numbers.
Such a way exists, and it is more than two thousand years old. But let's not rush to it. This chapter is a collection of puzzles: about a calendar, a long number, tiles, jugs and coins. Each seems independent at first, and then turns out to reduce to the same question: what is the largest number that divides both of two given numbers?
The calendar puzzle
Today is Monday. What day of the week will it be in a thousand days?
There's no need to leaf through a calendar. The days of the week repeat every seven, so every full seven days can be thrown away: in $7$, $14$ or $994$ days it will be Monday again. Divide $1000$ by $7$ with remainder: $1000 = 7 \cdot 142 + 6$. A hundred and forty-two full weeks change nothing, and six days after Monday is Sunday.
All we needed was the remainder. You've known it since primary school, but now let's write it down precisely, because the whole chapter rests on this notation.
To divide with remainder an integer $a$ by a natural number $b$ means to find integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$. Such a pair always exists and is always unique. The number $r$ is called the remainder; if $r = 0$, then $a$ is exactly divisible by $b$, and $b$ is a divisor of $a$ in the sense of the last chapter.
For every integer $a$ and natural number $b$ there are integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$, and there is only one such pair.
The idea: mark all the multiples of $b$ on the number line and see which two of them $a$ falls between.
Many people get confused by negative dividends. In mathematics the remainder is always taken to be non-negative, and that's convenient. What day of the week was it $17$ days before a Monday? Write $-17 = 7 \cdot (-3) + 4$: going back seventeen days is the same as going back three full weeks and then forward four days. Monday plus four days is Friday. Check another way: seventeen days is two weeks and three more days, and three days before Monday was Friday too.
Today is Wednesday. What day of the week will it be in $100$ days?
$100 = 7 \cdot 14 + 2$. The fourteen weeks can be thrown away, leaving two days: Wednesday, Thursday, Friday.
The long-number puzzle
Is $123{,}456{,}789$ divisible by $9$? By $11$? By $7$?
By nine, yes, and you can tell at once: the digit sum $1 + 2 + \dots + 9 = 45$ is divisible by $9$. Everyone knows divisibility tests from school, but they're usually taught as tricks, without explanation. The explanation is simple, and it also shows how to invent a test for any divisor.
Write the number out by place value (as we did in the chapter on counting):
$$\begin{aligned} 123{,}456{,}789 = 1 \cdot 10^8 &+ 2 \cdot 10^7 + 3 \cdot 10^6 + \dots \\ &+ 7 \cdot 10^2 + 8 \cdot 10 + 9. \end{aligned}$$We'll need a simple property of remainders: the remainder of a sum or a product depends only on the remainders of the terms or factors.
Numbers $x$ and $x'$ leave the same remainder on division by $d$ if and only if $d$ divides the difference $x - x'$. If $x$ and $x'$ leave the same remainder, and so do $y$ and $y'$, then the sums $x + y$ and $x' + y'$ leave the same remainder, and so do the products $xy$ and $x'y'$.
If $x = dq + r$ and $x' = dq' + r$ with the same remainder $r$, then $x - x' = d(q - q')$ is divisible by $d$. Conversely, let $x - x' = dk$ and $x' = dq' + r'$ with $0 \le r' < d$. Then $x = d(q' + k) + r'$ is a division of $x$ with remainder, and by uniqueness the remainder of $x$ is also $r'$.
Now sums: $(x + y) - (x' + y') = (x - x') + (y - y')$ is a sum of two multiples of $d$, so it is divisible by $d$. Products: $xy - x'y' = x(y - y') + y'(x - x')$, and both terms are divisible by $d$. By the first part the remainders agree.
Now the test itself, for any divisor $d$ at once.
Let $n = a_m 10^m + \dots + a_1 \cdot 10 + a_0$, and let $w_k$ be a number that differs from $10^k$ by a multiple of $d$ (for example, the remainder of $10^k$ on division by $d$). Then $n$ and the sum $S = a_m w_m + \dots + a_1 w_1 + a_0 w_0$ leave the same remainder on division by $d$. In particular, $n$ is divisible by $d$ if and only if $S$ is.
Subtract: $n - S = a_m (10^m - w_m) + \dots + a_1 (10 - w_1) + a_0 (1 - w_0)$. Each bracket is divisible by $d$ by assumption, so the whole sum is too. By the lemma on remainders, $n$ and $S$ leave the same remainder; remainder $0$ for one means remainder $0$ for the other.
For nine the weights are the simplest possible: $10 = 9 + 1$, $100 = 99 + 1$, $1000 = 999 + 1$, and every power of ten leaves remainder $1$.
A number and the sum of its digits leave the same remainder on division by $9$ and on division by $3$. So a number is divisible by $9$ (by $3$) if and only if the sum of its digits is divisible by $9$ (by $3$).
The idea: every hundred and every ten hides a multiple of nine plus one "extra" cell, and the extra cells together with the units make up the digit sum. We'll show it on the number $234$; the argument is the same for any number.
Eleven works similarly, except that $10 = 11 - 1$.
A number is divisible by $11$ if and only if the alternating sum of its digits $a_0 - a_1 + a_2 - a_3 + \dots$, starting from the last digit, is divisible by $11$.
The numbers $10$ and $-1$ leave the same remainder on division by $11$: their difference is $11$. By the lemma on remainders their products also leave the same remainder, so $10^k = 10 \cdot 10 \cdots 10$ and $(-1)^k$ differ by a multiple of $11$. So in the place-weight test we can take $w_k = (-1)^k$: the weights $1, -1, 1, -1, \dots$ The sum $S$ with these weights is exactly the alternating digit sum. For our number: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$. The remainder is $5$, so $123{,}456{,}789$ is not divisible by $11$.
The other school tests come out the same way.
A number is divisible by $2$ or by $5$ if and only if its last digit is divisible by $2$ (by $5$); by $4$ or by $25$ if and only if the number formed by its last two digits is divisible by $4$ (by $25$); by $8$ or by $125$ if and only if the number formed by its last three digits is divisible by $8$ (by $125$).
Use the place-weight test. The number $10$ is divisible by $2$ and by $5$, so $10^k$ for $k \ge 1$ is divisible by them too, and we can take $w_k = 0$ for every place except the last ($w_0 = 1$): the sum $S$ is the last digit. The number $100 = 4 \cdot 25$ is divisible by $4$ and by $25$, and so is every $10^k$ with $k \ge 2$; take $w_0 = 1$, $w_1 = 10$ and all other weights zero, and $S$ is the number formed by the last two digits. In the same way $1000 = 8 \cdot 125$ gives the test by the last three digits.
For $7$ the weights go round in a cycle: $1, 3, 2, -1, -3, -2$. A test for divisibility by seven exists, but it is harder to remember than to simply divide.
A number is divisible by $3$ if the sum of its digits is divisible by $3$. Is a number divisible by $6$ if the sum of its digits is divisible by $6$?
The digit sum of $15$ is $6$, but $15$ isn't divisible by $6$. The digit-sum test works only for the divisors of nine, $3$ and $9$: only for them does $10$ leave remainder $1$. On division by $6$, ten leaves remainder $4$, and the digit sum tells you nothing. The correct test for $6$ is that the number is divisible by both $2$ and $3$.
The tile puzzle
A hallway floor measures $336 \times 480$ centimetres. It is to be covered with identical square tiles without cutting any. What is the largest tile you can use?
The side of the tile has to fit a whole number of times both along $336$ and along $480$, that is, it must divide both numbers. We need their greatest common divisor. Factorize the numbers into primes, as in the last chapter:
$$336 = 2^4 \cdot 3 \cdot 7, \qquad 480 = 2^5 \cdot 3 \cdot 5.$$A common divisor can contain only primes present in both numbers, and no more times than in each. At most four twos, at most one three, and no sevens or fives. The largest such divisor is $2^4 \cdot 3 = 48$. A $48 \times 48$ tile, $7$ across and $10$ along.
The greatest common divisor of $a$ and $b$ is the largest number that divides both. It is written $\gcd(a, b)$. If $\gcd(a, b) = 1$, the numbers are called coprime (or relatively prime): they have no common divisors except one.
The second half of the puzzle is about repetitions. One lighthouse flashes every $12$ seconds, another every $18$. They have just flashed together. When will that happen again? We need a number divisible by both $12$ and $18$, and the smallest one. Factorize again: $12 = 2^2 \cdot 3$, $18 = 2 \cdot 3^2$. This time each prime has to be taken as many times as it occurs in each of the numbers, that is, the maximum: $2^2 \cdot 3^2 = 36$. In $36$ seconds.
The least common multiple $\operatorname{lcm}(a, b)$ is the smallest natural number divisible by both $a$ and $b$.
What we did with the tiles and the lighthouses always works.
Let $a = p_1^{a_1} \cdots p_k^{a_k}$ and $b = p_1^{b_1} \cdots p_k^{b_k}$ (listing every prime that occurs in at least one of the numbers; an exponent $0$ means the prime isn't there). Then $\gcd(a, b) = p_1^{\min(a_1, b_1)} \cdots p_k^{\min(a_k, b_k)}$ and $\operatorname{lcm}(a, b) = p_1^{\max(a_1, b_1)} \cdots p_k^{\max(a_k, b_k)}$. Moreover, every common divisor of $a$ and $b$ divides their gcd, and every common multiple is divisible by their lcm.
In the chapter on primes we worked out what divisors look like: by uniqueness of factorization, $d$ divides $a$ if and only if $d = p_1^{c_1} \cdots p_k^{c_k}$ with $c_i \le a_i$ for each $i$. So $d$ is a common divisor when $c_i \le a_i$ and $c_i \le b_i$, that is, $c_i \le \min(a_i, b_i)$. The largest such divisor comes from taking each exponent as large as possible, $c_i = \min(a_i, b_i)$, which is the formula for the gcd. And every common divisor, having $c_i \le \min(a_i, b_i)$, divides this number.
Multiples work the same way: $m$ is divisible by $a$ if and only if each $p_i$ occurs in $m$ at least $a_i$ times. A common multiple must contain $p_i$ at least $\max(a_i, b_i)$ times; the smallest such number is the product of the $p_i^{\max(a_i, b_i)}$ (other primes would only make it bigger), and every common multiple is divisible by it.
For any natural numbers $a$ and $b$, $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b$.
By the previous statement, each prime $p_i$ occurs in the product $\gcd \cdot \operatorname{lcm}$ exactly $\min(a_i, b_i) + \max(a_i, b_i)$ times. Of the two numbers $a_i$ and $b_i$, one is the minimum and the other the maximum, so $\min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i$. That's how many times $p_i$ occurs in $a \cdot b$. The two numbers have the same factorization, so they are the same number.
The formula is useful because it means you hardly ever need to compute the lcm directly: the gcd is enough. Next we'll learn to find the gcd without any factorization, and the lcm will then follow by division.
What is $\operatorname{lcm}(12, 18)$?
$12 \cdot 18 = 216$ is a common multiple, but not the least: $36$ is also divisible by both numbers. By the formula $\operatorname{lcm} = \frac{12 \cdot 18}{\gcd(12, 18)} = \frac{216}{6} = 36$. The product equals the lcm only for coprime numbers.
The fraction puzzle
Back to $\frac{391}{527}$. We don't want to factorize. But there is an observation so simple it's almost embarrassing: if a number divides both $527$ and $391$, it also divides their difference $527 - 391 = 136$. Conversely, a common divisor of $391$ and $136$ divides their sum $527$. So the pairs $(527, 391)$ and $(391, 136)$ have exactly the same common divisors, and hence the same greatest one.
We replaced a big number by a smaller one, and the problem didn't change. We can keep going: subtract the smaller from the larger as long as possible. It's more convenient to subtract as many times as fits in one go, that is, to divide with remainder.
If $a = bq + r$, then the common divisors of $a$ and $b$ are exactly the common divisors of $b$ and $r$. In particular, $\gcd(a, b) = \gcd(b, r)$.
Euclid's idea: a common divisor is a common measure. If a measuring stick $d$ fits a whole number of times into both $a$ and $b$, it also fits into what is left of $a$ after several $b$ are taken away.
Let's see it through to the end:
$$\begin{aligned} 527 &= 1 \cdot 391 + 136, \\ 391 &= 2 \cdot 136 + 119, \\ 136 &= 1 \cdot 119 + 17, \\ 119 &= 7 \cdot 17 + 0. \end{aligned}$$The last non-zero remainder is $17$. That is $\gcd(527, 391)$, and the fraction simplifies: $\frac{391}{527} = \frac{23 \cdot 17}{31 \cdot 17} = \frac{23}{31}$. Four divisions and not a single factorization.
Euclid's algorithm finds $\gcd(a, b)$: divide the larger number by the smaller with remainder, then the smaller by the remainder, then the first remainder by the second, and so on. When a division comes out exact, the last divisor is the gcd you want.
Why does the algorithm always finish, and why does it end with the gcd in particular? There is a vivid picture for this: a rectangle from which squares are cut off.
For any natural numbers $a > b$, Euclid's algorithm stops after finitely many divisions, and the last non-zero remainder (or $b$ itself, if $a$ is divisible by $b$) equals $\gcd(a, b)$.
The idea: division with remainder is cutting squares off a rectangle, and a rectangle with whole-number sides can't shrink forever.
Below you can cut the same rectangle yourself, including the $527 \times 391$ one from our fraction, and see what happens if the sides have no common measure at all.
Find $\gcd(1071, 462)$ with Euclid's algorithm.
$1071 = 2 \cdot 462 + 147$, $462 = 3 \cdot 147 + 21$, $147 = 7 \cdot 21 + 0$. The last non-zero remainder is $21$. Check: $1071 = 21 \cdot 51$, $462 = 21 \cdot 22$, and $\gcd(51, 22) = 1$.
How fast is the algorithm? The remainders decrease, but could there be very many of them? Gabriel Lamé answered this in 1844.
If the smaller of two numbers has $k$ digits, Euclid's algorithm makes at most $5k$ divisions.
Proof of Lamé's theorem: the most "awkward" pairs are Fibonacci numbers
The idea: the algorithm runs longest when every quotient is $1$, and then the numbers, read from the end back to the start, grow at least as fast as the Fibonacci numbers $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, $F_4 = 3$, $5, 8, 13, \dots$, where each number is the sum of the two before it (more about them in the chapter on sequences).
Suppose the algorithm made $n$ divisions on the pair $a > b$. List the numbers it meets: $u_0 = a > u_1 = b > u_2 > \dots > u_n > u_{n+1} = 0$, where the $i$-th division is $u_{i-1} = q_i u_i + u_{i+1}$. The last non-zero remainder $u_n \ge 1 = F_2$, and $u_{n-1} > u_n$, so $u_{n-1} \ge 2 = F_3$. Every quotient $q_i \ge 1$, so $u_{i-1} \ge u_i + u_{i+1}$: each number is at least the sum of the next two. Working up from the end, we get $u_{n-2} \ge F_3 + F_2 = F_4$, $u_{n-3} \ge F_5$, and in general $u_{n-j} \ge F_{j+2}$. For $j = n - 1$: $b = u_1 \ge F_{n+1}$.
Fibonacci numbers grow at least as fast as powers of $\varphi = \frac{1 + \sqrt5}{2} \approx 1.618$: $F_m \ge \varphi^{m-2}$. For $m = 2$ and $m = 3$ you can see it directly ($1 \ge 1$, $2 \ge 1.618$), and further along the chain: $F_{m+1} = F_m + F_{m-1} \ge \varphi^{m-2} + \varphi^{m-3} = \varphi^{m-3}(\varphi + 1) = \varphi^{m-1}$, because $\varphi + 1 = \varphi^2$ (check: $\varphi^2 = \frac{6 + 2\sqrt5}{4} = \varphi + 1$). So $b \ge F_{n+1} \ge \varphi^{n-1}$.
If $b$ has exactly $k$ digits, then $b < 10^k$. And $\varphi^5 \approx 11.09 > 10$, so $10^k < \varphi^{5k}$. We get $\varphi^{n-1} < \varphi^{5k}$, that is, $n - 1 < 5k$ and $n \le 5k$.
The bound is sharp: the pair $(13, 8)$ needs five divisions, $(144, 89)$ ten, and $(1597, 987)$ fifteen.
For three-digit numbers that's at most fifteen divisions, for twenty-digit numbers at most a hundred. Factorizing a twenty-digit number by trial division would take billions of divisions. Lamé's theorem is often called one of the first analyses in history of how much work an algorithm needs.
Time to practise. At level one the numbers are small and easy to factorize; at level two they are the kind you can't handle without Euclid. If a problem won't come out, the solver will run the algorithm step by step.
The jug puzzle
By a fountain stand two jugs, one of $3$ litres and one of $5$, and there are no other measures. How do you measure out exactly $4$ litres? This is exactly the puzzle Bruce Willis and Samuel L. Jackson solve in the film Die Hard with a Vengeance (1995), only in gallons and with a bomb ticking. Pouring puzzles are much older: Niccolò Tartaglia was already analysing them in the sixteenth century.
Jugs of $3$ and $5$ litres give any whole amount from $0$ to $5$. But with jugs of $6$ and $10$ litres you can't measure five litres however hard you try. Why? At first both jugs are empty. Filling a jug gives $6$ or $10$ litres, an even number. Emptying gives zero. Pouring moves either the whole content of one jug or as much as the other needs to be full, and both are even if the jugs held even amounts before. So each jug always holds an even number of litres: every volume is divisible by $\gcd(6, 10) = 2$. And five isn't divisible by two.
Every volume that appears in the jugs has the form $3x + 5y$ with integers $x$ and $y$: full jugs are written that way, and pouring and emptying only add and subtract such numbers. For example, $4 = 3 \cdot 3 + 5 \cdot (-1)$: fill the small jug three times, pouring it into the big one each time, and empty the full big jug once. The jugs are a device for building such sums. Which numbers can be written in the form $ax + by$ at all?
For any natural numbers $a$ and $b$ there are integers $x$ and $y$ (one of them usually negative) with $ax + by = \gcd(a, b)$.
The idea: follow Euclid's algorithm and notice that each of its remainders is built from $a$ and $b$ with integer coefficients.
Bézout's identity writes the greatest common divisor in the form $ax + by$ with integers $x$ and $y$. It is named after Étienne Bézout (eighteenth century), who proved a similar statement for polynomials; for integers it was already known to Claude Gaspard Bachet de Méziriac, a collector of recreational problems in the early seventeenth century.
To find $x$ and $y$, run the same Euclid's algorithm backwards. Each of its equations expresses a remainder through the two previous numbers.
Example: Bézout's identity for 527 and 391
Write the equations of the algorithm with the remainder on the left: $136 = 527 - 391$, $119 = 391 - 2 \cdot 136$, $17 = 136 - 119$. Start with the last one and substitute the earlier ones:
$$\begin{aligned} 17 &= 136 - 119 \\ &= 136 - (391 - 2 \cdot 136) \\ &= 3 \cdot 136 - 391 \\ &= 3 \cdot (527 - 391) - 391 \\ &= 3 \cdot 527 - 4 \cdot 391. \end{aligned}$$Check: $3 \cdot 527 = 1581$, $4 \cdot 391 = 1564$, and the difference is $17$.
This procedure is called the extended Euclidean algorithm.
The equation $ax + by = c$ with natural $a$, $b$ and integer $c$ has a solution in integers if and only if $c$ is divisible by $\gcd(a, b)$.
Write $d = \gcd(a, b)$; there are two directions to prove.
If there is a solution, then $d$ divides $a$ and hence $ax$; likewise $d$ divides $by$. Then $d$ divides the sum $ax + by = c$.
Conversely, let $c$ be divisible by $d$: $c = d \cdot t$. By Bézout's identity there are integers $x_0$, $y_0$ with $ax_0 + by_0 = d$. Multiply this equation by $t$: $a(x_0 t) + b(y_0 t) = dt = c$. The pair $x = x_0 t$, $y = y_0 t$ is a solution.
Equations that have to be solved in integers are called Diophantine equations, after Diophantus of Alexandria (around the third century AD), author of the Arithmetica. Diophantus himself usually looked for rational solutions, but the name stuck.
Let's go back to the jugs and answer the question completely.
With jugs of $a$ and $b$ litres, $a \le b$, you can measure out $c$ litres ($0 < c \le b$) if and only if $c$ is divisible by $\gcd(a, b)$.
Write $d = \gcd(a, b)$.
Necessity. We show that each jug always holds a multiple of $d$ litres. At the start each holds zero. Filling a jug gives $a$ or $b$ litres, a multiple of $d$. Emptying gives zero. When pouring, what moves is either the whole content of one jug or as much as the other needs to be full, that is, capacity minus content. If both jugs held multiples of $d$ before, then the amount poured and the new contents are multiples of $d$ too. So a volume that isn't a multiple of $d$ never appears.
Sufficiency. If $c = b$, just fill the big jug. Let $c < b$ and $c = dt$. Follow one rule: if the small jug is empty, fill it; pour from the small jug into the big one; if the big jug is full, empty it and carry on pouring. Once the water of $k$ filled small jugs has passed into the big one, it holds the remainder of $ka$ on division by $b$: $ka$ litres went in altogether, and each time we emptied it, it was full, $b$ litres. It remains to find a $k$ for which this remainder is $c$. By Bézout's identity $ax + by = d$ with integers $x$, $y$; multiply by $t$: $a \cdot xt = c - b \cdot yt$. Add a large enough multiple of $b$ to $xt$ to get a natural number $k = xt + bm$. Then $ka = c + b(am - yt)$, and since $0 \le c < b$, by uniqueness of division with remainder the remainder of $ka$ on division by $b$ is $c$. After the $k$-th small jug the big one holds exactly $c$ litres.
With jugs of $3$ and $5$ any volume up to five litres works; with $6$ and $10$, only even ones.
What is the smallest non-zero volume you can measure with jugs of $9$ and $12$ litres?
All volumes have the form $9x + 12y$ and are divisible by $\gcd(9, 12) = 3$, and the gcd itself can be obtained by Bézout's identity: $9 \cdot (-1) + 12 \cdot 1 = 3$, so fill the big jug and pour from it into the small one. Answer: $3$ litres.
Euclid's lemma once more
In the chapter on primes Euclid's lemma was proved without any gcd, using the smallest "suitable" number. Bézout's identity gives a two-line proof, and of a more general statement at once, which we'll need for the coins.
If $a$ divides a product $bc$ and $\gcd(a, b) = 1$, then $a$ divides $c$.
By Bézout's identity $ax + by = 1$ for some integers $x$, $y$. Multiply by $c$: $acx + bcy = c$. The first term is divisible by $a$ because it contains the factor $a$; the second because $a$ divides $bc$. So $a$ divides their sum $c$.
If a prime $p$ divides a product $bc$, then $p$ divides $b$ or $p$ divides $c$.
Suppose $p$ doesn't divide $b$. A common divisor of $p$ and $b$ is a divisor of the prime $p$, so it's $1$ or $p$; but $p$ doesn't divide $b$, so $\gcd(p, b) = 1$. By the generalized lemma, $p$ divides $c$.
In Euclid the lemma appears in Book VII as Proposition 30, the same book as the algorithm. The uniqueness of prime factorization from the last chapter rests on it. And in "Hilbert's world" from that chapter you can't subtract numbers without leaving the world ($9 - 5 = 4$ isn't in it), so there's neither Euclid's algorithm nor Bézout's identity, and uniqueness collapses.
The coin puzzle
In some country the only coins are $3$ and $5$ roubles. Which amounts can be paid exactly, without change?
Let's go through them: $3$, $5$, $6 = 3 + 3$, $8 = 3 + 5$, $9$, $10$, $11 = 3 + 3 + 5$, $12$, $13 = 3 + 5 + 5$… The amounts $1$, $2$, $4$ and $7$ don't work. But from eight on, everything does: $8$, $9$ and $10$ can be made, and after that it's enough to keep adding threes. Any three consecutive amounts you can make pull all the later ones along with them.
Let the natural numbers $a$ and $b$ be coprime. Then every integer greater than $ab - a - b$ can be written as $ax + by$ with non-negative integers $x$ and $y$, while $ab - a - b$ itself cannot.
The idea: sort all the amounts into $a$ columns by their remainder on division by $a$, and find in each column the first amount that can be made.
This is called the Frobenius problem, after the German mathematician Ferdinand Georg Frobenius, who, the story goes, liked to pose it in his lectures. For two coins the answer was known to James Sylvester in the 1880s. He also found how many amounts can't be made.
If $a$ and $b$ are coprime, exactly $\frac{(a - 1)(b - 1)}{2}$ amounts can't be made with coins $a$ and $b$: half of the numbers from $0$ to $ab - a - b$.
Proof: the amounts split into pairs
The idea: split the numbers from $0$ to $g = ab - a - b$ into pairs $n$ and $g - n$ and show that exactly one number in each pair can be made.
By the second step of the proof of the Frobenius theorem, every integer $n$ can be written uniquely as $n = xa + yb$ with integer $x$ and $0 \le y \le a - 1$: $yb$ is the marked number of the column where $n$ sits, and $x$ is how many cells below it $n$ is (negative $x$ means above). By the fourth step, $n$ can be made exactly when $x \ge 0$.
For the other number of the pair: $g - n = ab - a - b - xa - yb = (-x - 1)a + (a - 1 - y)b$, and again $0 \le a - 1 - y \le a - 1$. So for $g - n$ the role of $x$ is played by $-x - 1$, which is non-negative exactly when $x$ is negative. Of the two numbers in the pair, exactly one can be made.
There are $g + 1 = (a - 1)(b - 1)$ numbers from $0$ to $g$. This number is even (of two coprime numbers $a$ and $b$ at least one is odd, and the corresponding factor $a - 1$ or $b - 1$ is even), so $n$ and $g - n$ never coincide, and the numbers split into $\frac{(a - 1)(b - 1)}{2}$ pairs. In each pair one number can't be made, and there are no such numbers beyond $g$. For coins $3$ and $5$ that's four amounts: $1$, $2$, $4$ and $7$.
The coins in use are $5$ and $7$ roubles. What is the largest amount that can't be paid with them exactly?
$\gcd(5, 7) = 1$, so the formula applies: $5 \cdot 7 - 5 - 7 = 23$. Check: $23$, $23 - 7 = 16$, $23 - 14 = 9$, $23 - 21 = 2$; none of them is divisible by $5$, so $23$ can't be made. But $24 = 5 \cdot 2 + 7 \cdot 2$, $25 = 5 \cdot 5$, $26 = 5 + 7 \cdot 3$, $27 = 5 \cdot 4 + 7$, $28 = 7 \cdot 4$: five in a row, and from there just add fives.
With three coin values the problem becomes genuinely hard: there is no formula of the same simple kind. The best-known example is McDonald's chicken nuggets, once sold in boxes of $6$, $9$ and $20$. Any number greater than $43$ can be bought this way, but exactly $43$ can't. This number is jokingly called the McNugget number.
Where next
We've learned to find out whether one number divides another, to find common divisors and multiples, and to solve equations in integers. But not every division comes out exact. Seven pies for three people: two each, and one pie is left over. If we don't want it to go to waste, we'll have to cut it into parts, and along the way understand what $\frac13$ is and why its decimal expansion never ends. That's fractions, where the gcd and lcm will be needed at every step.