Сравнения и признаки делимости | Математика, которая мне нравится

9. Сравнения и признаки делимости

Определение. Пусть и – целые числа, – натуральное. Говорят, что число сравнимо с по
модулю , если $a-b\vdots m$ .

Обозначение. $a\equiv b\pmod{m}$ .

Пример.
$\begin{array}{l} 45\equiv75\pmod{10}\\ 182\equiv-4\pmod{6} \end{array}$

Теорема. $a\equiv b\pmod{m}$ тогда и только тогда, когда и дают при делении на равные остатки.

Доказательство. Разделим и на с остатками
$\begin{array}{l} a=mq_1+r_1,\quad 0\le r_1<m,\\ b=mq_2+r_2,\quad 0\le r_2<m,\\ a-b=m(q_1-q_2)+(r_1-r_2). \end{array}$

Тогда
$a-m\vdots m,m(q_1-q_2)\vdots m\Longrightarrow (r_1-r_2)\vdots m\Longrightarrow r_1-r_2=0\Longrightarrow r_1=r_2.$

Следовательно,
$r_1=r_2\Longrightarrow a-b=m(q_1-q_2)\Longrightarrow a-b\vdots m.$

Свойства сравнений

1. $a\equiv a\pmod{m}$ (рефлексивность),

2. $a\equiv b\pmod{m}\Longrightarrow b\equiv a\pmod{m}$ (симметричность),

3. $a\equiv b\pmod{m},b\equiv c\pmod{m}\Longrightarrow a\equiv c\pmod m$ (транзитивность),

4. $a\equiv b\pmod{m},c\equiv d\pmod{m}\Longrightarrow a\stackrel{+}{\stackrel{-}{\cdot}}b\equiv c\stackrel{+}{\stackrel{-}{\cdot}}d\pmod{m}$ .

5. $ac\equiv bc\pmod{m}$ , НОД $(c,m)=1\Longrightarrow a\equiv b\pmod{m}$ .

Доказательство.

1. $a-a=0\vdots m\Longrightarrow a\equiv a\pmod{m}$

2.
$\begin{array}{l} a\equiv b\pmod{m}\Longrightarrow(a-b)\vdots m\\ a-b=-(b-a)\Longrightarrow -(b-a)\vdots m\Longrightarrow b\equiv a\pmod{m}. \end{array}$

3.
$\begin{array}{l}\left.\begin{array}{l} a\equiv b\pmod{m}\Longrightarrow a-b\vdots m\\ b\equiv c\pmod{m}\Longrightarrow b-c\vdots m \end{array}\right|\Longrightarrow \\[4mm] \Longrightarrow a-b+(b-c)\vdots m\Longrightarrow a-c\vdots m\Longrightarrow a\equiv c\pmod{m} \end{array}$

4.
$\begin{array}{l} a\equiv b\pmod{m}\Longrightarrow a-b\vdots m,\\ c\equiv d\pmod{m}\Longrightarrow c-d\vdots m, \end{array}$
$\begin{array}{ll} a-b=km,&c-d=lm,\\ a=km+b,&b=a-km,\\ c=lm+d,&d=c-lm, \end{array}$
$\begin{array}{l} a+b=2a-km,\\ c+d=2d-lm,\\ a+c=m(k+l)+(b+d)\equiv b+d\pmod{m},\\ ac=(klm^2+blm+dkm)+bd\equiv bd\pmod{m},\\ a-c=(k-l)m+(b-d)\equiv b-d\pmod{m}. \end{array}$

5.
$\left.\begin{array}{l} ac-bc\vdots m,\\ c(a-b)\vdots m,\\ {\rm GCD}(c,m)=1, \end{array}\right|\Longrightarrow(a-b)\vdots m\Longrightarrow a\equiv b\pmod{m}. $

Признаки делимости

Пусть – натуральное число, $a=(\overline{a_0a_1\ldots a_n})_{10}$ ,
$a=a_0\cdot10^n+a_1\cdot10^{n-1}+a_2\cdot10^{n-2}+\dots+a_n$

1. Признаки делимости на 3 и 9

Так как $10\equiv1\pmod{3,9}$ , то $10^k\equiv1\pmod{3,9}$
$\Longrightarrow a\equiv a_0+a_1+a_2+\dots+a_n\pmod{3,9}.$

Натуральное число сравнимо с суммой своих цифр по модулю 3 и по модулю 9.

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

$k\ge1\Longrightarrow10^k\equiv0\pmod{2,5}$ $\Longrightarrow a\equiv a_n\pmod{2,5}$

Натуральное число сравнимо со своей последней цифрой по модулю 2 и по модулю 5.

3. Признаки делимости на 4 и на 25

$k\ge2\Longrightarrow 10^k\equiv0\pmod{4,25}$ $\Longrightarrow a\equiv a_{n-1}\cdot10+a_n\pmod{4,25}$

Натуральное число сравнимо по модулю 4 и по модулю 25 с числом, образованным его двумя последними цифрами.

4. Признак делимости на 11

$10\equiv-1\pmod{11}$
$10^k\equiv1\pmod{11}$ , если — четное,
$10^k\equiv-1\pmod{11}$ , если — нечетное.
$a\equiv a_n-a_{n-1}+a_{n-2}-a_{n-3}+\ldots\pmod{11}$

Натуральное число сравнимо по модулю 11 с числом, которое получится, если сложить все цифры, стоящие на нечетных местах, считая справа, и вычесть из этой суммы сумму всех остальных цифр.

Задачи.

1. Найдите остаток от деления числа
$A=15\cdot218\cdot2324\cdot53\cdot99$ на .