Составители:
Рубрика:
11
Более того, множество классов, порождающими элементами кото-
рых являются эти числа, обладает свойством замкнутости, а именно:
при любых целых t произведение представителей классов (1+8*t; 3+8*t;
5+8*t; 7+8*t) дает в результате представителя одного из этих же классов.
Можно показать, что классы вычетов, получаемые в соответствии с
функцией Эйлера, всегда образуют абелеву группу по умножению. А
это, в частности, означает, что для любого представителя из этих клас-
сов можно найти обратный элемент из представителей этих же классов.
Упражнения
Постройте абелевы группы классов, порождаемые числами 10, 12,
15, 18, 21, 24, 25, 27, 28.
1.9. Теоремы Ферма и Эйлера
а) Теорема Ферма.
Если p – простое число и (a, p)=1, то a
p –1
≡ 1 mod p.
Пусть p = 23, a = 18. Очевидно, что (23, 18) = 1, следовательно,
18
22
≡ 1 mod 23. Проверить этот результат несложно. Для этого заметим,
что 18 ≡ –5 mod 23, поэтому можно написать эквивалентное сравнение
(–5)
22
≡ 1 mod 23 или 5
22
≡ 1 mod 23.
Последнее сравнение можно представить в виде (5
2
)
11
≡ 1 mod 23 и
так как 25 ≡ 2 mod 23, то 2
11
≡ 1 mod 23.
Полученное сравнение элементарно проверяется : 2048 ≡ 1 mod 23.
б) Теорема Эйлера.
Если m >1 и (a, m)=1, то a
ϕ(m)
≡ 1 mod m. Эта теорема обобщает
теорему Ферма, так как при m = p, ϕ(m = p) = p –1.
Пусть m = 18, a = 5. Очевидно, что (5, 18) = 1.
Функция Эйлера ϕ(m = 18) = 6. Поэтому 5
6
≡ 1 mod 18. Это сравнение
проверяется достаточно просто:
5
2
≡ 7 mod 18, следовательно, ((5
2
))
3
≡ 7
3
= 343 ≡ 1 mod 18.
Упражнения
На основании теорем Ферма и Эйлера доказать справедливость срав-
нений:
2
36
≡ 3
36
≡ … ≡ 36
36
≡ 1 mod 37;
2
100
≡ 3
100
≡ … ≡ 100
100
≡ 1 mod 101;
2
8
≡ 4
8
≡ 7
8
≡ 8
8
≡ 11
8
≡ 13
8
≡ 14
8
≡ 1 mod 15.
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
