Глава
Теория
Сравнения позволяют заменить бесконечно много целых чисел конечной таблицей остатков. Чтобы доказать невозможность, часто достаточно найти модуль, в котором левая и правая части всегда попадают в разные наборы остатков.
В этом модуле главное - не вычислять механически, а выбирать модуль: \(3,4,5,7,8,9,11,16\) часто дают быстрые противоречия.
Если справа стоит число вида \(4k+3\), \(8k+7\), \(3k+2\), попробуйте таблицы квадратов. Если есть кубы, проверьте модуль \(7\) или \(9\). Если речь о последней цифре, ищите цикл степеней.
Правильный модуль обычно маленький и делает одну сторону очень ограниченной: например, квадрат по модулю \(8\) не может дать \(2,3,5,6,7\).
Примеры
Сравнение фиксирует остаток, но позволяет работать с числами без деления нацело.
Задача. Найдите остаток \(2026^2+2026\) при делении на \(5\).
\(2026\equiv1\pmod5\). Тогда \(2026^2+2026\equiv1^2+1=2\pmod5\). Остаток равен \(2\).
Комментарий. Сначала заменяем число его остатком, затем считаем.
Квадраты имеют очень мало остатков.
Задача. Покажите, что квадрат целого числа по модулю \(8\) может иметь только остаток \(0,1,4\).
Проверим остатки \(0,1,2,\ldots,7\). Их квадраты по модулю \(8\): \(0,1,4,1,0,1,4,1\). Значит, возможны только \(0,1,4\).
Комментарий. Эта таблица будет использоваться много раз.
Сумма двух квадратов не может иметь остаток \(3\) по модулю \(4\).
Задача. Докажите, что \(x^2+y^2=4z+3\) не имеет целочисленных решений.
Квадрат по модулю \(4\) равен \(0\) или \(1\). Поэтому сумма двух квадратов по модулю \(4\) может быть \(0,1,2\), но не \(3\). Правая часть \(4z+3\equiv3\pmod4\). Противоречие.
Комментарий. Модуль \(4\) выбран из вида правой части.
Модуль \(8\) сильнее обычной четности.
Задача. Докажите, что \(x^2+y^2=8z+7\) не имеет целочисленных решений.
Квадраты по модулю \(8\) дают \(0,1,4\). Сумма двух таких остатков может быть \(0,1,2,4,5\), но не \(7\). Правая часть равна \(7\) по модулю \(8\). Противоречие.
Комментарий. Здесь модуль \(4\) был бы слабее, а модуль \(8\) решает задачу.
Иногда проще проверить все остатки по небольшому модулю.
Задача. Найдите все остатки \(n\pmod7\), при которых \(7\mid n^2+n+1\).
Проверяем \(n=0,1,2,3,4,5,6\). Значения \(n^2+n+1\) по модулю \(7\): \(1,3,0,6,0,3,1\). Поэтому подходят \(n\equiv2\) и \(n\equiv4\pmod7\).
Комментарий. Таблица из семи строк вполне допустима, если она дает полный ответ.
Кубы по модулю \(9\) дают только три остатка.
Задача. Покажите, что куб целого числа по модулю \(9\) равен \(0,1\) или \(8\).
Проверим остатки \(0,\ldots,8\): кубы дают \(0,1,8,0,1,8,0,1,8\). Значит, возможны только \(0,1,8\), то есть \(0,\pm1\).
Комментарий. Эта таблица полезна для задач о суммах кубов.
Последняя цифра - это работа по модулю \(10\).
Задача. Найдите последнюю цифру \(7^{2026}\).
Последние цифры степеней \(7\) идут циклом: \(7,9,3,1\). Длина цикла \(4\). Так как \(2026\equiv2\pmod4\), берем вторую цифру цикла: \(9\).
Комментарий. Не надо вычислять большую степень.
Иногда модуль виден по коэффициенту перед переменной.
Задача. Докажите, что уравнение \(x^2=3y^2+2\) не имеет целочисленных решений.
Рассмотрим уравнение по модулю \(3\). Правая часть \(3y^2+2\equiv2\pmod3\). Но квадрат по модулю \(3\) может быть только \(0\) или \(1\). Противоречие.
Комментарий. Модуль \(3\) выбран потому, что правая часть почти кратна \(3\).
Задачи
Найдите остаток числа \(2026\) при делении на \(7\).
Вычтите ближайшее кратное \(7\).
\(7\cdot289=2023\), поэтому \(2026=7\cdot289+3\). Остаток равен \(3\).
Докажите, что квадрат целого числа по модулю \(4\) может иметь только остаток \(0\) или \(1\).
Проверьте четное и нечетное число.
Если \(n=2k\), то \(n^2=4k^2\equiv0\pmod4\). Если \(n=2k+1\), то \(n^2=4k^2+4k+1\equiv1\pmod4\).
Составьте таблицу квадратов по модулю \(8\).
Достаточно проверить остатки \(0,1,\ldots,7\).
Квадраты остатков \(0,1,2,3,4,5,6,7\) по модулю \(8\) равны \(0,1,4,1,0,1,4,1\). Значит, возможны только \(0,1,4\).
Найдите последнюю цифру числа \(3^{2025}\).
Посмотрите цикл последних цифр степеней \(3\).
Последние цифры степеней \(3\): \(3,9,7,1\), цикл длины \(4\). Так как \(2025\equiv1\pmod4\), последняя цифра равна \(3\).
Найдите все остатки \(n\pmod5\), для которых \(n^2\equiv1\pmod5\).
Проверьте остатки \(0,1,2,3,4\).
Квадраты по модулю \(5\): \(0^2\equiv0\), \(1^2\equiv1\), \(2^2\equiv4\), \(3^2\equiv4\), \(4^2\equiv1\). Подходят \(n\equiv1\) и \(n\equiv4\pmod5\).
Докажите, что уравнение \(x^2+y^2=4z+3\) не имеет решений в целых числах.
Рассмотрите уравнение по модулю \(4\).
Квадрат по модулю \(4\) равен \(0\) или \(1\). Поэтому \(x^2+y^2\) может иметь остаток \(0,1,2\), но не \(3\). Правая часть имеет остаток \(3\). Противоречие.
Докажите, что уравнение \(x^2+y^2=8z+7\) не имеет решений в целых числах.
Используйте квадраты по модулю \(8\).
Квадраты по модулю \(8\): \(0,1,4\). Сумма двух таких остатков может быть \(0,1,2,4,5\), но не \(7\). Правая часть дает остаток \(7\). Противоречие.
Найдите все целые \(n\), для которых \(7\mid n^2+n+1\).
Проверьте \(n=0,1,\ldots,6\) по модулю \(7\).
Таблица значений \(n^2+n+1\) по модулю \(7\) для \(n=0,1,2,3,4,5,6\): \(1,3,0,6,0,3,1\). Поэтому \(n\equiv2\) или \(n\equiv4\pmod7\).
Докажите, что ни один квадрат целого числа не имеет остаток \(2\) или \(3\) при делении на \(4\).
Используйте таблицу квадратов по модулю \(4\).
Любой квадрат по модулю \(4\) равен \(0\) или \(1\). Остатки \(2\) и \(3\) не появляются, значит, квадрат не может иметь такие остатки.
Найдите последнюю цифру числа \(7^{2026}\).
Цикл последних цифр степеней \(7\) имеет длину \(4\).
Цикл: \(7,9,3,1\). Так как \(2026\equiv2\pmod4\), берем вторую цифру цикла. Ответ: \(9\).
Докажите с помощью сравнений, что \(n^2+n\) четно для любого целого \(n\).
Проверьте остатки \(n\) по модулю \(2\).
Если \(n\equiv0\pmod2\), то \(n^2+n\equiv0\). Если \(n\equiv1\pmod2\), то \(n^2+n\equiv1+1\equiv0\pmod2\). Значит, выражение всегда четно.
Докажите, что сумма трех кубов целых чисел не может иметь остаток \(4\) или \(5\) при делении на \(9\).
Куб по модулю \(9\) равен \(0\), \(1\) или \(-1\).
Каждый куб по модулю \(9\) равен \(0,\pm1\). Сумма трех таких остатков лежит среди \(-3,-2,-1,0,1,2,3\), то есть по модулю \(9\) среди \(6,7,8,0,1,2,3\). Остатков \(4\) и \(5\) нет.
Докажите, что число вида \(8t+7\) нельзя представить в виде суммы трех квадратов целых чисел.
Квадраты по модулю \(8\): \(0,1,4\). Проверьте суммы трех таких остатков.
Квадрат по модулю \(8\) равен \(0,1\) или \(4\). Сумма трех таких остатков может дать \(0,1,2,3,4,5,6\), но не \(7\). Поэтому сумма трех квадратов не может быть сравнима с \(7\) по модулю \(8\). Число \(8t+7\) как раз имеет остаток \(7\). Противоречие.
Докажите, что уравнение \(x^2=3y^2+2\) не имеет решений в целых числах.
Рассмотрите уравнение по модулю \(3\).
Правая часть \(3y^2+2\equiv2\pmod3\). Но квадрат по модулю \(3\) равен только \(0\) или \(1\). Значит, левая часть не может иметь остаток \(2\). Противоречие.
Докажите: если \(3\mid x^2+y^2\), то \(3\mid x\) и \(3\mid y\).
Квадраты по модулю \(3\) равны \(0\) или \(1\).
Если число не делится на \(3\), его квадрат имеет остаток \(1\) по модулю \(3\). Если хотя бы одно из \(x,y\) не делится на \(3\), сумма квадратов имеет остаток \(1\) или \(2\), но не \(0\), кроме случая когда оба квадрата дают \(0\). Поэтому \(x\) и \(y\) оба делятся на \(3\).
Найдите все целые \(n\), для которых \(13\mid n^2+n+1\).
Проверьте остатки \(0,1,\ldots,12\) или используйте симметрию \(n\) и \(-1-n\).
Проверка остатков по модулю \(13\) дает нули только при \(n\equiv3\) и \(n\equiv9\). Действительно, \(3^2+3+1=13\), \(9^2+9+1=91=7\cdot13\). Другие остатки дают ненулевые значения. Ответ: \(n\equiv3\) или \(9\pmod{13}\).
Докажите, что \(n^2+n+1\) не делится на \(11\) ни при каком целом \(n\).
Проверьте все остатки \(n\pmod{11}\).
Для \(n=0,1,\ldots,10\) значения \(n^2+n+1\) по модулю \(11\) равны \(1,3,7,2,10,9,10,2,7,3,1\). Нуля среди них нет, значит, делимость на \(11\) невозможна.
Докажите, что уравнение \(x^4+y^4=16z+15\) не имеет решений в целых числах.
Четвертая степень по модулю \(16\) равна \(0\) или \(1\).
Если \(x\) четно, то \(x^4\equiv0\pmod{16}\); если \(x\) нечетно, то \(x^2\equiv1\) или \(9\pmod{16}\), а \(x^4\equiv1\pmod{16}\). Значит, \(x^4+y^4\) может иметь остаток \(0,1,2\), но не \(15\). Правая часть имеет остаток \(15\). Противоречие.
Докажите, что сравнение \(x^3\equiv2\pmod7\) не имеет решений.
Составьте таблицу кубов по модулю \(7\).
Для остатков \(0,1,2,3,4,5,6\) кубы по модулю \(7\) равны \(0,1,1,6,1,6,6\). Возможны только \(0,1,6\). Остатка \(2\) нет, значит, решений нет.
Найдите последние две цифры числа \(3^{20}\).
Работайте по модулю \(100\). Заметьте, что \(3^4=81\).
\(3^{20}=(3^4)^5=81^5\). По модулю \(100\): \(81^2\equiv61\), \(81^4\equiv61^2\equiv21\), \(81^5\equiv21\cdot81\equiv1\). Значит, последние две цифры: \(01\).
Докажите, что единственное целочисленное решение уравнения \(x^2+y^2=3z^2\) - это \(x=y=z=0\).
Сначала докажите, что из делимости \(x^2+y^2\) на \(3\) следует \(3\mid x\) и \(3\mid y\).
Из уравнения следует \(3\mid x^2+y^2\). По таблице квадратов modulo \(3\) получаем \(3\mid x\) и \(3\mid y\). Пусть \(x=3x_1\), \(y=3y_1\). Тогда \(9x_1^2+9y_1^2=3z^2\), значит, \(z^2=3(x_1^2+y_1^2)\), и \(3\mid z\). Получаем, что все \(x,y,z\) делятся на \(3\). Если есть ненулевое решение, можно делить все три числа на \(3\) бесконечно, что невозможно для ненулевых целых чисел. Значит, ненулевых решений нет.
Докажите, что уравнение \(x^2-5y^2=2\) не имеет решений в целых числах.
Рассмотрите уравнение по модулю \(5\).
По модулю \(5\) получаем \(x^2\equiv2\pmod5\). Но квадраты по модулю \(5\) равны только \(0,1,4\). Остаток \(2\) невозможен. Значит, решений нет.
Докажите: если \(7\mid x^2+y^2\), то \(7\mid x\) и \(7\mid y\).
Квадраты по модулю \(7\): \(0,1,2,4\).
Квадратичные остатки по модулю \(7\): \(0,1,2,4\). Чтобы сумма двух таких остатков была \(0\), возможен только вариант \(0+0\): числа \(1,2,4\) имеют противоположные остатки \(6,5,3\), которые квадратами не являются. Значит, \(x^2\equiv0\) и \(y^2\equiv0\pmod7\), откуда \(7\mid x\) и \(7\mid y\).
Докажите, что существует бесконечно много натуральных чисел, которые нельзя представить в виде суммы трех квадратов целых чисел.
Рассмотрите числа вида \(8t+7\).
Из задачи о трех квадратах по модулю \(8\) следует: сумма трех квадратов не может иметь остаток \(7\) по модулю \(8\). Поэтому ни одно число вида \(8t+7\) не представляется в виде \(x^2+y^2+z^2\). Таких натуральных чисел бесконечно много: \(7,15,23,31,\ldots\). Следовательно, требуемых чисел бесконечно много.
Лестницы