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

Пример 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 будет 36, следовательно и нужных трехзначных чисел будет .

в) Поскольку (n+m)^2 и n^2 при делении на 200 дают одинаковый остаток, то их разность должна делиться на 200 без остатка: \frac{(n + m)^2 - n^2}{200} = \frac{m(2n + m)}{200} = \frac{2nm + m^2}{200} — целое, отсюда следует, что m — четное, следовательно, m = 2k . Тогда \frac{4nk + 4k^2}{200} = \frac{nk + k^2}{50} = \frac{k(n + k)}{2 \cdot 25} — целое. Так как m двузначное, то 5 \le k \le 49 .

1) Если k = 25 , то n — любое трехзначное, их больше, чем 36.

2) Если k \neq 25 , но k \ \vdots \ 5 , то или n + k \ \vdots \ 10 , или k \ \vdots \ 10 . Тогда подойдут либо все четные числа, кратные 5, либо все нечетные, кратные 5. В любом случае их больше 36.

3) Пусть k не кратно 5, k — нечетное, но сумма (n + k) \ \vdots \ 50 . Так как k \in [5; 49] , то 150 \le n + k \le 1000 принимает все значения, кратные 50, причем каждому значению n+k соответствует только одно значение m . Следовательно, для каждого k возможно 18 значений n , что не подходит по условию.

4) Пусть k не кратно 5, k — четное, и сумма (n+k) кратна 25. Рассуждая аналогично п. 3) при k \in [6; 24] и (n + k) \in [125; 1000] , получим, что возможных значений (n + k) будет 36, поэтому возможных значений n также 36. Таким образом, подходящие k — четные от 6 до 24. При k \in [26; 48] и (n + k) \in [150; 1025] возможных значений (n + k) также 36, поэтому возможных значений n тоже 36.

Таким образом наберется 18 подходящих k , четных, но не кратных 5.

Ответ: а) 17; б) 36; в) 18.

Пример 5.4.

ЕГЭ-2020, тренировочный вариант, 19.

По кругу в некотором порядке по одному разу написаны числа от 10 до 21. Для каждой из двенадцати пар соседних чисел нашли их наибольший общий делитель.

а) Могло ли получиться так, что все наибольшие общие делители равны 1?

б) Могло ли получиться так, что все наибольшие общие делители попарно различны?

в) Какое наибольшее количество попарно различных наибольших общих делителей могло при этом получиться?

Решение.

а) Да, можно, например, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 или 10, 21, 20, 19, 16, (опечатка OCR, текст обрывается)

б) Среди чисел есть простые (11, 13, 17, 19), наибольшие общие делители у них со всеми остальными будут 1, поэтому все наибольшие общие делители не могут быть попарно различны.

в) Среди чисел есть 4 простых (11, 13, 17, 19). Каждое из этих чисел имеет соседей, поэтому хотя бы 5 из наибольших общих делителей будут равняться 1, то есть совпадать. Следовательно, не может быть более 8 попарно различных наибольших общих делителей из 13, а, по крайней мере, 5 совпадают. Для расстановки 10, 20, 19, 17, 13, 11, 18, 12, 16, 14, 21, 15 получается ровно 8 попарно различных общих делителей.

Ответ: а) Да; б) нет; в) восемь.