Теория чисел. Ч. 2 (110,00 руб.)

Стр.1

Стр.3

Стр.6

Стр.7

Стр.8

Стр.9

Стр.10

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Р.С. Адамова ТЕОРИЯ ЧИСЕЛ Часть 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   p1 ,  x y  x p2 y p2  y p1  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 q1 Выполнив в (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, где kZ. 7 ( 1) 2 1 ( 1) 2 1     p  p  2  x 1q   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 q1 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 p1 x y z q . Аналогично получим, что (mod q) . (31)

Стр.7

§ 6. Классы вычетов по модулю m Пример 11 . [3]5={3+5k}kZ = {  , -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}. Полная система наименьших по абсолютной величине вычетов m1 (когда 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} имеем, например, 57 = 4, 25 = 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 m1 … m2 … k … … m k … … … … m 2m … (n–1) m1 (n–1) m2 … (n–1) mk … 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