Числа и делимость — ДВИ

Задачи в целых числах и делимость

На ДВИ по математике задачи на числа делятся на два больших класса. Первый — собственно делимость: разложение на простые множители, работа с НОД и НОК, признаки делимости, сравнения по модулю и остатки. Второй — уравнения в целых числах (диофантовы): от простейших линейных $a x + b y = c$ до уравнений второй степени с двумя-тремя переменными. В отличие от школьной программы, здесь требуется уметь разлагать сложные многочлены на множители, анализировать остатки от деления, пользоваться алгоритмом Евклида и применять свойства квадратного трёхчлена для ограничения перебора.

Часть I. Аппарат делимости

Прежде чем решать уравнения, нужен фундамент: как устроена делимость целых чисел. На ДВИ эти факты применяют без вывода, но ссылаться на них в решении обязательно — иначе под рубрику «±» теряются баллы за необоснованные переходы.

Свойства делимости

ВАЖНОЕ

Базовые свойства делимости

Пусть $a, b, c \in Z,$ $a \neq = 0 .$ Тогда (см. справочник, раздел «Числа и делимость»):

a ∣ b и a ∣ c ⟹ a ∣ (b \pm c), a ∣ b ⟹ a ∣ b c .

Если $p$ — простое и $p ∣ ab,$ то $p ∣ a$ или $p ∣ b$ (лемма Евклида).
Основная теорема арифметики: всякое натуральное $n > 1$ единственным образом (с точностью до порядка) раскладывается в произведение простых:

n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}} .

Из канонического разложения сразу получают число и сумму делителей.

ВАЖНОЕ

Число и сумма делителей

Если $n = p_{1}^{α_{1}} \dots p_{k}^{α_{k}},$ то количество натуральных делителей равно

τ (n) = (α_{1} + 1) (α_{2} + 1) \dots (α_{k} + 1),

а сумма всех натуральных делителей равна

σ (n) = i = 1 \prod k \frac{p _{i}^{α_{i} + 1} - 1}{p _{i} - 1} .

НОД, НОК и алгоритм Евклида

ВАЖНОЕ

НОД, НОК и алгоритм Евклида

Через каноническое разложение: НОД берёт минимальные степени общих простых, НОК — максимальные. Связь:

НОД (a, b) \cdot НОК (a, b) = ab (a, b \in N) .

Алгоритм Евклида (не требует разложения на простые):

НОД (a, b) = НОД (b, a mod b),

повторять, пока остаток не станет $0;$ последний ненулевой остаток и есть НОД. Числа $a, b$ называют взаимно простыми, если $НОД (a, b) = 1 .$

ПРИМЕР 1

НОД алгоритмом Евклида и каноническим разложением

Условие. Найдите $НОД (1071, 462)$ и $НОК (1071, 462) .$

Сравнения по модулю

ВАЖНОЕ

Сравнения и остатки

a \equiv b (mod m) ⟺ m ∣ (a - b) .

Сравнения по одному модулю можно складывать, вычитать, умножать и возводить в степень:

a \equiv b, c \equiv d ⟹ a \pm c \equiv b \pm d, a c \equiv b d, a^{n} \equiv b^{n} (mod m) .

Делить на общий множитель нельзя без оговорок (только на взаимно простой с модулем).

Главный рабочий инструмент метода остатков — таблицы остатков квадратов и кубов. Запоминай их как факт (лист формул на ДВИ не выдают).

ВАЖНОЕ

Таблица остатков квадратов и кубов

$n$	возможные остатки $x^{2} mod n$	пояснение
$3$	${0, 1}$	остаток $2$ невозможен
$4$	${0, 1}$	остатки $2,$ $3$ невозможны
$8$	${0, 1, 4}$	нечётный квадрат $\equiv 1;$ чётный $\equiv 0$ или $4$

Для кубов: $x^{3} mod 9 \in {0, 1, 8} .$

В отличие от исходной версии конспекта здесь приведён полный набор остатков по модулю $8 :$ у чётного квадрата остаток равен $0$ или $4$ (а не только нечётный случай). Этот факт работает в задачах про сумму квадратов — см. Пример 7.

Круговая диаграмма-«циферблат» остатков по модулю 8

Часть II. Линейные диофантовы уравнения

Самый частый сюжет темы «делимость». Уравнение $a x + b y = c$ ( $a, b, c \in Z$ ) ищем в целых числах.

ВАЖНОЕ

Критерий разрешимости и общее решение

a x + b y = c разрешимо в целых ⟺ d ∣ c, где d = НОД (a, b) .

Если решение есть, частное $(x_{0}, y_{0})$ находят через алгоритм Евклида (обратный ход), а все решения задаёт формула (см. справочник):

x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t, t \in Z .

ПРИМЕР 2

Линейное диофантово уравнение

Условие. Решите в целых числах уравнение $15 x + 21 y = 6 .$

!ЧАСТАЯ ОШИБКА

Забыл проверить критерий

d ∣ c

Ошибка: начать перебирать или искать частное решение для уравнения вроде $6 x + 9 y = 4,$ не заметив, что $НОД (6, 9) = 3,$ а $3 ∤ 4 .$
Правильно: левая часть всегда кратна $d = НОД (a, b),$ поэтому при $d ∤ c$ решений нет — это пишется сразу, в одну строку. Пропуск этой проверки на ДВИ — типичная потеря балла «на ровном месте».

Часть III. Уравнения второй степени: три метода

Для уравнений с квадратами переменных на ДВИ чаще всего применяются три метода: разложение на множители, метод дискриминанта (оценок) и метод остатков.

ВАЖНОЕ

Разложение на множители

Если уравнение можно привести к виду $(a x + b y + c) (d x + ey + f) = N,$ где $N$ — целое число, то задача сводится к перебору всех пар делителей числа $N .$
Помогают формулы сокращённого умножения и группировка:

a^{2} - b^{2} = (a - b) (a + b)

x y + a x + b y + ab = x (y + a) + b (y + a) = (x + b) (y + a)

ВАЖНОЕ

Метод дискриминанта (оценка мажорантой)

Если уравнение имеет вид $a x^{2} + b x y + c y^{2} + d x + ey + f = 0,$ его можно рассматривать как квадратное относительно $x .$

A x^{2} + B (y) x + C (y) = 0

Чтобы существовал действительный корень $x,$ необходимо $D (y) ⩾ 0 .$ Это неравенство часто задаёт узкий отрезок, ограничивающий возможные целые значения $y .$
Более того, для целого $x$ дискриминант $D (y)$ должен быть точным квадратом целого числа: $D (y) = k^{2}$ — но с важной оговоркой об обосновании (см. ниже).

✓СОВЕТ

Почему «целый

x

\Rightarrow

D

— точный квадрат» (обоснование)

Этот переход не очевиден и на ДВИ требует обоснования. Записав уравнение как квадратное с приведённым старшим коэффициентом $1$ (т.е. в виде $x^{2} + B x + C = 0$ с целыми $B, C$ ), мы по теореме о рациональных корнях получаем: всякий рациональный корень приведённого целочисленного многочлена автоматически целый. Значит, корень $x = \frac{- B \pm D}{2}$ цел тогда и только тогда, когда $D$ — целое число, то есть $D$ — точный квадрат.

Важно: если старший коэффициент при $x$ не равен $1$ (уравнение неприведённое), требования « $D$ — точный квадрат» недостаточно — нужна дополнительная проверка делимости числителя $- B \pm D$ на $2 A .$ В исходной формулировке этой оговорки не было — её пропуск штрафуется.

ВАЖНОЕ

Остатки квадратов

При анализе нерешаемых уравнений помогает взятие остатков по модулю 3, 4 или 8 (полная таблица — в Части I):

x^{2} mod 3 \in {0, 1}, x^{2} mod 4 \in {0, 1}, x^{2} mod 8 \in {0, 1, 4} .

Нечётный квадрат при делении на 8 всегда даёт остаток $1;$ чётный — $0$ или $4 .$

Алгоритм решения уравнения второй степени

АЛГОРИТМ

Как подходить к целочисленному уравнению

1. Проверь остатки. Если уравнение выглядит как $x^{2} + 3 y^{2} = 17$ (сумма квадратов с коэффициентами), проверь остатки по модулю 3, 4 или 8. Возможно, решений просто нет.
2. Попробуй разложить на множители. Собери члены с переменными вместе и попытайся вынести общие скобки так, чтобы справа осталось только целое число $N .$ Затем перебери все пары делителей $N$ (включая отрицательные).
3. Запиши квадратное уравнение. Если группировка не удаётся, но есть квадраты переменных, запиши уравнение как квадратное относительно одной из них. Найди дискриминант.
4. Оцени дискриминант. Реши неравенство $D ⩾ 0 .$ Найди все целые числа на полученном отрезке.
5. Проверь полные квадраты. Подставь найденные целые значения в $D .$ Оставь только те, при которых $D$ является точным квадратом (с обоснованием через приведённость), и дорешай уравнение.

Примеры

ПРИМЕР 3

Группировка и разложение (с полным перебором систем)

Условие. Реши в целых числах уравнение $2 x^{2} + x y - y^{2} - 3 x + 3 y = 6 .$

ПРИМЕР 4

Оценка через дискриминант

Условие. Найдите все пары целых чисел $(x, y),$ удовлетворяющие уравнению
$x^{2} - 2 x (y + 1) + 3 y^{2} - 2 y - 1 = 0 .$

ПРИМЕР 5

Метод остатков (модуль 3)

Условие. Докажите, что уравнение $x^{2} - 3 y^{2} = 17$ не имеет решений в целых числах.

ПРИМЕР 6

Линейное уравнение + ограничение (комбинированный приём)

Условие. Найдите все натуральные числа $x, y,$ для которых $3 x + 5 y = 47 .$

ПРИМЕР 7

Модуль 8: сумма двух квадратов

Условие. Докажите, что число вида $8 k + 7$ ( $k \in Z$ ) нельзя представить в виде суммы двух квадратов целых чисел.

ПРИМЕР 8

Метод бесконечного спуска

Условие. Докажите, что уравнение $x^{2} + y^{2} = 3 z^{2}$ не имеет решений в целых числах, кроме $x = y = z = 0 .$

ПРИМЕР 9

Последняя цифра и периодичность степеней

Условие. Найдите последнюю цифру числа $7^{2026} .$

Частые ошибки

!ЧАСТАЯ ОШИБКА

Потеря отрицательных делителей

Ошибка: получить уравнение $(x - 1) (y + 2) = 5$ и рассматривать только случаи $1 \cdot 5$ и $5 \cdot 1 .$
Правильно: число 5 также делится на отрицательные числа. Обязательно проверяй системы с множителями $(- 1) \cdot (- 5)$ и $(- 5) \cdot (- 1) .$ На ДВИ за потерю отрицательных случаев сразу снижают балл до существенного недочёта или ниже.

!ЧАСТАЯ ОШИБКА

Деление на переменную в диофантовом уравнении

Ошибка: из $x y = 4 x + 3$ выразить $y = 4 + \frac{3}{x}$ и сказать, что $x$ должен быть делителем тройки (то есть $\pm 1, \pm 3$ ).
Правильно: этот метод работает, но требует проверки $x \neq = 0 .$ Если ты делишь на выражение с переменной, обязательно пиши ОДЗ и проверяй случай равенства нулю отдельно. Безопаснее переносить всё влево и группировать: $x y - 4 x = 3 ⟹ x (y - 4) = 3 .$

!ЧАСТАЯ ОШИБКА

Молча выкинуть «лишние» системы вместо явной отбраковки

Ошибка: при переборе делителей $N$ дойти до системы, дающей нецелые $x, y,$ и просто не записать её, оставив в ответе только «удачные» пары.
Правильно: под рубрику ДВИ полнота решения требует выписать все пары делителей и явно пометить отбракованные («система даёт $x = 5/3$ — нет целых решений»), как в таблице Примера 3. Молчаливый пропуск читается экспертом как незавершённый перебор и стоит баллов.

!ЧАСТАЯ ОШИБКА

D ⩾ 0

принято за достаточное условие

Ошибка: найдя в методе дискриминанта отрезок из $D ⩾ 0,$ сразу выписать все целые $y$ как решения, забыв, что для целого $x$ дискриминант обязан быть точным квадратом.
Правильно: $D ⩾ 0$ лишь сужает перебор; затем для каждого целого $y$ проверяй, является ли $D$ точным квадратом (и помни об оговорке про приведённость уравнения — см. блок-обоснование выше).

!ЧАСТАЯ ОШИБКА

Спутать

Z

N

Ошибка: условие требует натуральных решений, а ты выписываешь все целые (включая отрицательные и ноль), либо наоборот — ищешь только положительные, когда разрешены любые целые.
Правильно: в первой же строке решения зафиксируй, в каком множестве ищешь корни, и в конце отсей не подходящие по знаку/нулю. Это частый «технический» недочёт ровно на стыке делимости и перебора.

Что запомнить

Делимость: $a ∣ b, a ∣ c \Rightarrow a ∣ (b \pm c);$ каноническое разложение единственно; НОД считается алгоритмом Евклида, $НОД \cdot НОК = ab .$
Линейное $a x + b y = c$ разрешимо $⟺ НОД (a, b) ∣ c;$ общее решение $x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t .$
Если перед тобой многочлен с двумя переменными второй степени, сгруппируй его в $(A) (B) = N$ и перебери все делители $N$ (включая отрицательные), явно отбраковывая нецелые.
Если группировка оставляет квадраты, пиши дискриминант. Условие $D ⩾ 0$ почти всегда ограничит одну переменную до 2-4 целых значений; затем требуй, чтобы $D$ был точным квадратом.
Остатки квадратов: $mod 3 \in {0, 1},$ $mod 4 \in {0, 1},$ $mod 8 \in {0, 1, 4} .$ Это самый мощный фильтр для уравнений, которые вообще не имеют решений; куб $mod 9 \in {0, 1, 8} .$
Для доказательства «решений нет» сверх остатков работает спуск; для степеней — периодичность остатков (последняя цифра).

Оформление под рубрику ДВИ

ДВИ оценивают по outcomes-рубрике «±»: важен не только верный ответ, но и полнота и обоснованность записи. Числовые задачи теряют баллы именно на пропущенных шагах перебора и недоказанных переходах.

АЛГОРИТМ

Эталон полного решения числовой задачи

1. Зафиксируй множество поиска ( $Z$ или $N$ ) и при необходимости ОДЗ (если делишь на переменную).
2. Сошлись на критерий/факт делимости явно: « $НОД (a, b) = d,$ $d ∣ c,$ значит решения есть» или « $x^{2} mod 3 \in {0, 1}$ ».
3. Преобразование с обоснованием: разложил в $(A) (B) = N$ — назови, почему скобки целые; перешёл к дискриминанту — отметь приведённость уравнения.
4. Полный перебор: выпиши ВСЕ пары делителей / все целые $y$ на отрезке. Отбракованные пометь явно («нет целых решений»), не удаляй из записи.
5. Ответ полным перечнем всех пар $(x, y)$ и проверка подстановкой хотя бы одной (а в доказательствах несуществования — чёткое «получили противоречие»).

!ЧАСТАЯ ОШИБКА

За что снимают «±» на числовых задачах

Найден верный отрезок/факторизация, но перебор неполон (часть систем не выписана) — частичный балл вместо полного.
Переход «целый $x$ $\Rightarrow$ $D$ — точный квадрат» использован без обоснования приведённостью — снимают за необоснованный шаг.
Деление на переменную без оговорки $x \neq = 0$ / ОДЗ — потеря случая, существенный недочёт.
Найдены целые решения, но не отсеяны не подходящие под $N$ (или потеряны отрицательные при $Z$ ).
В задаче «решений нет» сказано «перебрал — не нашёл» без доказательства (остатки/спуск) — это вообще не засчитывается как решение.

Стратегия на ДВИ

✓СОВЕТ

На экзамене

Задачи на числа редко стоят первыми. Обычно это 5-я или 6-я задача варианта. Не трать на неё время, пока не решены базовые уравнения и неравенства.
Сначала прощупай остатками (mod 3/4/8): если решений нет, это короткое и полное решение.
Если уравнение линейное — проверь критерий $НОД (a, b) ∣ c$ в одну строку, прежде чем что-то перебирать.
Если уравнение выглядит громоздким, проверь, нельзя ли собрать в нём полные квадраты: $(x + y)^{2} + (x - 2)^{2} ⩽ 0 .$ Сумма квадратов равна нулю только если каждый из них равен нулю.
Эксперты оценивают строгость. Если ты перебираешь делители, обязательно выпиши все системы, даже те, которые дают дробные корни (просто пиши напротив них «нет целых решений»).

Проверь себя0 из 4

1.Какие остатки может давать квадрат целого числа при делении на

8 ?

2.Уравнение

6 x + 9 y = 4

в целых числах:

3.Чему равен

НОД (1071, 462) ?

4.Уравнение

x^{2} + B x + C = 0

с целыми

B, C

имеет целый корень. Что верно про дискриминант

D ?