Делимость целых чисел и остатки

Пример 5.1. ЕГЭ-2020, тренировочный вариант, 19. Произведение нескольких различных простых чисел делится на каждое из этих чисел, уменьшенное на 1. Чему может быть равно это произведение? Решение. Произведение нескольких простых чисел может делиться лишь на эти простые числа и 1. Это означает, что каждое из этих простых чисел, уменьшенное на 1, является либо другим простым числом из набора, либо произведением нескольких из них, либо 1. Единственное простое число, при уменьшении которого на 1 получается также простое число, это 3. Единственное число, при уменьшении которого на 1 получается 1, это 2. Таким образом, первый ответ $2 \cdot 3 = \fbox{6}$. Следующий ответ получится, если предыдущий ответ, увеличенный на 1, является простым числом. Поскольку $6 + 1 = 7$ — простое число, то второй ответ: $2 \cdot 3 \cdot 7 = \fbox{42}$. Следующим членом произведения может стать либо $2 \cdot 7 + 1$, либо $3 \cdot 7 + 1$, либо $2 \cdot 3 \cdot 7 + 1$, если это простые числа. Числа $2 \cdot 7 + 1 = 15$, $3 \cdot 7 + 1 = 22$ — не являются простыми. Число $2 \cdot 3 \cdot 7 + 1 = 43$ — простое, поэтому третий ответ $2 \cdot 3 \cdot 7 \cdot 43 = \fbox{1806}$. Поскольку $2 \cdot 43 + 1$, $3 \cdot 43 + 1$, $2 \cdot 3 \cdot 43 + 1$, $2 \cdot 7 \cdot 43 + 1$, $3 \cdot 7 \cdot 43 + 1$ и $2 \cdot 3 \cdot 7 \cdot 43 + 1$ — не являются простыми числами, то больше таких чисел нет. Ответ: 6, 42, 1806. Пример 5.2. Пусть $q$ — наименьшее общее кратное, а $d$ — наибольший общий делитель натуральных чисел $x$ и $y$, удовлетворяющих равенству $7x = 16y - 73$. а) Может ли $\frac{q}{d}$ быть равным 204? б) Может ли $\frac{q}{d}$ быть равным 2? в) Найдите наименьшее значение $\frac{q}{d}$. Решение. а) Если $d = НОД(x, y)$, $q = НОК(x, y)$, то справедливо представление $$ x = ud, \quad y = vd, \quad q = duv, $$ где $u, v$ — натуральные числа, взаимно простые. Подставим это представление в уравнение $$ 7x = 16y - 73 \implies 7ud = 16vd - 73 \implies d(16v - 7u) = 73. $$ Решим это уравнение в целых числах, учитывая, что 73 — простое число. 1) $d = 1, \quad 16v - 7u = 73 \implies v = \frac{73 + 7u}{16}$, $\frac{q}{d} = wv = \frac{(73 + 7u)u}{16} = 204 \implies 7u^2 + 73u - 16 \cdot 204 = 0 \implies$ $u = \frac{-73 \pm \sqrt{73^2 + 28 \cdot 16 \cdot 204}}{14} = \frac{-73 \pm 311}{14} \implies$ $\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad u = 17, \ v = \frac{73 + 7 \cdot 17}{16} = 12$. Отсюда $x = 17, \ y = 12 \ НОД(17, 12) = 1, \ НОК(17, 12) = 204$. . 2) $d = 73, \ 16v - 7u = 1$ можно не рассматривать; так как уже доказано существование в 1). б) Проведем рассуждения аналогично а). 1) $d = 1, \quad 16v - 7u = 73 \implies v = \frac{73 + 7u}{16}, \quad \frac{q}{d} = uv = \frac{(73 + 7u)u}{16} = 2$ $\implies 73u + 7u^2 = 32 \implies 7u^2 + 73u - 32 = 0 \implies$ $u = \frac{-73 \pm \sqrt{73^2 + 28 \cdot 32}}{14}$ — нет натуральных решений. 2) $d = 73, \quad 16v - 7u = 1 \implies v = \frac{1 + 7u}{16}, \quad \frac{q}{d} = uv = \frac{(1 + 7u)u}{16} = 2$ $\implies 7u^2 + u - 32 = 0 \implies u = \frac{-1 \pm \sqrt{1 + 28 \cdot 32}}{14}$ — нет натуральных решений. . в) Рассмотрим сначала, аналогично предыдущим пунктам возможные значения $d$ из уравнения $d(16v - 7u) = 73$. 1) $d = 1$. Минимальное значение $u$ найдем из выражения $v = \frac{73 + 7u}{16}$. Путем подбора находим $u = 1$, тогда $$ v = \frac{80}{16} = 5 \implies \boxed{\frac{q}{d} = 5}. $$ В этом случае $$ x = u = 1, \quad y = v = 5, \quad НОД(1, 5) = 1, \quad НОК(1, 5) = 5, \quad \frac{q}{d} = 5. $$ 2) $d = 73$. Тогда $16v - 7u = 1 \implies v = \frac{1 + 7u}{16}$. Подбором находим $$ u = 9, \implies v = \frac{64}{16} = 4. $$ В этом случае $$ x = 73u = 73 \cdot 9 = 657, \quad y = 73v = 73 \cdot 4 = 292, $$ $$ НОД(657, 292) = 73, \quad НОК(657, 292) = 2628, \quad \frac{q}{d} = \frac{2628}{73} = 36. $$ Таким образом, минимальное значение $\boxed{\frac{q}{d} = 5}$. Ответ: а) да; б) нет; в) 5. Пример 5.3. ЕГЭ-2020, тренировочный вариант, 19. а) Приведите пример такого натурального числа $n$, что числа $n^2$ и $(n + 16)^2$ дают одинаковый остаток при делении на 200. б) Сколько существует трёхзначных чисел $n$ с указанным в пункте а) свойством? в) Сколько существует двухзначных чисел $m$, для каждого из которых существует ровно 36 трёхзначных чисел $n$, таких, что $n^2$ и $(n + m)^2$ дают одинаковый остаток при делении на 200. Решение. а) Если числа дают одинаковый остаток при делении на 200 это означает, что их разность делится на 200: $$\begin{aligned} (n + 16)^2 - n^2 &= 200k \implies n^2 + 32n + 256 - n^2 = 200k \implies \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad 4n + 32 = 25k. \end{aligned}$$ Так как левая часть делится на 4 без остатка, то $k \ \vdots \ 4$. При $k = 4$ получаем $n = 17$. , например, $n = 17$. б) Согласно рассуждениям предыдущего пункта $k \ \vdots \ 4 \implies k = 4l$. Тогда $n + 8 = 25l \implies n = 25l - 8$. Чтобы $n$ было трехзначным $5 \le l \le 40$, разным $l$ соответствуют разные $n$, таким образом подходящих чисел $l$ будет...