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

Определение. Пусть a и b — целые числа, m — натуральное. Говорят, что число a сравнимо с b по
модулю m, если 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} тогда и только тогда, когда a и b дают при делении на m равные остатки.

Доказательство. Разделим a и b на 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 — натуральное число, 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. Докажите, что

    \[1\cdot2\cdot3\times\ldots\times2000\cdot2001+2002\cdot2003\times\ldots\times 4001\cdot4002\]

делится на 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.

Комментарии (RSS)  |  Трекбек

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

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

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

    18 Июль 2012, 0:09

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

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

    2 Декабрь 2012, 0:06

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

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