книги из ГПНТБ / Чандрасекхаран, К. Введение в аналитическую теорию чисел

и, следовательно, 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'.

= ГК‘=™-

1=1

§ 3. Число решений сравнения. Мы уже видели в этой главе, что если (а, т) — 1, то линейное сравнение

= c(modm) разрешимо и имеет единственное решение. Поставим теперь вопрос о числе решений полиномиаль­ ного сравнения

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

Полиномиальные сравнения могут иметь решения, а могут их не иметь. Например, сравнение x2= 3 (m o d 7 ) не имеет решений.

вательно, любая степень, большая р— 1, может быть ре­ дуцирована и можно считать, что п<.р. Далее мы пред­

имеет не более п решений.

Доказательство. Докажем теорему индукцией по п. Для п = 1 утверждение теоремы справедливо, посколь­ ку (ао, р) = \. Предположим теперь, что теорема спра­ ведлива для п— 1, и докажем ее справедливость для п. Если сравнение (2) не имеет решений, то доказывать нечего. Если же оно имеет решение, скажем х ь то

Вычитая из (2) сравнение (3), мы получим сравнение

а0(хл — х") + ах(х”- 1 — х " - 1) + ...

■••+an- i ( * — Jfi) = 0 (modp), (4)

которому, очевидно, удовлетворяет каждое решение сравнения (2). Далее, мы можем переписать (4) в виде

(х—х,) (a0x™-1+ 6 1x " -2+ ...+ 6 „ _ 1)= 0 (m o d p ),

сравнения (2) должно удовлетворять или сравнению х—Xi==0(mod р),

которое имеет степень п— 1 и по предположению индук­ ции не более n— 1 решений. В таком случае сравнение

(2) может иметь самое большее п решений, что и требо­ валось доказать.