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}]$

Тогда

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

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

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}$

$[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}]$

$[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}]$

$[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}]$

$[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. Докажите, что

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

Оставить комментарий

Свежие комментарии

alex в Интегрирование тригонометрических функций sin(x)^m*cos(x)^n. Правила понижения степени: “а что именно?” Апр 24, 18:31
alex в Иррациональные уравнения на примерах: “Ну эти уравнения не очень сложны, но рассказано очень хорошо про иррациональные уравнения - здесь я согласен!” Апр 24, 18:15
Константин в Иррациональные уравнения на примерах: “То чувство, когда всё разложено по полочкам и кажется очень просто, но на практике начинаются сложности. Математика требует не только…” Апр 15, 17:47
Настя в Интегрирование тригонометрических функций sin(x)^m*cos(x)^n. Правила понижения степени: “Реально помогло решить задачи дочке)” Апр 15, 17:43
Сергей в Квадратные уравнения. Примеры решения: “Никогда не был предрасположен к точным наукам. Вроде бы и примеры не сложные, но по истечении лет, и они вызывают…” Апр 15, 17:40