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

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

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

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

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

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

Тогда
a-m\vdots m,m(q_1-q_2)\vdots m\Longrightarrow (r_1-r_2)\vdots<br />
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<br />
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}<br />
a\equiv b\pmod{m}\Longrightarrow(a-b)\vdots m\\<br />
a-b=-(b-a)\Longrightarrow -(b-a)\vdots m\Longrightarrow b\equiv a\pmod{m}.<br />
\end{array}

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

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

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

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

Пусть a – натуральное число, 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}, если k — четное,
10^k\equiv-1\pmod{11}, если k — нечетное.
a\equiv a_n-a_{n-1}+a_{n-2}-a_{n-3}+\ldots\pmod{11}

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

Задачи.

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

2. Найдите остаток от деления

a) 8! на 11;

б) a на 13, если a^x\equiv2 \pmod{13}  и a^{x+1}\equiv 6 \pmod{13}.

3. Докажите, что если 3^n\equiv-1 \pmod{10}, то 3^{n+4}\equiv-1 \pmod{10}.

4. Докажите, что
<br />
1\cdot2\cdot3\times\ldots\times2000\cdot2001+2002\cdot2003\times\ldots\times<br />
4001\cdot4002<br />
делится на 4003.

5. Докажите, что если n^{n+1}+(n+1)^n делятся на 3, то n\equiv3\pmod{6}.

6. Докажите, что если натуральные числа a\ne1 и n таковы, что a^n-1 делится на (a-1)^2, то n делится на a-1.

7. Докажите, что если a^s\equiv a^t\equiv1\pmod{m}, то a^d\equiv1\pmod{m}, где d – наибольший общий делитель s и t.

8. Выведите признаки делимости на 6, 8, 13.

Комментариев: 3

  1. 2 Задача от Hewlett-Packard | Математика, которая мне нравится:

    [...] значение при . Для этого переведем в двоичную систему счисления: И очевидно, что число, в двоичной записи которого [...]

  2. 3 Доказательство конца света в троичной системе счисления | Математика, которая мне нравится:

    [...] ставлю 0 последним, потому что в десятичной системе счисления на самом деле есть только девять цифр плюс ноль, [...]

Оставьте свой отзыв

Добавить изображение