А.И. Галочкин, Ю.В. Нестеренко, А.Б. Шидловский - Введение в теорию чисел (1159516), страница 10
Текст из файла (страница 10)
1). Отсюда следует, что все целые числа по модулю т разбиваются на т непересекающихся классов сравнимых между собой чисел (т. е. имеющих одинаковые остатки при делении на т). Каждое число, входящее в какой-либо из классов, называется вычетом этого класса, а сами классы — классами вьгчегов по модулю т. Простейшие свойства сравнений напоминают свойства обычных числовых равенств. Укажем только некоторые из них: 1) Два числа, сравнимые с третьим, сравнимы между собой.
2) Сравнения по одному и тому же модулю можно почленно складывать, 3) Сравнения по одному и тому же модулю можно почленно перемножать. Правила сокращения несколько отличаются от правил сокрашения равенств. 4) Если аи=— ао(гпой т) и =— о(гпой т). аи — = ао(шабат), и (а, т)=1, то 5) Если и = — о(пюй т). Пусть 1(х) — многочлен с целыми коэффициентами.
Сравнение г' (х) = О (шой т) а, 2а, За,...,та (б) не сравнимы между собой по модулю т. Следовательно, все эти числа лежат в разных классах вычетов по модулю т. Ввиду того что имеется ровно т различных классов вычетов по модулю т, получаем, что одно из чисел (6) содержится в классе вычетов, содержащем Ь. Значит, сравнение разрешимо.
Если аг=— Ь(шойт), то, очевидно, все числа из класса вычетов, содержащего г, удовлетворяют сравнению (5) (свойства 3) и 1)), и любое решение лежит в классе вычетов, содержашем г (свойства 1) и 4)). Лемма доказана. Для каждого т, т ) 1, обозначаем через ~р(т) количество чисел совокупности О, 1,...,т — 1, (у) взаимно простых с т. называют сравнением с неизвестной величиной, Если число хо е- :Х таково, что ~ (хо) — = 0 (той т ), то говорят, что хь удовлетворяет рассматриваемому сравнению. Задача о решении сравнения с неизвестной величиной состоит н отыскании всех значений х, которые ему удовлетворяют. Рассмотрим простейшее линейное сравнение: ах=— Ь(шой1 т), (а, т) =1.
(5) Л е м м а 1. Сравнение (5) разрешимо. Множество удовле- творяющих ему чисел составляет некоторый класс вычетов по модулю т. Доказательство. Из свойства сравнений 4) следует, что числа П р и м е р ы: «р (1) = 1, «р (2) = 1, «р (3) = 2, «р (4) = 2, «р (5) = = 4, «р(6) = 2; если р — простое, то «р(р) = р — 1.
Существует ровно «р(т) различных арифметических прогрессий (1) с условием (1, т) = 1, 0 ~1< т. Функция ф(т) называется Функцией Эйлера. Т е о р е м а Э й л е р а. Если а ен У, (а, т) = 1, то ао(оо = 1(шо(1 т), Доказательство. Пусть гь го,...,пп где е = «р(т) — все числа из совокупности (7), взаимно простые с т. Пусть г — одно из чисел ги Тогда произведение аг можно представить в виде аг= дт+ го, 0 (го <т. Если г, и т имеют общий простой делитель р, то р ~ аг.
Но это невозможно, так как (и, гп) = 1 и (г, т) = 1. Следователь но, (г,, т) = 1 и число го содержится среди г(,, г,. Таким обра. зом для каждого индекса «, 1 ( ! ( с, аг; = г,(о(пюдт) (8) Если а(у) = а(!), то аг; =— аг;(гпод гп) или т / а(г,— г(), Поскольку (а, т) = 1, то по лемме 3 гл, 1' т / (г,— г!), что невозможно, так как 1 ~ ~г,— г(~ < т. Итак.. набор чисел (а(1), а(2), ..., а(с)) есть некоторая перестановка чисел (1, 2, ..., с) и г! ' го ' - го = ! а(О - ' га(е) (9) Перемножив теперь сравнения (8), получим а' г! ... г,= г«- .... г,(гпо«)т) и так как (г,....
г„,т) =1, то по свойству 4) сравнений а' = 1(!пой т). Теорема доказана. Следствие 1 (малая теорема Ферма). Если р— простое чис.«о, и р 4 а, го ао-! = 1(шо() р) . Утверждение очевидно, так как ф(р) = р — 1. Локажем теперь утверждение б), которое использовалось- выше. Пусть р — нечетный простой делитель числа а'+ Ьо. Тогда: а'= — — Ь'(гпо() р).
(10) Если. р делит а, то нз условия следует, что р делит Ь, Но это противоречит равенству (а, Ь) = 1. Итак, (а, р) =! и, аналогично, (Ь, р) = 1. Возведем обе части сравнения (10) в степень — и вее- р — 1 2 т!ользуемся малой теоремой Ферма. Получим р — ! 1= — ( — 1) ' (гпо!1 р) р — ! Так как р > 3 и !1 — ( — 1) '-'! <2, то из последнего сравнения находим р — ! 'Зто равенство означает, что с некоторым целым п имеем р — ! — = 2п или р = 4п + 1.
2 Рассмотрим фактор-кольцо Х/гпХ кольца целых чисел Х по идеалу тХ, состоящему нз чисел, кратных и!, элементами которого являются классы вычетов по модулю т. Из леммы 1 следует, что классы вычетов, состоящие из чисел, взаимно простых с !и, являются обратимыми элементами этого кольца. И каждый класс вычетов, обратимый в кольце Х/гпУ, как легко .видеть, состоит из чисел, взаимно простых с т. Таким образом, в кольце У/тХ имеется в точности 4 (пт) обратимых элементов, и мультиплнкативная группа (Х/гпХ)" обратимых элементов кольца Х/тЕ состоит из !(!(и!) элементов. Так как по теореме .Лагранжа порядок каждого элемента группы делит порядок группы, т.
е. !р(т), то получаем еще одно доказательство теоремы Эйлера. $2. Другое доказательство бесконечности множества простых чисел в прогрессиях вида 4п-!-1 В этом параграфе на простейших примерах прогрессий вида 4п ~ 1 будет показана основная идея доказательства теоремы о бесконечности множества простых чисел в арифметической прогрессии. Соответствующее обобщение этой идеи позволит в конце главы изложить доказательство теоремы Дирихле в об.
зцем случае. Рассмотрим два ряда, члены которых являются функциями действительной перемсннои ж й (з) =- 1 + — .;- — + ... —..-. ~' 3* ' 5~ ''' 24 (2а+1)'' о=! откуда получаем, что 1и Е, (з) = — Т~ (п 1 1 — '(Р ), !пав,2(з) = — ~~)~~ 1п (1 — ~' ). р Пользуясь разложением в ряд Тейлора функции — 1п(1 — 1) — 1п(1 — 1)=- Š— ", ~г~(1, находим прн з > 1 для 1 = О, 1 1 г,, ( ) =-- '~~ Ч ("")" = 'Р х"" + 'Г Ч ("("', (1З) /г.рм Йа1 р' ' л ю ам' а.рм р ргн Р р 2=2 Оценим сверху двойную сумму в правой части полученного равенства. Так как ~т;(р) ) ~1, то при 2>1 2=2 2 2 2=2 Тогда, пользуясь неравенством „")', — '„<~ — ',, л 2 л=2,' получаем оценку Таким образом, при з- 1+ О двойная сумма в правой части равенства (13) остается ограниченной.
Поэтому при 2-2.1+0 1п(.,(.) = 'Р— "'" + О(1), = О,1. лл Р' Из этих равенств имеем Š— ""' = х'(р) = 1п Ц (з) + О (1), Ю = О, 1 . (14) Р' Пользуясь теперь определением тг(р) и абсолютной сходимостью рядов в левой части равенств (14) при з > 1, находим, что — = 1п1.о(з) + 0(1), Р р=.1(4под 2) ю-)-'' — — в'. — =!пЕ,)(з)+0(1).
д'д и' (15) (16) Р Р=З(град 4) Р р=1(п4од 4) Равенство (15) можно представить аналогично равенству (!6) в виде — + ~~~ — = 1п7.о(з) + 0(1). (!7) Р Р р.= 1(п4ад О Р.-.З(п4од 4) Из равенств (16) и (17) следует, что Š— =-. — (1 4 о(з) рп 1Па,1(з)) + 0(1), Р Р р -1(4пад 4) Х вЂ” '=- — ' — — (1п7,о(з) — 1п1,1(з)) + О(1). р' 2 (18) Р р- З(вад 4) Поскольку функция й((з) непрерывна в точке з = 1 и, как 2 доказано выше 7.1(1) ) — ) О, то функция !п й((з) ограничена в окрестности точки з = 1.
Но функция Ео(з) стремится к бесконечности при з — 4-1 + О (см. (11)). Поэтому из равенств (18) находим, что 1пп ~ — =-,оо, и 1+0 Р р 1(пп4д 4) 1пп ~ =+со, ) 4-~!+О рп р- З(п4ад 4) 3» Последние равенства означают, что в каждой из прогрессий 4п + 1, Ап + 3, и = О, 1, 2, ..., содержится бесконечное множество простых чисел. Подобные рассуждения были проведены Дирихле в общем случае для любой арифметической прогрессии вида (1) Для этого потребовалось построить ())(лз) (это число различных арифметических прогрессий вида (1) с условием (т, !) = 1, О < ! < т) различных мультипликативных и периодических с периодом т функций )((и) (они называются характерами) и соответствующих им й(з, !()-функций (они носят название 7.-функций Дирихле).
Как ни странно на первый взгляд, но наибольшие трудности в этом обобщении пришлось преодолеть, доказывая утверждение (19) 1.(1, х) ~0 для характеров х(п), не равных тождественно 1 на всех числах и, взаимно простых с и (неглавных характеров). В настоящее время наиболее короткий путь доказательства утверждений (19) связан с определением Е(з, х) рядами, подобными рядам (12), для комплексного з и исследованием аналитических свойств функций Е(з, х) комплексного переменного з. $3. Характеры Пусть 6 — конечная абелсва группа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
