МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
Р.С. Адамова
ТЕОРИЯ ЧИСЕЛ
Часть 2
Учебно-методическое пособие
Воронеж
Издательский дом ВГУ
2017
Стр.1
§ 5. Сравнения
§ 5. Сравнения
Рассмотрим делимость в кольце ц е лых чисел. Пусть a, b Z, , m N.
Определение 8 . Говорят, что a д е лит с я на b, если существует q Z
такое, что a = b q.
Определение 9. Наибольшим общим д е ли т е лем целых чисел
a1, a2, , ak называется наибольший среди их общих делителей.
Определение 10. Два числа a, b Z называются сра внимыми по
. Это записывается выражением
модулю m, если a b m
a b (mod m) ,
которое называется сравнением по модулю.
Заметим, что каждое число сравнимо по модулю m с остатком от
деления его на m.
Свойства сравнений по одному модулю.
a b (modm) ( )
a b(modm) a c b d(modm)
c d(modm)
a b
b c
(mod )
(mod )
a b(mod )m a m b m
a c b d(modm)
a c b d(modm)
m a c(modm)
m
( , ) ( , )
(19)
(20)
Доказательства этих свойств очень просты. Рассмотрим их применение.
(18)
d
a
k a k b (modm k), Z,
a b (modm n N,
),
n
n
),
f a f b( ) (modm f Z[x],
d
b
), ,
(17)
(modm a b d d m
, ( , ) 1.
3
Стр.3
§ 5. Сравнения
2) x
x
p 1
d
x d . Поскольку (x y d)
Это невозможно согласно выбору решения (x, y, z).
Итак, получили противоречия, которые доказывают, что множители в
правой части (27) действительно взаимно просты. Так как их произведение
p y dp , откуда, в силу (26), z d z d
p
, , и в результате имеем (x y z d),,
есть z p , то эти сомножители являются p-ми степенями взаимно простых
чисел, т. е.
x y A A Z,
p
A R 1.
x
,
Записав соотношение (26) в виде x ) , получим, в силу (52),
что возможно представление:
p
(
Аналогично получим, что
y z C Cp
z)
p
x z B Bp
(
y
, .Z
, .Z
условию теоремы это число q – простое, поэтому
x
xyz q
x
x
y
y
z
z
p
p
p
p
p
p
1
1
1
z q
y q
x q
1
y
z
q
(mod )
(mod )
q
q
(mod )
(mod )
q
1
1
q
(mod )
(mod )
q
q
q
1
1
q 1
1(modq)
q)
1(mod y
1(modq)
p
z
p
x
y
p
1
1
2
0
z
x
2
2
p
p
2 p
p
(29)
(30)
Покажем, что для выбранного решения (x, y, z) произведение
xyz p2 1 . Для краткости записи обозначим 2p +1 через q. Согласно
1(modq)
1(mod q)
1(modq)
(mod )
p
2
(mod )
p
Полученное противоречие c соотношением (26) говорит о том, что xyz q .
Следовательно, по крайней мере один из сомножителей x , y , z делится
на q. Не ограничивая общности доказательства, предположим, что z q .
Тогда
2 (
p
z
x y) (x z) (y z A B C
)
6
p
p
p
A B C q .
p
p
z
x
p
y
p
p
p1
,
x y x
p2
y
p2
y
p1
R R Z,
p
,
(28)
, то получаем, что и y d , и
.
Стр.6
§ 6. Классы вычетов по модулю m
Отсюда
A B C (mod q
p
p
p
p
)
). Применяя теорему Ферма как и выше,
докажем, что ABC q . Но теперь мы сможем доказать, какой именно из
( , , ) ,
сомножителей делится на q , это А . Действительно,
B q B q
но по условию ( , , )
x y A
A q
p y (mod R px
p
(x y q)
x
( , )
1
R
q)
Далее, согласно (28) имеем (A, R) = 1, поэтому
A q R q
С другой стороны, из сравнения, полученного в (31), имеем
)
R
B q
z q
2 p
x z B
p
p x
(mod p x
q) 1
x B (modq)
1 mod
p
B
q1
Выполнив в (32) соответствующую замену, получим 1 p2 (mod q), но
1 p (modq) 1 2 1
2
p
p
p
теоремы.
§ 6. Классы вычетов по модулю m
Отношение сравнимости двух чисел по модулю m является отношением
эквивалентности, поэтому оно разбивает множество Z на классы
эквивалентности, которые называются классами вычетов по модулю m.
Определение 12. Кла с сом выч е то в числа a по модулю m называется
совокупность всех целых чисел, сравнимых с ним по этому модулю, а
каждое из этих чисел называется выче т ом числа a по этому модулю.
Класс вычетов числа a по модулю m будем обозначать [a]m или короче –
[a]. Очевидно, этот класс состоит из чисел вида a + km, где kZ.
7
( 1) 2 1
( 1) 2 1
p
p
2
x
1q
p
p
1(modq)
2
p
( 1) 2 1.
( 1) 2 1
p
p
p
p
Полученное противоречие указывает на справедливость утверждения
q
2 ( 1)
2 p
B
x
2 2( 1)
p
(modq
p p
Покажем, что в последнем сравнении x p2 1( )
p
2 ( 1)
B
1(modq)
1(mod ) 1(mod ).
2 2 2p
q1
q R
2p
q
(32)
можно заменить на 1:
2 ( 1)
(modq)
C q и остается, что именно A q .
Выведем следствия из этой делимости :
(x z q x q x q y q
x y z 1. Следовательно, B q
p
p
p1
x y z q
. Аналогично получим, что
(mod q) .
(31)
Стр.7
§ 6. Классы вычетов по модулю m
Пример 11 . [3]5={3+5k}kZ = { , -7, -2, 3, 8, 13, 18, }.
Свойства классов вычетов по модулю m
1. [a] [b]
a
c
2. [ ] [ ]
[ ] [ ]
a
c
b
a b(modm)
d
[a c] [b d]
a c
a c]
[ ] [ ] [a c]
[a c] [b d]
(33)
(34)
Последнее свойство гарантирует корректность следующего определения
операций сложения и умножения классов вычетов по модулю m:
[ ] [ ] [
Относительно этих операций множество всех классов вычетов по
модулю m является кольцом. Это кольцо обозначается Z/m. В нем операция
умножения обладает свойством коммутативности, ассоциативности,
наличия единичного элемента, которым оказывается класс [1].
Теорема 23. В кольце Z/m класс [a] является обратимым элементом
тогда и только тогда, когда (a, m) = 1.
Доказательство. [a] – обратим существует [k] Z/m такой,
что [k][a] = 1 существуют k, l Z такие, что ka – 1 = lm (a, m) = 1.
Следствие. Если (a , m) =1, то существует число k Z такое,
что a k 1(mod m). Это число k обладает свойством: ( k , m) 1.
Правило построения обратного элемента в кольце Z/m
Чтобы построить обратный элемент к классу [a] Z/m, нужно
заменить a его наименьшим положительным вычетом по модулю m
(т. е. остатком от деления на m);
выполнить алгоритм Евклида последовательного деления m на этот
вычет;
дробь P
Q q q
по всем неполным частным этого алгоритма q1, q2, , qn вычислить
1 2,
, ,qn ,
[a]–1= [k], где k= (–1) n P.
Замечание. Построенное число k обладает свойством :
a k 1 (mod m)
Пример 12 . Вычислить класс [–11]–1 в кольце Z/8.
1) –11 5 (mod 8)
2)8 = 5 1 + 3
5 = 3 1 + 2
3 = 2 1 + 1
2 = 1 2
8
(35)
Стр.8
§ 7. Полная и приведенная система вычетов по модулю m
3) P
Q
| , , | 111 3
2
4)[–11]–1 = [–3]
простое число. Доказательство. Кольцо Z/m – поле в Z/m каждый класс
[ a] [0] – обратим каждое число a Z, не делящееся на m,
взаимно просто с ним m – простое.
§ 7. Полная и приведенная система вычетов по модулю m
Определение 13. Полной сис т емой выч е то в по модулю m
называется совокупность чисел, взятых по одному из каждого класса
вычетов по модулю m.
Пример 13 .
Полная система наименьших неотрицательных вычетов по модулю m:
{0, 1, 2, , m – 1}.
Полная система наименьших положительных вычетов по модулю m:
{ 1, 2, , m – 1, m}.
Полная система наименьших по абсолютной величине вычетов
m1
(когда m – нечетное):
m 1 m 3
2
,
2
, ,
, , ,
0 1
2
.
Полной системой вычетов по модулю 8 будет, например, система
чисел {12, 3, – 6, 9, 22, – 11, 15, 0}.
Теорема 25. Всякая полная система A вычетов по модулю m является
кольцом относительно операций сложения и умножения, выполняемых по
этому модулю :
a b c , если c A c a b (modm)
a b d , еслиd A d ab (modm)
и
и
.
(36)
Доказательство. Взаимно однозначное соответствие между A и Z/m,
устанавливаемое по закону a [a], переносит на A из Z/m операции
сложения и умножения, которые в A выглядят именно так, как описано
в формулах (36).
Следствие. Полная система вычетов по модулю m является полем
относительно операций сложения и умножения, выполняемых по этому
модулю, тогда и только тогда, когда m – простое число.
Замечание. Полную систему наименьших неотрицательных вычетов по
модулю m с операциями (36) будем обозначать Zm.
9
Теорема 24. Кольцо Z/m является полем тогда и только тогда, когда m –
Стр.9
§ 7. Полная и приведенная система вычетов по модулю m
Пример 14 . В Z8 = {0, 1, 2, 3, 4, 5, 6, 7} имеем, например, 57 = 4,
25 = 2, обратным к 5 будет 5, а элемент 4 не имеет обратного.
Из свойства сравнений (20) следует, что если один элемент в классе
вычетов взаимно прост с модулем, то и любой другой элемент этого класса
обладает этим же свойством. Это позволяет сделать следующее
определение.
Определение 14. Привед енной си с т емой выч е то в по модулю m
называется совокупность чисел, взятых по одному из каждого класса
вычетов, взаимно простых с этим модулем.
Пример 15 .
1. Приведенной системой вычетов по модулю 8 будет, например,
совокупность чисел {3, 9, – 11, 15}.
2. Если p – простое число, то приведенной системой наименьших
неотрицательных вычетов будет система
{1, 2, … , p – 1}.
Очевидно, что во всех приведенных системах вычетов по модулю m
одно и то же число вычетов. Оно равно количеству чисел среди 1, 2, … , m,
взаимно простых с m. Число этих чисел обозначается (m). Оно определяет
функцию от m на множестве натуральных чисел. Эта функция называется
ф у н к ц и е й Э й л е р а .
Пример 16 . (8) = 4; ( p ) = p – 1, если p – простое число.
Теорема 26. Функция Эйлера является мультипликативной.
Доказательство. Необходимо показать, что для натуральных чисел m и n
при условии (m, n) = 1 будет справедливым соотношение
(m n) = (m) (n).
вычетов по модулю mn:
1
2
m1
…
m2
…
k
…
…
m k
…
…
…
…
m
2m
…
(n–1) m1 (n–1) m2 … (n–1) mk …
mn
Выделим из них числа, взаимно простые с m, воспользовавшись
соотношением (20): (im + k, m) = 1 (k, m) = 1. Эти числа составляют
столбцы, номера которых взаимно просты с m. Таких столбцов (m).
Каждый из этих столбцов представляет полную систему вычетов по модулю
n. Действительно, в столбце n чисел и они попарно несравнимы по этому
модулю потому, что
sm k im k(modn) sm im(mod s i(mod (s i n)
n)
n)
10
,
(37)
Выпишем в таблицу полную систему наименьших положительных
…
Стр.10