Числа и делимость

Алгоритм Евклида

Делим с остатком, заменяем пару $(a,b)\to(b,\,a\bmod b)$:

Последний ненулевой остаток — $21$, значит $\text{НОД}(1071,462)=21$.

Проверка разложением

$1071 = 3\cdot 357 = 3\cdot 3\cdot 119 = 3^2\cdot 7\cdot 17$, а $462 = 2\cdot 3\cdot 7\cdot 11$. Общие простые с минимальными степенями: $3^1$ и $7^1$, поэтому $\text{НОД}=3\cdot 7 = 21$. Совпало.

Находим НОК

Теперь НОК по формуле связи:

Проверяем разрешимость

$d=\text{НОД}(15,21)=3$. Так как $3\mid 6$, решения есть. Сократим всё уравнение на $3$:

Теперь $\text{НОД}(5,7)=1$.

Частное решение алгоритмом Евклида

Обратный ход для $5x+7y=1$:

Значит $5\cdot 3 + 7\cdot(-2)=1$. Умножим на $2$ (правая часть нашего уравнения):

Общее решение

Здесь $d=1$ (после сокращения), $a=5$, $b=7$:

Проверка

При $t=-1$: $x=-1$, $y=1$, и $15\cdot(-1)+21\cdot 1 = -15+21 = 6$. Верно.

Раскладываем однородную часть

Попытаемся разложить на множители однородную часть $2x^2 + xy - y^2$:

Подбираем константы в скобках

Теперь нужно подобрать такие числа $A$ и $B$, чтобы произведение скобок $(2x-y+A)(x+y+B)$ дало линейную часть $-3x+3y$ и какую-то константу:

Приравниваем коэффициенты при $x$ и $y$:

Сводим к произведению с целой правой частью

Значит, $(2x-y+1)(x+y-2) = 2x^2 + xy - y^2 - 3x + 3y - 2$. Вычтем из обеих частей исходного уравнения двойку, чтобы слева получить ровно это произведение:

Полный перебор систем

Так как $x, y \in \ZZ$, множители в скобках тоже целые. Число 4 раскладывается в произведение двух целых чисел шестью способами. Выпишем все системы и для каждой найдём $x,y$. Удобно сложить уравнения: из $u = 2x-y+1$ и $v = x+y-2$ получаем $u+v = 3x-1$, то есть $x = \dfrac{u+v+1}{3}$, а $y = v - x + 2$. Целое $x$ возможно лишь когда $u+v+1$ делится на $3$.

Три системы с дробным $x$ явно отбрасываем (а не молча пропускаем) — именно за этот шаг под рубрику ДВИ начисляют полноту решения. Остаются три пары.

Записываем как квадратное относительно $x$

Рассмотрим уравнение как квадратное относительно $x$ (старший коэффициент при $x^2$ равен $1$ — уравнение приведённое, это важно для следующего шага):

Вычисляем дискриминант

Вычислим четверть дискриминанта (коэффициент при $x$ чётный):

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

Чтобы уравнение имело действительные корни, необходимо $\dfrac{D}{4} \geqslant 0$:

Корни уравнения $y^2 - 2y - 1 = 0$ равны $y = 1 \pm \sqrt{2}$. Следовательно, решение неравенства:

Проверяем точные квадраты

Так как $y \in \ZZ$, возможны только три значения: $y = 0$, $y = 1$, $y = 2$. Проверим каждое (так как уравнение приведённое, целому $x$ соответствует ровно точный квадрат $D/4$):

1. При $y = 0$: $\dfrac{D}{4} = 2$. Число $2$ не является точным квадратом — целых решений нет.
2. При $y = 1$: $\dfrac{D}{4} = -2(1) + 4(1) + 2 = 4 = 2^2$. Точный квадрат! Тогда $x = (y+1) \pm \sqrt{4} = 2 \pm 2$. Отсюда $x = 4$ или $x = 0$.
3. При $y = 2$: $\dfrac{D}{4} = -2(4) + 4(2) + 2 = 2$. Не точный квадрат — целых решений нет.

Остатки правой части по модулю 3

Перепишем уравнение в виде $x^2 = 3y^2 + 17$. Рассмотрим остатки обеих частей при делении на 3: Правая часть: $3y^2$ делится на 3 нацело (остаток 0). Число 17 при делении на 3 даёт остаток 2 ($17 = 3 \cdot 5 + 2$). Значит, вся правая часть при делении на 3 даёт остаток 2.

Остатки левой части

Левая часть: $x^2$. Переберём все возможные остатки целого числа $x$ при делении на 3:

• Если $x \equiv 0 \pmod 3$, то $x^2 \equiv 0 \pmod 3$.
• Если $x \equiv 1 \pmod 3$, то $x^2 \equiv 1 \pmod 3$.
• Если $x \equiv 2 \pmod 3$, то $x^2 \equiv 4 \equiv 1 \pmod 3$.

Получаем противоречие

Квадрат целого числа при делении на 3 может давать только остатки 0 или 1. А правая часть требует, чтобы остаток был равен 2. Возникает противоречие.

Проверяем разрешимость

Здесь полезно сочетать делимость и оценку. $\text{НОД}(3,5)=1$ делит $47$, решения в целых есть. Но требуются именно натуральные $x,y$, поэтому удобнее не выписывать общую серию, а ограничить перебор.

Условие делимости

Выразим $x = \dfrac{47 - 5y}{3}$. Чтобы $x$ был целым, нужно $47 - 5y \equiv 0 \pmod 3$. Так как $47 \equiv 2$ и $5\equiv 2 \pmod 3$, условие даёт $2 - 2y \equiv 0$, то есть $2y \equiv 2$, $y \equiv 1 \pmod 3$. Значит $y \in \{1, 4, 7, 10, \dots\}$.

Оценка сверху и перебор

Теперь оценка сверху: для $x \geqslant 1$ нужно $5y \leqslant 44$, то есть $y \leqslant 8{,}8$. С учётом $y\geqslant 1$ остаётся $y \in \{1,4,7\}$:

• $y=1$: $x = (47-5)/3 = 14$. Пара $(14,1)$.
• $y=4$: $x = (47-20)/3 = 9$. Пара $(9,4)$.
• $y=7$: $x = (47-35)/3 = 4$. Пара $(4,7)$.

Все три пары — натуральные.

Остатки квадратов по модулю 8

Это ровно тот сюжет, где работает модуль $8$ (в исходном конспекте он вводился, но не использовался). По таблице остатков квадрат целого числа при делении на $8$ даёт только остатки из множества $\{0,\,1,\,4\}$.

Перебираем суммы остатков

Переберём все суммы двух таких остатков (по модулю $8$):

Итого сумма двух квадратов по модулю $8$ может давать только остатки из множества $\{0,1,2,4,5\}$. Остатка $7$ среди них нет.

Получаем противоречие

Но число $8k+7$ имеет остаток ровно $7$ при делении на $8$. Противоречие: оно не может быть суммой двух квадратов.

Идея спуска

Метод бесконечного спуска (нисхождения): предполагаем существование ненулевого решения и строим из него «меньшее», что невозможно для натуральных чисел.

Анализ остатков по модулю 3

Пусть $(x,y,z)$ — решение с наименьшим возможным $|z|>0$. Рассмотрим остатки по модулю $3$. Квадраты дают $0$ или $1 \pmod 3$, а правая часть $3z^2 \equiv 0 \pmod 3$. Сумма $x^2+y^2\equiv 0 \pmod 3$ возможна только если оба слагаемых $\equiv 0$, то есть $3\mid x$ и $3\mid y$ (иначе сумма была бы $1$ или $2$).

Строим меньшее решение

Запишем $x = 3x_1$, $y = 3y_1$. Подставляя:

Значит $z = 3z_1$, и после подстановки $9(x_1^2+y_1^2) = 9 z_1^2$, то есть

Противоречие с минимальностью

Получили решение того же вида, но с $|z_1| = |z|/3 < |z|$ — противоречие с минимальностью $|z|$.

Следовательно, ненулевых решений нет.

Период остатков по модулю 10

Последняя цифра — это остаток по модулю $10$. Выпишем степени семёрки по модулю $10$:

Остатки повторяются с периодом 4: $(7,9,3,1)$.

Находим остаток показателя

Найдём остаток показателя по модулю $4$: $2026 = 4\cdot 506 + 2$, то есть $2026 \equiv 2 \pmod 4$. Значит $7^{2026}$ имеет ту же последнюю цифру, что и $7^2$, — это $9$.