[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]
| Определение |
Вычет a называется обратимым, если существует вычет b такой, что a*b ≡ 1 (mod n). Пишут a-1 = b. |
|---|
Тогда b - вычет, обратный к a.
Примеры: n = 18, a = 5.
5 * 11 = 55 =18 * 3 +1 ≡ 1 (mod 18). b = 11 - вычет, обратный к
a (mod 18).
n = 12, a = 5.
5 * 5 = 25 = 2*12 +1 ≡ 1 (mod 12). b = 5 - самообратимый вычет.
| Вычет а является обратимым по модулю n тогда и только тогда, когда а и n - взаимно просты (не имеют общих делителей не равных 1). |
Примеры: 6 и 25 - взаимно просты.
n = 25, a = 6.
6 * 21 = 126 ≡ 1 (mod 25). 21- обратный вычет к 6 (mod 25).
12 и 18 не являются взаимно простыми. Следовательно не существует такого b, что 12*b ≡ 1 (mod 18). Число (12*b-1) - нечетное и не может делиться на 18.
| Определение | Системой обратимых вычетов по модулю n называется множество чисел {a1, ... ,ak} таких, что все они обратимы по модулю n, попарно не сравнимы, и любой из них обратен с некоторым из вычетов в системе. |
|---|
Примеры: n = 10. Полная система обратимых вычетов {1, 3, 7, 9}.
1*1=1 ≡ 1 (mod 10).
3*7=21 ≡ 1 (mod 10).
9*9=81 ≡ 1 (mod 10).
Т.о. в системе два вычета 1 и 9 обратны самим себе, и два вычета 3 и 7
взаимно обратны.
Если модуль n является простым числом /не имеет делителей кроме 1 и
n/, то все числа от 1 до (n-1) взаимно просты с модулем
n. Тогда удобно иметь дело с системой обратимых вычетов {1, 2, ... ,
(n-1)}.
[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]