Кудреватов Г. А.

СравненияКудреватов Г. А. Сравнения // Квант. — 1972. — № 9. — С. 16⁠—⁠21.‍‍

Разделится или нет? Этот вопрос часто возникает в арифметике целых чисел. И это не случайно — ведь деление является наиболее сложным из арифметических действий.

Обозначим делимое и делитель буквами $a$‍‍ и $m$‍‍ (мы ограничимся случаем $m\gt0$‍),‍ а частное и остаток — буквами $q$‍‍ и $r$‍‍ соответственно. Тогда (см. рисунок) $a=mq+r$‍,‍ $0\le r\lt m$‍‍ (определение деления с остатком).

Если $r=0$‍,‍ то $a=mq$‍,‍ и мы говорим, что «$a$‍‍ делится на $m$‍‍» или «$a$‍‍ кратно $m$‍‍». Обозначается это с помощью троеточия: $\global\def\del{\mathrel{\raisebox{-2pt}{\(\vdots\)}}} a\del m$‍;‍ символ $\del$‍‍ означает «делится на...».

Ответить на вопрос, делится или нет, в ряде случаев помогают признаки делимости. Но в школьном курсе рассматриваются лишь простейшие из них: на 2, 3, 5 и 9. Признаки делимости, например, на 7, 11 лежат за пределами школьного курса. Знаний, получаемых на уроках арифметики, недостаточно, чтобы найти остаток от деления $2^{2^{\scriptstyle5}}+1$‍‍ на 641, $1971^{1972}$‍‍ на 7, $22^{11}-11^{22}$‍‍ на 3. На эти и многие другие вопросы даёт ответ теория сравнений, об элементах которой и рассказывается в данной статье.

1. Остаток от деления

Нередко остаток $r$‍‍ представляет больший интерес, чем частное $q$‍.‍ Например, чтобы определить $\gcd(x,6)$‍‍ при некотором $x$‍,‍ достаточно определить $\gcd(x_0,6)$‍,‍ где $x_0$‍‍ — остаток от деления $x$‍‍ на 6 ($x=6q+x_0$‍,‍ $0\le x_0\lt6$‍);‍ $\gcd(x,6)=\gcd(x_0,6)$‍.‍ Таким образом, целые числа, дающие при делении на 6 один и тот же остаток, имеют один и тот же НОД с числом 6. Это свойство целых чисел и лежит в основе алгоритма Евклида‍.

Другой пример. Наблюдая таблицу целых неотрицательных степеней числа 3, легко заметить (а заметив, и доказать) периодическое повторение последней цифры: $$ \def\a#1{\hskip1.25em\mathclap{#1}\hskip1.25em} \colsep{0pt}{\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline\\[-6pt] \a x&\hskip2pt&\a0&\a1&\a2&\a3&\hskip2pt&\a4&\a5&\a6&\a7\\[6pt]\hline\\[-6pt] 3^x&&1&3&9&27&&81&\a{243}&\a{729}&\a{2187}\\[6pt]\hline \end{array}} $$

Поэтому, чтобы определить последнюю цифру числа $3^x$‍‍ при некотором значении $x$‍,‍ достаточно определить её для числа $3^{x_0}$‍,‍ где $x_0$‍‍ — остаток от деления $x$‍‍ на 4. Например, последняя цифра числа $3^{4939}$‍‍ есть 7, так как $4939=4\cdot1234+3$‍‍ и $3^3=27$‍.‍

Для тех, кто знаком с комплексными числами (о них шла речь в статье С. Г. Гиндикина «Дебют Гаусса»‍, «Квант» №1, 1972), приведём ещё один пример: целые степени мнимого числа $i$‍‍ равны, если показатели при делении на 4 дают один и тот же остаток, поэтому достаточно знать следующую таблицу значений $i^x$‍:‍ $$ \def\a#1{\quad\mathclap{#1}\quad} \colsep{0pt}{\begin{array}{|c|c|c|c|c|c|}\hline\\[-6pt] \a x&\hskip2pt&\a0&\a1&\a2&\a3\\[6pt]\hline\\[-6pt] i^x&&1&i&-1&-i\\[6pt]\hline \end{array}} $$

Например, $i^{-2}=i^2=-1$‍,‍ $i^{11}=i^3=-i$‍.‍

Остаток однозначно определяется по делимому $a$‍‍ и делителю $m$‍,‍ поэтому в дальнейшем мы будем обозначать его символом $r(a,m)$‍.‍ Например, $r(-10,5)=0$‍,‍ $r(30,7)=2$‍,‍ $r(-30,7)=5$‍.‍

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

Рассмотренные примеры показывают, что в ряде случаев нам приходится иметь дело с фиксированным натуральным делителем $m$‍‍ или модулем (от латинского modulus — мера). В примере с $\gcd(x,6)$‍‍ модуль был равен шести, а в следующих двух примерах четырём. Мы видели, что целые числа, дающие равные остатки при делении на данный модуль, обладают некоторыми общими свойствами, например, имеют с модулем один и тот же НОД или служат показателем степени числа 3, имеющей заданную последнюю цифру. Это обстоятельство может быть широко использовано при решении различных задач теории делимости. Поэтому числа, дающие равные остатки при делении на данный модуль, получили специальное название — числа, сравнимые по данному модулю. Например, $-18$‍‍ и 14 сравнимы по модулю 4, так как $r(-18,4)=r(14,4)=2$‍,‍ но эти числа не сравнимы по модулю 5, так как $r(-18,5)=2$‍,‍ а $r(14,5)=4$‍.‍ То, что целые числа $a$‍‍ и $b$‍‍ сравнимы по модулю $m$‍,‍ принято записывать в виде сравнения: $$ \global\def\pmod#1{~(\text{mod}~#1)} a\equiv b\pmod m. $$ По определению эта запись означает, что $r(a,m)=r(b,m)$‍.‍ Так, $-18\equiv14\pmod4$‍,‍ но $-18\not\equiv14\pmod5$‍.‍

Очевидно, что каждое целое число сравнимо со своим остатком по модулю $m$‍,‍ т. е. $a\equiv r(a,m)\pmod m$‍.‍ И обратно, если $a\equiv b\pmod m$‍‍ и $0\le b\lt m$‍,‍ то $b=r(a,m)$‍.‍ Ещё заметим, что сравнение типа $a\equiv 0\pmod m$‍‍ означает, что $a\del m$‍.‍

С помощью понятия сравнения выводы в примерах из п. 1 могут быть записаны следующим образом‍:

1. $$ a\equiv b\pmod6~\Rightarrow~\gcd(a,6)=\gcd(b,6). $$

Здесь мы вместо шести можем взять произвольное натуральное число $m$‍,‍ т. е. справедливо утверждение $$ a\equiv b\pmod m~\Rightarrow~\gcd(a,n)=\gcd(b,m). $$ (Обратное утверждение неверно, вот опровергающий пример: $\gcd(1,4)=\gcd(3,4)=1$‍,‍ но $1\not\equiv3\pmod4$‍.)‍

2. $$3^{x_1}\equiv3^{x_2}\pmod{10}~\Leftrightarrow~x_1\equiv x_2\pmod4$$

(последняя цифра натурального числа является его остатком по модулю 10, поэтому числа с одной и той же последней цифрой сравнимы по модулю 10);

3. $$i^{x_1}=i^{x_2}~\Leftrightarrow~x_1\equiv x_2\pmod4.$$

Сравнимы ли числа $15\,884$‍‍ и $27\,467$‍‍ по модулю 13? На этот вопрос можно ответить с помощью определения: так как $r(15\,884,13)=r(27\,467,13)=11$‍,‍ то $15\,884\equiv27\,467\pmod{13}$‍.‍ Однако ответ можно получить и с помощью следующего критерия: $$ a\equiv b\pmod m~\Leftrightarrow~(a-b)\del m.\tag{К} $$

В данном случае $27\,467-15\,884=11\,583=13\cdot891$‍,‍ т. е. делится на 13.

Утверждение $(a-b)\del m$‍‍ эквивалентно тому, что существует целое $t$‍,‍ при котором $a=b+mt$‍.‍

Таким образом, сравнимые целые числа равны с точностью до слагаемого, кратного модулю. При этом замечательно то, что сравнения имеют не только внешнее сходство с обычными равенствами, но обладают почти всеми основными их свойствами. Так, сравнения по одному и тому же модулю можно почленно складывать, вычитать и перемножать: $$ a\equiv b{,}~c\equiv d\pmod m~\Rightarrow~a\pm c\equiv b\pm d{,}~ac\equiv bd\pmod m.\tag{С} $$ Отсюда получаются такие следствия: к частям данного сравнения можно прибавлять одно и то же число, их можно умножать на одно и то же число, а также возводить в одну и ту же натуральную степень, т. е. $$ a\equiv b\pmod m~\Rightarrow~a+c\equiv b+c{,}~ac\equiv bc{,}~a^k\equiv b^k\pmod m. $$

Упражнения

1. Докажите критерий (К) и свойства сравнений (С).
2. Докажите, что части сравнения можно сокращать на число, взаимно простое с модулем (если, конечно, обе части сравнения делятся на это число).
3. Покажите, что сравнение $3x\equiv4\pmod5$‍‍ верно при любом $x$‍,‍ сравнимом с 3 по данному модулю.
4. Проверьте, что не существует целых чисел $x$‍,‍ удовлетворяющих сравнению $3x\equiv2\pmod6$‍.‍

3. Сравнения по модулю и разбиения на классы

Свойства сравнений, данные в п. 2, позволяют сравнительно просто решать многие задачи теории делимости, нередко встречающиеся среди олимпиадных, конкурсных и т. п. Рассмотрим некоторые из них, но предварительно заметим, что при решении этих задач множество всех целых чисел полезно представлять себе разбитым на классы чисел, сравнимых по данному модулю (при этом модуль выбирается в зависимости от обстоятельств или определяется самим условием задачи).

При каждом $a$‍‍ сравнению $x\equiv a\pmod m$‍‍ удовлетворяет класс целых чисел $x$‍,‍ которые при делении на $m$‍‍ дают остаток $r(a,m)$‍.‍ Для каждого целого $x$‍‍ выполняется одно из сравнений $$ x\equiv0{,}~x\equiv1{,}~x\equiv2{,}~{\ldots}{,}~x\equiv m-2{,}~x\equiv m-1\pmod m $$ или, что то же самое, одно из равенств $$ x=mt{,}~x=1+mt{,}~x=2+mt{,}~{\ldots}{,}~x=m-2+mt{,}~x=m-1+mt, $$ где $t$‍‍ — соответствующее целое число. Итак, каждое целое число принадлежит одному из $m$‍‍ классов; не сравнимые по данному модулю числа принадлежат различным классам.

Упражнение

5. Проверьте, что отношение сравнимости является отношением эквивалентности и разбивает все числа на классы сравнимых, а именно, докажите, что

   1. $x\equiv x\pmod m$‍;‍
   2. $x\equiv y\pmod m~\Rightarrow~y\equiv x\pmod m$‍;‍
   3. $x\equiv y{,}~y\equiv z\pmod m~\Rightarrow~x\equiv z\pmod m$‍.‍

   Подробно о разбиении на классы рассказано в статье М. М. Глухова «Отношения эквивалентности и разбиения множеств»‍, «Квант» №2, 1972.

4. Некоторые задачи

Чтобы свободнее пользоваться «языком сравнений» при решении задач, рассмотрим следующие вопросы: какие классы, например, по модулю $6$‍,‍ содержат простые числа? Какому из этих классов принадлежит простое число $37$‍?‍ Какие классы по модулю $6$‍‍ содержат четвёртые степени целых чисел?

Легко видеть, что класс $x\equiv0\pmod6$‍‍ не содержит простых чисел: он состоит из чисел, кратных 6. Не входят простые числа и в класс $x\equiv4\pmod6$‍,‍ так как он состоит из чётных чисел $4+6t=2(2+3t)$‍‍ (и не содержит числа 2). Классы $x\equiv2$‍‍ и $x\equiv3\pmod6$‍‍ содержат по одному простому числу: соответственно 2 и 3. Классы $x\equiv1$‍,‍ $x\equiv5\pmod6$‍‍ содержат все остальные простые числа; например, в первый из них входят 7 и 13, а во второй 11 и 17.

Так как $37\equiv1\pmod6$‍,‍ то 37 принадлежит классу $x\equiv1\pmod6$‍.‍

Ответ на последний вопрос можно получить так: целое число по модулю 6 сравнимо с одним из остатков 0, 1, 2, 3, 4 и 5; его четвёртая степень сравнима соответственно с четвёртой степенью остатка, т. е. с одним из чисел 0, 1, 16, 81, 256 и 625. Так как $16\equiv4$‍,‍ $81\equiv3$‍,‍ $256\equiv4$‍,‍ $625\equiv1\pmod6$‍,‍ то четвёртые степени целых чисел встречаются лишь в классах $x\equiv0$‍,‍ $x\equiv1$‍,‍ $x\equiv3$‍,‍ $x\equiv4\pmod6$‍.‍

Остановимся ещё на одном вопросе. До сих пор неизвестно, конечно или бесконечно множество пар простых чисел-близнецов, т. е. простых чисел вида $$ p{,}\quad p+2. $$ Примерами «близнецов» служат 3 и 5, 5 и 7, 11 и 13. Но вот с тройками простых чисел вида $$ p{,}\quad p+2{,}\quad p+4 $$ дело обстоит значительно проще. По модулю 3 для $p$‍‍ имеем три возможности: а) $p\equiv0$‍,‍ б) $p\equiv1$‍,‍ в) $p\equiv2\pmod3$‍.‍

Первому из этих классов принадлежит единственное простое число $p=3$‍,‍ которому соответствуют простые числа $p+2=5$‍‍ и $p+4=7$‍.‍ Таким образом, первая возможность приводит к тройке $(3,5,7)$‍.‍ При $p\equiv1\pmod3$‍‍ $p+2\equiv3\equiv0\pmod3$‍,‍ откуда $p+2=3$‍,‍ $p=1$‍,‍ что противоречит условию. При $p\equiv2\pmod3$‍‍ $p+4\equiv6\equiv0\pmod3$‍,‍ откуда $p+4=3$‍‍ или $p=-1$‍,‍ что тоже не подходит. Итак, с помощью сравнений весьма просто выясняется, что существует единственная тройка «близнецов»: $(3,5,7)$‍.‍

Теперь перейдём к решению задач.

Задача 1. Найти $$ r(2^{2^{\scriptstyle5}}+1,641). $$

Решение. $2^{15}=32\,768\equiv77\pmod{641}$‍,‍ откуда $2^{30}\equiv77^2=5929\equiv160\pmod{641}$‍‍ и $2^{32}\equiv160\cdot4=640\pmod{641}$‍,‍ значит, $2^{32}+1\equiv641\equiv0\pmod{641}$‍,‍ т. е. $r(2^{2^{\scriptstyle5}}+1,641)=0$‍‍ или $(2^{2^{\scriptstyle5}}+1)\del641$‍‍‍.

Задача 2. Найти последнюю цифру натурального числа $33^{22}+22^{11}$‍.‍

Решение. Требуется найти $r(33^{22}+22^{11},10)$‍.‍

Так как $33\equiv3\pmod{10}$‍,‍ то $33^2\equiv9\equiv-1\pmod{10}$‍‍ и $33^{22}\equiv(-1)^{11}\equiv-1\pmod{10}$‍.‍ Из $22\equiv2\pmod{10}$‍‍ следует $22^5\equiv32\equiv2\pmod{10}$‍,‍ $22^{10}\equiv4\pmod{10}$‍‍ и $22^{11}\equiv4\cdot22\equiv8\pmod{10}$‍.‍ Складывая почленно полученные сравнения, имеем $$ 33^{22}+22^{11}\equiv7\pmod{10}. $$ Таким образом, данное число оканчивается цифрой 7.

Задача 3. Доказать, что не существует натуральных чисел $x$‍,‍ $y$‍‍ и $z$‍,‍ удовлетворяющих уравнению $$ 2^x+7^y=19^z. $$

Решение. Используем модуль 3. В силу $19\equiv1\pmod3$‍‍ имеем $19^z\equiv1\pmod3$‍.‍ С другой стороны, $2^x+7^y\equiv(-1)^x+1\pmod3$‍,‍ откуда $2^x+7^y\equiv2\pmod3$‍‍ или $2^x+7^y\equiv0\pmod3$‍‍ (в зависимости от чётности $x$‍).‍ Так как $2^x+7^y\not\equiv19^z\pmod3$‍,‍ то $2^x+7^y\ne19^z$‍.‍

Подчеркнём, что при решении этой задачи мы догадались, что надо использовать модуль 3. Если бы мы взяли модуль 4, то у нас противоречия не получилось бы. Вопрос о выборе подходящего модуля при решении задачи сложен. Если он вас интересует — посмотрите статью М. И. Башмакова «Нравится ли вам возиться с целыми числами»‍, «Квант», №3, 1971.

Задача 4. Доказать, что число $p^3+2$‍‍ — простое, если простыми являются числа $p$‍‍ и $p+2$‍.‍

Решение. Если $p\equiv0\pmod3$‍,‍ то $p=3$‍‍ и $p^2+2=11$‍,‍ $p^3+2=29$‍.‍

Если $p\equiv1\mod3$‍,‍ то $p^2\equiv1$‍‍ и $p^2+2\equiv3\equiv0\pmod3$‍,‍ откуда $p^2+2=3$‍,‍ но такому соотношению ни одно простое число не удовлетворяет. К противоречию приводит и вариант $p\equiv2\pmod3$‍.‍ Таким образом, числа $p$‍‍ и $p^2+2$‍‍ являются простыми только при $p=3$‍.‍ В этом случае и число $p^3+2$‍‍ простое.

Задача 5. Доказать, что не существует квадратного уравнения $$ ax^2+bx+c=0 $$ с целыми коэффициентами и дискриминантом 215.

Решение. Если $b^2-4ac=215$‍,‍ то $(b^2-215)\del4$‍‍ или $b^2\equiv215\equiv3\pmod4$‍.‍ Но это невозможно, так как $r(b^2,4)$‍‍ может быть равен только 0 или 1 (докажите!).

Замечание. Из решения ясно, что все целые числа, сравнимые с 2 или 3 по модулю 4, не могут быть дискриминантом квадратного уравнения с целыми коэффициентами.

Задача 6. Доказать, что по крайней мере одна из сторон пифагорова треугольника (прямоугольного треугольника, стороны которого выражаются натуральными числами) делится на 5.

Решение. Пусть $x$‍,‍ $y$‍,‍ $z$‍‍ — натуральные числа, причём $x^2+y^2=z^2$‍.‍ Допустим, что ни одно из них не сравнимо с нулём по модулю 5. Тогда квадрат каждого из них сравним с 1 или 4 (докажите!). Имеем три возможности:

1. $x^2\equiv y^2\equiv1\pmod5$‍;‍
2. $x^2\equiv1$‍,‍ $y^2\equiv4\pmod5$‍‍ или $x^2\equiv4$‍,‍ $y^2\equiv1\pmod5$‍;‍
3. $x^2\equiv y^2\equiv4\pmod5$‍.‍

Тогда соответственно:

1. $z^2=x^2+y^2\equiv2\pmod5$‍;‍
2. $z^2=x^2+y^2\equiv0\pmod5$‍;‍
3. $z^2=x^2+y^2\equiv8\equiv3\pmod5$‍.‍

Случаи а) и в) невозможны ($z^2$‍‍ должно быть сравнимо с 1 или 4). Значит, хотя бы одно из чисел $x$‍,‍ $y$‍,‍ $z$‍‍ сравнимо с нулём по модулю 5, т. е. делится на 5.

Упражнения

6. Найдите:

   1. $r(1971^{1972},7)$‍;‍
   2. $r(22^{11}+11^{22},3)$‍.‍
7. Докажите, что по крайней мере один из катетов пифагорова треугольника делится на 3.
8. Найдите натуральные числа $n$‍‍ такие, что $n^2+5$‍‍ кратно 7.
9. Докажите, что нет на плоскости целых точек (точек, обе координаты которых выражаются целыми числами), принадлежащих параболе $$ y=\dfrac15x^2-\dfrac35. $$
10. Докажите, что число 287 нельзя представить в виде суммы двух квадратов целых чисел.
11. Найдите такое простое число $p$‍,‍ чтобы числа $4p^2+1$‍‍ и $6p^2+1$‍‍ оба были простыми.
12. Докажите, что не существует прямоугольного параллелепипеда с целочисленными рёбрами и диагональю $\sqrt{807}$‍.‍

5. Признаки делимости и проверка действий

Сравнения могут служить для установления различных признаков делимости. Например, признак делимости на 11 можно вывести с помощью очевидного сравнения $10\equiv-1\pmod{11}$‍.‍ Заметим, что $10^1\equiv-1$‍,‍ $10^2\equiv1$‍,‍ $10^3\equiv-1$‍,‍ $10^4\equiv1$‍,‍ $10^5\equiv-1$‍,‍ $10^6\equiv1$‍,‍ $10^7\equiv-1$‍,‍ ${\ldots}\pmod{11}$‍.‍ Записав число $n$‍‍ в виде $$ n=\overline{a_ka_{k-1}\ldots a_2a_1a_0}=a_k10^k+a_{k-1}10^{k-1}+\ldots+a_210^2+a_110+a_0 $$ и воспользовавшись свойствами сравнений, получим сравнение $$ n\equiv(a_0+a_2+{\ldots})-(a_1+a_3+{\ldots})\pmod{11}, $$ т. е. каждое число сравнимо по модулю 11 с разностью между суммой его цифр, стоящих на нечётных местах (справа налево), и суммой остальных цифр.

Остаётся сформулировать признак делимости: число делится на 11 тогда и только тогда, когда на 11 делится упомянутая разность. Например, $1\,493\,745\del11$‍,‍ так как $(5+7+9+1)-(4+3+4)=11$‍.‍

Рассмотрим ещё признак делимости на 7. Исходя из сравнения $1000\equiv-1\pmod7$‍,‍ для любого $n=\overline{a_ka_{k-1}\ldots a_2a_1a_0}$‍‍ легко получить сравнение $$ n\equiv(\overline{a_2a_1a_0}+\overline{a_8a_7a_6}+{\ldots})-(\overline{a_5a_4a_3}+\overline{a_{11}a_{10}a_9}+{\ldots})\pmod7 $$ выражающее признак делимости на 7. Сформулируйте этот признак самостоятельно.

При выполнении «арифметических действий полезно проверять правильность результатов. Один из способов проверки действий сложения, вычитания и умножения — «способ девятки» — легко получить с помощью сравнений. По модулю 9 каждое натуральное число $n$‍‍ сравнимо с суммой $S(n)$‍‍ своих цифр: $$ n\equiv S(b)\pmod9 $$ (докажите этот факт самостоятельно). Значит, если $n_1+n_2+\ldots+n_k=n$‍‍ или $n_1n_2\ldots n_k=n$‍,‍ то соответственно $S(n_1)+S(n_2)+\ldots+S(n_k)=S(n)\pmod9$‍‍ и $S(n_1)\,S(n_2)\ldots S(n_k)\equiv S(n)\pmod9$‍.‍ Например, верной записи $121\,232\cdot212\,323=25\,740\,341\,936$‍‍ отвечает соотношение $$ \begin{gather*} (1+2+1+2+3+2)\cdot(2+1+2+3+2+3)-{}\qquad\\\qquad{}-(2+5+7+4+3+4+1+9+3+6)=11\cdot13-44=99. \end{gather*} $$

Найденное условие может выполняться и при ошибке в результате действия (когда ошибка кратна 9), но если выведенное нами условие не выполняется, то результат действия заведомо ошибочен. Для действия деления, например, чтобы обнаружить ошибочность записи $95\,425:775=123$‍,‍ достаточно её представить в виде $95\,495=775\,123$‍‍ и заметить, что $$ (9+5+4+2+5)-(7+7+5)\cdot(1+2+3)=25-114=-89 $$ не делится на 9.

Ещё пример. Запись $\!\sqrt[\scriptstyle5~]{371293}=23$‍‍ ошибочна, так как $S(371\,293)=25$‍,‍ $S(23)=5$‍‍ и $5^5-25=3100\not\equiv0\pmod9$‍,‍ а это значит, что $23^5\ne371\,293$‍,‍ откуда $\!\sqrt[\scriptstyle5~]{371\,293}\ne23$‍.‍

Упражнения

13. Дан многочлен $ax^n+bx^{n-1}+\ldots+fx+d$‍‍ с целыми коэффициентами. Докажите, что сравнимым значениям аргумента $x$‍‍ отвечают сравнимые значения этого многочлена (по одному и тому же модулю).
14. Попробуйте вывести признак делимости на 101.
15. Установите ещё один признак делимости на 11, исходя из сравнения $$ 100\equiv1\pmod{11}. $$
16. Докажите, что $\!\sqrt[\scriptstyle3~]{19\,783}\ne27$‍.‍

17. Делятся ли на 7 числа

    1. $123\,456\,789$‍;‍
    2. $987\,654\,321$‍?‍

В заключение укажем, что с методом сравнений более подробно можно познакомиться по книгам:

1. И. М. Виноградов. Основы теории чисел. — М.: Наука. 1965.
2. Г. Н. Берман. Число и наука о нём. — М.: Физматгиз, 1960.
3. Г. Дэвенпорт. Высшая арифметика. — М.: Наука, 1965.
4. Ш. Х. Михелевич. Теория чисел. — М.: Высшая школа, 1967.