Взаимнообратные по модулю ш
Обратным элементом по модулю т для элемента а называется число Ь, удовлетворяющее равенству ab = ba = l(mod тії). При этом числа а и b называются взаимно обратными по модулю т (или мультипликативно обратными по модулю т).
Теорема 2.45
Пусть (a,m) = 1 и Qr-і - знаменатель предпоследней подходящей дроби представления числа—. Тогда число(— l)kQk_1 является обратным к элементу а по модулю т.
а
Доказательство. Пусть число — представлено в виде цепной дроби:
я
— =(qi;q2—Чк) (2.159)
т
Рк—і Рк а
И пусть ---- и — две последние подходящие дроби числа —.
Qk-1 Qk r m
Тогда,
ВДк-1 - Pk-iQk = (-1)к. (2.160)
a Pk
b = 5k = ^ (2'161)
Так как по условию теоремы
(а, т) = 1, то
a(-l)kQk.1 - т(-1)Ч-1 = Г (2-162)
То есть значения
x=(-l)kQk-i,y = (-l)k+1Pk_1 (2.163)
являются целочисленными решениями уравнения ах — ту = 1 и, значит, а’1 = (-l)kQk-1. (2.164)
Например, используя алгоритма Евклида, найдем мультипликативно обратный элемент для вычета а = 25 по модулю m = 42.
25
Решение. Представим рациональное число г = —в виде цепной дроби.
Имеем, а0 = 25, аг = 42 . Применяем алгоритм Евклида:
|
I |
-1 |
0 |
1 |
2 |
3 |
4 |
5 |
|
Чі |
0 |
1 |
1 |
2 |
8 |
||
|
Pi |
0 |
1 |
0 |
1 |
1 |
3 |
25 |
|
Q> |
1 |
0 |
1 |
1 |
2 |
5 |
42 |
а0 = 25 = 42 х 0 + 25 = a1q1 + а2, аг = 42 = 25 х 1 + 17 = a2q2 + а3, а2 = 25 = 17 х 1 + 8 = a3q3 + а4, а3 = 17 = 8x2 + 1 = a4q4 + а5, а3 = 8 = 1 х 8 + 0 = a5q5, Получаем, ||= (0; 1,1,2,8). Теперь, заполняем табличку:
ао _
а2
а2 _
аз _
а4
«4 _
а5
- 25
- 42
- 42
- 25
- 25
- 17
- 17
- 8
- 8
- 1 '
’ _ п I 25 _
1 42
’ - 1 і 17 _
? — 1 + — — q?
; 25 42
; _ -і і 8 _
- — 1 + — — q3
, 17
- = 2+|= q4+^,
о CI4
= 8 = q5.
1-^
а2
F —
“з‘
4s
а4'
Таким образом, Qr-і = 5.
Тогда,
a' = (-l)kQk_1 = (-l)5x5 = -5.
Укажем, наименьший положительный вычет.
Так как —5 + 42 = 37, то для вычета а = 25 мультипликативно обратным элементом 25 * по модулю т= 42 будет являться число 37.
В завершении этого пункта рассмотрим обобщающую теорему о классе вычетов Zm.
Теорема 2.46
- 1. Если т составное число, то кольцо 7Lm содержит делители нуля.
- 2. Класс а кольца TLm обратим тогда и только тогда, когда НОД(а,щ) = 1.
- 3. Если т — просто число, то 7Lm является полем.
Доказательство.
1. Пусть т составное число, тогда его можно представить в виде произведения двух натуральных чисел
т = р ? q, каждое из которых меньше т. Очевидно, что р Ф о и q Ф д.
В тоже время
p-q= рд.
Таким образом, в Z„, существуют элементы р и q, которые отличны от нулевого, но их произведение равно 0, то есть. Zm содержит делители нуля.
2. Если а обратим в Z,„, то существует х Є Zm такой, что а • х = 1. Это значит, а • х = 1 или ах = 1 (mod m). Откуда следует, что НОД(а; т) = 1.
Обратно, если а и т взаимно просты, то согласно теореме о взаимно простых числах существуют целые числа х и у такие, что ах + ту = 1.
Тогда
ах + ту = 1 (mod т).
В таком случае, верно, что
ах = 1 (mod т).
Это значит, а • х = 1или а • х = 1.
Из последнего равенства следует, что а обратим в Zm.
3. Так как т простое число, то в Z,„ каждый ненулевой элемент обратим, а, значит, Z,„ поле.
Ч.т.д.
