Сравнение по модулю m

1. Сравнение по модулю m.

2. Определение:

2
Определение:
• Два натуральных числа a и b , разность
которых кратна натуральному числу m ,
называются сравнимыми по модулю m .
обозначение: a ≡ b (mod m ).
или
• Целые числа a и b называют сравнимыми
по модулю m, если каждое из них при
делении на m дает один и тот же остаток
r.

3. Примеры:

3
Примеры:

4. Свойства сравнений по модулю:

4
Свойства сравнений по модулю:

5. Теорема:

5
Теорема:
• В любой части сравнения можно отбросить
или добавить слагаемое, кратное модулю.
a b mod m a km b mod m

6. Примеры:

6
Примеры:
• Найдите остаток от деления 229 на 11.
• Решение:
• Так как 25 ≡ -1 (mod 11),
( определение: 32-(-1)= 33 делится на 11), то по
свойству сравнений:
(25)5 ≡ (-1)5 (mod 11), то есть 225 ≡ -1 (mod 11) и
24 ≡ 5 (mod 11), и 229=225∙24 по свойству
сравнений 229 ≡ -5 (mod 11),
так как -5 ≡ 6 (mod 11), то остаток отделения
будет 6.

7. Дома:

7
Дома:
П1.8 и 1.9.
Решить №1.86(а,б);
1.95 (а,б).