Задача 2. Пары и делимость на сумму

Выносим общий делитель

Делимость удобнее изучать, когда числа «очищены» от общего множителя. Пусть $d = \text{НОД}(a, b)$, $a = dx$, $b = dy$, где $x < y$ и $\text{НОД}(x, y) = 1$. Тогда

Условие «$ab$ делится на $a + b$» после сокращения на $d$ означает: $d \cdot xy$ делится на $x + y$.

x + y и xy взаимно просты

Пусть простое число $q$ делит и $x + y$, и $xy$. Раз $q$ делит произведение $xy$, оно делит $x$ или $y$ — скажем, $x$. Но тогда $q$ делит и $y = (x + y) - x$, то есть $q$ — общий делитель взаимно простых $x$ и $y$. Противоречие.

Значит, у $x + y$ и $xy$ нет общих простых делителей, и раз $x + y$ делит $d \cdot xy$, то $x + y$ делит само $d$:

Общий вид всех пар

Подставим $d = m(x + y)$:

где $x < y$ взаимно просты, $m \geqslant 1$. Обратно, любая такая пара подходит: $\dfrac{ab}{a + b} = \dfrac{m^2 xy (x + y)^2}{m (x + y)^2} = m \cdot xy$ — целое число. Значит, нужно просто сосчитать такие пары с $b \leqslant 30$. Пары с одними и теми же $x$, $y$ лежат на одном луче $b = \dfrac{y}{x} a$ (рисунок).

Перебор

Самое маленькое $b$ для данных $x, y$ получается при $m = 1$ и равно $y(x + y)$. Так как $x \geqslant 1$, оно не меньше $y(y + 1)$, поэтому сначала ограничим $y$:

ведь $5 \cdot 6 = 30$, а $6 \cdot 7 = 42 > 30$. Кроме того, $y \geqslant 2$, потому что $1 \leqslant x < y$. Теперь для каждого $y$ от $2$ до $5$ переберём все взаимно простые с ним $x < y$; при каждых $x, y$ годятся $m = 1, 2, \ldots$, пока $b = m \cdot y(x + y) \leqslant 30$.

• $y = 2$: только $x = 1$, $y(x + y) = 6$, $m = 1, \ldots, 5$: $(3; 6)$, $(6; 12)$, $(9; 18)$, $(12; 24)$, $(15; 30)$ — $5$ пар.
• $y = 3$: $x = 1$, $y(x + y) = 12$, $m = 1, 2$: $(4; 12)$, $(8; 24)$ — $2$ пары; $x = 2$, $y(x + y) = 15$, $m = 1, 2$: $(10; 15)$, $(20; 30)$ — $2$ пары.
• $y = 4$: $x = 1$, $y(x + y) = 20$: $(5; 20)$ — $1$ пара; $x = 2$ не взаимно просто с $4$; $x = 3$, $y(x + y) = 28$: $(21; 28)$ — $1$ пара.
• $y = 5$: $x = 1$, $y(x + y) = 30$: $(6; 30)$ — $1$ пара; уже $x = 2$ даёт $b \geqslant 5 \cdot 7 = 35 > 30$, а $x = 3, 4$ — ещё больше.

Так перебраны все возможные $y$ и при каждом $y$ — все $x$, поэтому других пар нет. Всего $5 + 2 + 2 + 1 + 1 + 1 = 12$ пар.