Ю.В. Нестеренко - Курс лекций по теории чисел, страница 5

m.3. Если ab ≡ ac (mod m) и (a, m) = 1, то b ≡ c (mod m). Действительно, если m | (ab − ac) и m не делит a, топо лемме 1.6 получаем, что m | (b − c), а это и требовалось.Замечание. Условие (a, m) = 1 в последнем свойстве существенно: 4 ≡ 0 (mod 4), но из этого не следует,что 2 ≡ 0 (mod 4).Итак, мы разбили все множество Z на классы сравнимых по модулю m элементов (классы вычетов по модулю m): 0, 1, . . . , m − 1. Из свойств, указанных выше, сразу следует, что классы вычетов по модулю m образуюткольцо, обозначаемое Z/mZ.17Чтобы не доказывать эти свойства вычетов, можно было бы сослаться на алгебру и сказать: рассмотрим факторкольцо Z/mZ.Очень часто для кольца Z/mZ используется более короткое обозначение: Zm .

Мы тоже будем его использовать.Лемма 3.2. При всех a ∈ Z, для которых (a, m) = 1, уравнение ax ≡ b (mod m) имеет единственноерешение в Zm . Рассмотрим отображение S : Zm → Zm , определённое по правилу S : k → ak. Заметим, что S инъективно:(если ak1 ≡ ak2 (mod m), то k1 ≡ k2 (mod m)). Но инъективное отображение конечных множеств биективно,значит, найдётся ровно одно x ∈ Zm , для которого ax = b.

Следствие 3.1. Если (a, m) = 1, то элемент a обратим в Zm . Уравнение ax ≡ 1 (mod m) разрешимо. А это и означает, что x = a−1 . Определение. Количество натуральных чисел, не превосходящих m и взаимно простых с m, называетсяфункцией Эйлера и обозначается ϕ(m).Утверждение 3.3. Количество обратимых элементов в Zm равно ϕ(m). Они образуют группу, котораяобозначается Z∗m . Первое сразу следует из предыдущего следствия и определения функции Эйлера. Доказательство второго утверждения предоставляется читателю. Как вычислять функцию ϕ(m)? Вообще говоря, вычисление ϕ для произвольного m — это алгоритмическитрудоёмкая задача.

Однако, если p — простое, то ясно, что ϕ(p) = p − 1. Легко также видеть, что ϕ(pk ) == pk − pk−1 = pk−1 (p − 1), поскольку лишь числа, кратные p, не взаимно просты с pk .Определение. Функция f называется мультипликативной, если для любых взаимно простых чисел a и bимеет место равенство f (ab) = f (a)f (b).Замечание.

Всякая вполне мультипликативная функция является мультипликативной, но не наоборот.Лемма 3.4. Функция Эйлера мультипликативна. Пусть (a, b) = 1. Рассмотрим множество чиселM := m = ak + bl k = 0, . . . , b − 1,l = 0, . . . , a − 1 .(1)Докажем, что все они различны. Действительно, если ak1 + bl1 = ak2 + bl2 , то b (ak1 − ak2 ), значит, b (k1 − k2 ).Воспользовавшись тем, что |k1 − k2 | < b, заключаем, что k1 = k2 , поэтому и l1 = l2 .Теперь докажем, что (ak + bl, ab) = 1 тогда и только тогда, когда (a, l) = 1 и (k, b) = 1.⇒ Предположим противное: найдётся p такое, что p | a и p | l.

Но тогда p | (ak + bl) и p | ab — противоречие.Взаимная простота k и b доказывается симметрично.⇐ Предположим противное: найдётся p такое, что p | (ak + bl) и p | ab. Тогда p делит либо a, либо b. Пусть,для определённости, p | a. Тогда p | bl. Но p не может делить b (т. к. a и b взаимно просты), значит p | l. Но этопротиворечит тому, что (a, l) = 1.Докажем, что ak + bl лежат в разных классах вычетов по модулю ab. Действительно, если ak1 + bl1 ≡ ak2 + bl2(mod ab), тогда a | (a(k1 − k2 ) + b(l1 − l2 )), поэтому a | (l1 − l2 ), значит, l1 = l2 . Аналогично, k1 = k2 .Итак, количество чисел, взаимно простых с ab и меньших ab, столько, сколько существует в M чисел ak + bl,для которых (a, l) = 1, и (k, b) = 1.

А это и означает, что ϕ(ab) = ϕ(a)ϕ(b). Теорема 3.5 (Эйлер). Если (a, m) = 1, то aϕ(m) ≡ 1 (mod m). 1◦ Группа Z∗m имеет порядок ϕ(m). А по теореме Лагранжа порядок элемента делит порядок группы,значит aϕ(m) = 1 ⇒ aϕ(m) ≡ 1 (mod m).2◦ Можно доказать эту теорему, не ссылаясь явно на алгебру. Пусть b1 , . .

. , bϕ(m) — все числа из отрезка [1, m],взаимно простые с m. Легко проверить, что числа ab1 , . . . , abϕ(m) тоже взаимнои лежат в просты с модулемразных классах вычетов. Значит, существует биекция между b1 , . . . , bϕ(m) и ab1 , . . . , abϕ(m) . Поэтомуb1 · . . . · bϕ(m) ≡ ab1 · . . . · abϕ(m)откуда aϕ(m)(mod m),(2)≡ 1 (mod m). Следствие 3.2 (Малая теорема Ферма). Если простое число p не делит a, то ap ≡ a (mod p).Утверждение 3.6. Множество простых вида 4n + 1 бесконечно.

Предположим противное: p1 , . . . , pr — все простые такого вида. Составим число N := 4p21 · . . . · p2r + 1 == a2 + 1, где a = 2p1 · . . . · pr . Пусть q — простой делитель N . Очевидно, что q 6= p1 , . . . , pr . Имеем a2 + 1 ≡ 0(mod q), то есть a2 ≡ −1 (mod q). Возведем левую и правую части последнего выражения в степень q−12 (онацелая, поскольку q, очевидно, нечётное).

Получимaq−1 ≡ (−1)q−12(mod q).Пользуемся теоремой Ферма и получаем, что q = 4k + 1. Противоречие. 18(3)3.1.3. Ещё одно доказательство бесконечностимножества простых чисел вида 4n ± 1Хотя этот факт нами уже установлен в предыдущих параграфах, не лишним будет узнать доказательство,предложенное Эйлером. Похожий метод будет использован в общем случае, функции χ назовутся характерами,а функции Li — L-функциями Дирихле.Теорема 3.7.X 1X 1= ∞,= ∞.(4)ppp≡3(4)p≡1(4)Введем новые функцииL0 (s) := 1 +∞X111+ s + ...

=,s35(2n+1)s0(5)∞X (−1)n11L1 (s) := 1 − s + s − . . . =.35(2n + 1)s0Оба ряда сходятся, а второй ещё и абсолютно сходится. Пусть(0, n = 2k,χ0 (n) :=1, n = 2k + 1,(6) 0, n = 2k,χ1 (n) :=1, n ≡ 1 (mod 4),−1, n ≡ 3 (mod 4).ТогдаL0 (s) =∞Xχ0 (n)1ns,L1 (s) =∞Xχ1 (n)1ns(7)Легко проверить, что χ0 и χ1 — вполне мультипликативные функции. Значит, для функцииили χ = χ1 , можно применить лемму 2.10 и получить, чтоL0 (s) =−1Yχ0 (p)1−,psL1 (s) =p>3−1Yχ1 (p)1−.psp>31p2 .x22P P 1Значит, rp (s) 6n2 6 ∞. ПосемуX χ(p)p>3Значит, получаемXp≡1(4)Xp≡1(4)(9)(10)+ .

. . , поэтому|x|2|x|31|x|2++ . . . 6 (|x|2 + |x|3 + . . .) =6 |x2 |.2322(1 − |x|)ln L(s) =где χ = χ0p>3Оценим rp (s). Если |x| < 12 , то ln(1 − x) = − x +2Поэтому rp (s) 6 χ(p)sp 6χ(n)ns ,p>3Логарифмируя левую и правую части полученных выражений, получаем XX χ(p)χ(p)ln L(s) = −ln 1 − s=+r(s).ppps| ln(1 − x) + x| 6(8).ps+ O(1),s > 1.X 11+= ln L0 (s) + O(1),sppsp≡3(4)X 11−= ln L1 (s) + O(1).sppsp≡3(4)19(11)(12)(13)Складывая и вычитая эти равенства, получаемX 11= ln L0 (s) + ln L1 (s) + O(1).sp2p≡1(4)Xp≡3(4)(14)11= ln L0 (s) − ln L1 (s) + O(1).sp2Пусть s ∈ R. Перейдём к пределу s → 1+. Если бы ряды из формулировки теоремы сходились, то это быозначало, что существуют пределы правых частей равенств. Покажем, что они не существуют.L0 (s) =∞X0∞11 X1ζ(s)>= s → ∞,(2n + 1)s2s 0 (n + 1)s2s → 1,(15)поскольку ζ-функция в точке 1 имеет полюс.PТеперь оценимP L1 (s).

Применим признак Дирихле равномерной сходимости nряда: если | a1n (s)| 6 C иbn ⇒ 0, то рядan (s)bn (s) сходится равномерно. В нашем случае an (s) = (−1) , а bn (s) = (2n+1)s . Значит,L1 (s) сходится равномерно при s → 1. Поэтому1 1 1lim ln L1 (s) = ln L1 (1) = ln 1 − + − + . . . < ∞.(16)s→13 5 7Значит, наши ряды расходятся (а значит, слагаемых в них бесконечно много).

3.2. Характеры Дирихле3.2.1. Определение и простейшие свойстваЗафиксируем некоторое m > 2.Определение. Вполне мультипликативная m-периодическая функция χ : Z → C называется характеромДирихле, если χ(n) 6= 0 тогда и только тогда, когда (n, m) = 1. Характер(1, (n, m) = 1,χ0 (n) =(17)0, (n, m) 6= 1называется главным характером.Сформулируем некоторые очевидные свойства характеров.1◦ Если χ1 и χ2 — характеры, то и χ1 χ2 — характер.2◦ χ0 χ = χ для любого χ.Далее мы покажем, что характеры образуют группу (пока не доказано существование обратного элемента).3◦ По определению χ(1) 6= 0.

Из мультипликативности следует, что χ(1) = 1.4◦ Пусть (n, m) = 1. Тогда nϕ(m) ≡ 1 (mod m). Поэтому 1 = χ(1) = χ nϕ(m) = χϕ(m) (n). Значит, ненулевыезначения характера — это просто корни из единицы степени ϕ(m).5◦ Очевидным следствием 4◦ является следующий полезный факт: |χ(n)| 6 1 для всех n.Теорема 3.8. Для каждого m > 2 существует в точности ϕ(m) характеров.(mXϕ(m), χ = χ0 ,χ(n) =(18)0,χ 6= χ0 .n=1(Xϕ(m), n ≡ 1 (mod m),(19)χ(n) =0,n 6≡ 1 (mod m).χ 1◦ Группа Z∗m абелева, а потому единственным образом разлагается в прямое произведение циклическихподгрупп:Z∗m = H1 × .

. . × Hr ,(20)Hj = hcj i , |Hj | = dj , d1 · . . . · dr = ϕ(m).Иначе говоря, если n ∈ Z∗m , то n = ck11 · . . . · ckr r . На языке сравнений это звучит так: если (n, m) = 1, тоn = ck11 · . . . · ckr r (mod m).Пусть ξk — корень из 1 степени dk , k = 1, . . . , r. Обозначим ξ := (ξ1 , . . . , ξr ). Построим функцию(0,(n, m) 6= 1,χξ (n) :=(21)ξ1k1 · . . . · ξrkr , n ≡ ck11 · . . .

· ckr r (mod m).20Очевидно, что это характер. Покажем теперь, что разным наборам ξ соответствуют разные характеры. Действительно, если ξi 6= νi , то ξi = χξ (ci ) 6= χν (ci ) = νi . Значит, количество построенных характеров совпадает сколичеством наборов ξ, а их d1 · . . . · dr = ϕ(m).Теперь докажем, что других характеров нет. Пусть χ — произвольный характер. Покажем, что он определяddется значениями на образующих группы. Пусть τi := χ(ci ). Поскольку cj j ≡ 1 (mod m), то 1 = χ(1) = χ(cj j ) == χdj (cj ).

Таким образом τ := (τ1 , . . . , τr ) — это набор корней из единицы соответствующих степеней. Поэтому,если (n, m) = 1, то χ(n) = χ ck11 · . . . · ckr r = τ1k1 · . . . · τrkr . Значит, χ уже содержится в построенном множествехарактеров и первое утверждение полностью доказано.mP2◦ Если χ = χ0 , то очевидно, чтоχ(n) = ϕ(m). Если же χ 6= χ0 , то сопоставим этому характеру набор ξn=1такой, что если (n, m) = 1 и n ≡ ck11 · . . . · ckr r (mod m), то χ(n) = ξ1k1 · . . . · ξrkr . Поэтомуdj −1mrXYX kXXχ(n) =χ(n) =ξ1k1 · . . .

· ξrkr =ξj j  = 0.n=1j=1k1 ,...,krn : (n,m)=1(22)k=0Последнее равенство обосновано тем, что найдётся k такое, что ξk 6= 1 и поэтому один из сомножителей равен 0.Поясним, почему один из сомножителей равен нулю. Пусть ξ — корень степени d из 1, причём ξ 6= 1. Покажем, что 1 + ξ + ξ 2 ++ . . . + ξ d−1 = 0. Умножение этой суммы на ξ означает поворот, и при этом повороте фигура из d векторов, торчащих из нуля ввершины правильного d-угольника, переходит в себя. Значит, сумма тоже не поменяется.