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

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

Обозначение. aequiv bpmod{m}.

Пример.

    [begin{array}{l} 45equiv75pmod{10}\ 182equiv-4pmod{6} end{array}]

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

Доказательство. Разделим a и b на m с остатками

    [begin{array}{l} a=mq_1+r_1,quad 0le r_1<m,\  b=mq_2+r_2,quad 0le r_2<m,\  a-b=m(q_1-q_2)+(r_1-r_2). end{array}]

Тогда

    [a-mvdots m,m(q_1-q_2)vdots mLongrightarrow (r_1-r_2)vdots mLongrightarrow r_1-r_2=0Longrightarrow r_1=r_2.]

Следовательно,

    [r_1=r_2Longrightarrow a-b=m(q_1-q_2)Longrightarrow a-bvdots m.]

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

1. aequiv apmod{m} (рефлексивность),

2. aequiv bpmod{m}Longrightarrow bequiv apmod{m} (симметричность),

3. aequiv bpmod{m},bequiv cpmod{m}Longrightarrow aequiv cpmod m (транзитивность),

4. aequiv bpmod{m},cequiv dpmod{m}Longrightarrow astackrel{+}{stackrel{-}{cdot}}bequiv cstackrel{+}{stackrel{-}{cdot}}dpmod{m}.

5. acequiv bcpmod{m}, НОД(c,m)=1Longrightarrow aequiv bpmod{m}.

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

1. a-a=0vdots mLongrightarrow aequiv apmod{m}

2.

    [begin{array}{l} aequiv bpmod{m}Longrightarrow(a-b)vdots m\ a-b=-(b-a)Longrightarrow -(b-a)vdots mLongrightarrow bequiv apmod{m}. end{array}]

3.

    [begin{array}{l}left.begin{array}{l} aequiv bpmod{m}Longrightarrow a-bvdots m\ bequiv cpmod{m}Longrightarrow b-cvdots m end{array}right|Longrightarrow \[4mm] Longrightarrow a-b+(b-c)vdots mLongrightarrow a-cvdots mLongrightarrow aequiv cpmod{m} end{array}]

4.

    [begin{array}{l} aequiv bpmod{m}Longrightarrow a-bvdots m,\ cequiv dpmod{m}Longrightarrow c-dvdots 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+dpmod{m},\ ac=(klm^2+blm+dkm)+bdequiv bdpmod{m},\ a-c=(k-l)m+(b-d)equiv b-dpmod{m}. end{array}]

5.

    [left.begin{array}{l} ac-bcvdots m,\ c(a-b)vdots m,\ {rm GCD}(c,m)=1, end{array}right|Longrightarrow(a-b)vdots mLongrightarrow aequiv bpmod{m}.]

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

Пусть a — натуральное число, a=(overline{a_0a_1ldots a_n})_{10},
a=a_0cdot10^n+a_1cdot10^{n-1}+a_2cdot10^{n-2}+dots+a_n

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

Так как 10equiv1pmod{3,9}, то 10^kequiv1pmod{3,9}

    [Longrightarrow aequiv a_0+a_1+a_2+dots+a_npmod{3,9}.]

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

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

kge1Longrightarrow10^kequiv0pmod{2,5}Longrightarrow aequiv a_npmod{2,5}

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

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

kge2Longrightarrow 10^kequiv0pmod{4,25}Longrightarrow aequiv a_{n-1}cdot10+a_npmod{4,25}

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

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

10equiv-1pmod{11}

10^kequiv1pmod{11}, если k — четное,
10^kequiv-1pmod{11}, если k> — нечетное.
aequiv a_n-a_{n-1}+a_{n-2}-a_{n-3}+ldotspmod{11}

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

Задачи.

1. Найдите остаток от деления числа
A=15cdot218cdot2324cdot53cdot99 на 7.

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

a) 8! на 11;

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

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

4. Докажите, что

    [1cdot2cdot3timesldotstimes2000cdot2001+2002cdot2003timesldotstimes 4001cdot4002]

делится на 4003.

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

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

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

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

Ссылка на основную публикацию