Файл: Чандрасекхаран, К. Введение в аналитическую теорию чисел.pdf

и, следовательно, 1 -j-аб ( = 641) делит f5.

По-видимому, неизвестно, являются ли простыми ка­ кие-либо другие числа Ферма, за исключением первых четырех.

ГЛАВА It

СРАВНЕНИЯ

если т |(а— Ь). Это соотношение между а, b и ш мы бу­ дем называть сравнением и обозначать символом а = = b(modm). Если т \(а—Ь), мы говорим, что а и Ь не сравнимы по модулю т, и записываем это следующим образом: аФ Ь(тодт ).

Отношение сравнимости является отношением экви­

ет множество целых чисел на непересекающиеся классы эквивалентности А, В, С, ..., причем два целых числа сравнимы друг с другом по модулю т тогда и только тогда, когда они лежат в одном и том же классе. Эти классы называются классами вычетов по модулю т.

Очевидно, что целые числа 0, 1, ..., т— 1 лежат в раз­ ных классах вычетов. Так как каждое целое число п мо­ жет быть записано в виде n=qm-\-r, — 1, то каждое целое сравнимо по модулю т с одним из чисел О, 1, ..., т— 1. Следовательно, имеется точно т классов вычетов по модулю т и числа 0, 1, ..., т— 1 образуют множество представителей этих классов.

Подобно обычным равенствам, сравнения можно складывать, вычитать и умножать. Если a==6 (mod т)

и c==d(mod т ), то мы имеем a + c = 6 + d (m o d т), а—с =

В общем случае делить сравнения нельзя. Мы имеем

2 = 12(mod 10), но l# 6 (m o d 10).

но умножения, единичным элементом которой будет класс, содержащий целое число 1. Каждый приведенный класс вычетов имеет обратный, так как если (а, т) = 1, то существует целое а', такое, что а а '= 1 (mod т ).

Рассмотрим аддитивную группу всех классов вычетов по простому модулю р. За исключением нулевого класса, все остальные классы вычетов в этом случае будут при­ веденными классами вычетов и, следовательно, образу­ ют также мультипликативную абелеву группу. Дистри­ бутивный закон А-( В + С)=А-В-\-А-С непосредственно следует из дистрибутивного закона для целых чисел. Следовательно, справедлива следующая теорема:

Теорема 1. Классы вычетов по простому модулю р об­ разуют поле из р элементов.

Системы вычетов. Из всех m классов вычетов по мо­ дулю пг мы выделили приведенные классы вычетов по модулю пг. Полная система вычетов по модулю m состо­ ит из m представителей, взятых по одному из каждого класса. Следовательно, множество из пг целых чисел об­ разует полную систему вычетов по модулю т, если толь­ ко его элементы попарно не сравнимы друг с другом по модулю т. С другой стороны, полная приведенная си­ стема вычетов по модулю m состоит из представителей, взятых по одному из каждого приведенного класса по модулю т.

Например, числа 0, 1, ..., 7 образуют полную систему вычетов (mod 8), в то время как 1, 3, 5, 7 образуют пол­ ную приведенную систему вычетов (mod 8).

Функция Эйлера ф. Функция Эйлера ф определяется для всех положительных целых чисел п следующим обра­ зом: значение ф(п) равно количеству положительных це­ лых чисел s=;п, которые взаимно просты с п.

Из определения следует, что значение ф(п) равно так­ же числу приведенных классов вычетов по модулю п.

§ 2. Теоремы Эйлера и Ферма. Если а ь а2, ..., ат со­ ставляют полную систему вычетов* по модулю т и если k взаимно просто с т, то множество kau ka2, ..., kam так­ же будет полной системой вычетов по модулю т. Это

Так как гь г2, ..., гф(т) взаимно просты с т, то тем самым нами доказана

(а, р) = 1, то аР-1= 1 (mod р) .

Чтобы доказать важное свойство функции Эйлера, нам потребуется следующая теорема:

Теорема 4. Пусть (пг, пг') — 1. Если а пробегает пол­ ную систему вычетов по mod m и а' пробегает полную систему вычетов по mod m', то am'-\-a'm пробегает пол­ ную систему вычетов по mod mm'.

Определение. Комплекснозначная функция, опреде­ ленная на множестве положительных целых чисел, назы­ вается арифметической функцией.

Арифметическая функция f называется мультиплика­ тивной, если

(i)f не равна тождественно нулю;

(п) из (m, п) = 1 следует, что f(mn)=f(m) -f(n) .

Используя теорему 4, мы можем теперь доказать следующий результат:

Теорема 5. Функция Эйлера ср (п) мультипликативна.

Доказательство. Так как ср(1) = 1, то ср(гс) не равна тождественно нулю. Пусть (m, m') = 1, и пусть а и а' пробегают полные системы вычетов по модулям пг и т' соответственно. Тогда по теореме 4 ат'-\-а'т пробегает полную систему вычетов по mod тт'. Следовательно, Ф(тт') равна числу целых чисел вида ат'-\-а'т, удов­ летворяющих условию (ат '+а'т , тт') = 1. Но послед­ нее условие эквивалентно следующим двум условиям:

(ат'-\-а'т, т) = 1 и (ат'-{-а'т, т') = 1,

или

(ат ',т ) = 1 и (а'т, т') = \,

или

(а, т) — \ и (а',т ') = 1.

Так как имеется ф (т) значений а, для которых (а, т) —

Из доказательства теоремы 5 вытекает следующее утверждение:

Теорема 5'. Пусть (m, m') = 1. Если а пробегает пол­

ную приведенную систему вычетов по mod m и а' пробе­

гает полную приведенную систему вычетов по mod m', то am'-\-a'm пробегает полную приведенную систему выче­ тов по mod mm'.