Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 80
Текст из файла (страница 80)
Пусть число а — взаимно простое с т и пусть а < т. Рассмотрим последовательность а, а+ т,а+ 2т,..., а+ (и — 1)т. Никакие два из этих чисел не сравнимы по модулю и, поскольку, если а+ йт ь— з а+ Йт (шоц и), то и ~ (1т — йт). Отсюда и (т(~ — lс). Поскольку числа т и и — взаимно простые, то и ! (1 — й), что невозможно. Следовательно, рассматриваемая последовательность представляет собой полную систему вычетов по модулю и, и каждый элемент данной последовательности сравним по модулю и с целым положительным числом, меньшим и. Следовательно, количество этих элементов, взаимно простых с и, равно ф(п).
Поскольку существуют ф(т) таких последовательностей, то существует ф(т)ф(п) чисел, взаимно простых одновременно и с ги, и с и, которые меньше тп и взаимно простые с тип. Поэтому ф(тп) = ф(т)ф(п). ° Например, пусть ги = 8 и и = 15. Тогда ф(8) = 4, поскольку только 1, 3, 5 и 7 — положительные целые числа, которые меньше 8 и взаимно простые с 8.
Также ф(15) = 8, поскольку только 1, 2, 4, 7, 8, 11, 13 и 14 — положительные целые числа, которые меньше 15 и взаимно простые с 15. Следовательно, ф(120) = ф(8)ф(15) = 32, что можно проверить непосредственно. В соответствии с утверждением теоремы 10.19 говорят, что ф — мультипликативна относительно взаимно простых множителей. В следующей главе рассматриваются другие мультипликативные функции. Теперь покажем, как вычислять ф(п), когда и представляет собой степень единственного простого числа.
ТЕОРЕМА 10.20. Если р — простое число, то ф(р") = р" — р~ ДОКАЗАТЕЛЬСТВО. Числа, не превышающие рь и не являющиеся взаимно простыми с р", имеют вид р 2р Зр,...,(р" з)р. Поскольку имеются р" 1 таких целых чисел, то существует р" — р" ' целых чисел, взаимно простых с рь. Следовательно, ф(р") = р" — р" СЛЕДСТВИЕ 10.21. Целое положительное число р является простым тогда и только тогда, когда ф(р) = р — 1.
ДОКАЗАТЕЛЬСТВО. Если р — простое число, то из теоремы 10.20 непосредственно следует, что ф(р) = р — 1. С другой стороны, если число р не является простым, у него есть делитель Ы, отличный от р и от 1. Поскольку, по определению, ф(р) < р — 1 и Н являются одним из р — 1 положительных целых чисел, меньших р, имеем ф(р) < р — 2, что составляет противоречие. СЛЕДСТВИЕ 10.22. ф(2") = 2" 436 ГЛАВА Ю. Некоторые специальные вопросы теории чисел На основе свойства мультипликативности ф(тп) = ф(т)ф(п) для взаимно простых чисел т и и в сочетании с соотношением ф(рь) = р" — р" ' можно для любого целого положительного числа п получить явное выражение для ф(п), используя разложение и на простые множители.
Эта формула приведена в следующей теореме, доказательство которой предоставляется читателю в качестве упражнения. ТЕОРЕМА 10.23. Если и — целое положительное число с разложением на простые множители вида то ПРИМЕР 10.24. Поскольку и = 40 = 2 5, ф(40) = 40(1 — 1/2И1 — 1/5) = 40(1/2)(4/5) = 16, что совпадает со значением, полученным в одном из примеров в начале этого раздела. Кроме этого, в главе 3 показано, что п = 39616304 = 2~ 7з 13з 23~, поэтому ф(39616304) 2з(2 1)7~(7 1)13з(13 1)23о(23 1) = 8 1 7 . 6 .
169 . 12 . 1 22 = 14990976. Существуют ограничения, касающиеся количества целых чисел з, 1 < з < и, взаимно простых с и. Одну из таких ограничивающих связей устанавливает следующая теорема. ТЕОРЕМА 10.25. Если целое число п больше 2, то ф(п) — четное. ДОКАЗАТЕЛЬСТВО. Если п = 2"гп, где т — целое нечетное число и к ) 1, то ф(2"т) = ф(2")ф(т) = 2" 'ф(т) и, следовательно, ф(п) — четное. Если п = р гп, где р — нечетное простое число и числа р и т — взаимно простые, тогда ь ь ф(р"т) = ф(р")ф(тп) = (р" — р" г)ф(т). Но р" — р" г = р" ~(р — 1) и р — 1— четное число, поскольку р — нечетное. Следовательно, ф(п) — четное.
Приведенный ниже результат нами уже упоминался, но здесь он излагается формально. ТЕОРЕМА 10.26. Если и — целое число, тогда ненулевой класс приведенных вычетов образует группу относительно умножения по модулю и. ДОКАЗАТЕЛЬСТВО. Если числа а и Ь вЂ” взаимно простые с и, то, очевидно, число аЬ вЂ” также взаимно простое с и, поэтому наш класс вычетов замкнут относительно умножения. Если число а — взаимно простое с и, то сравнение ах =— 1 (шой п) имеет единственное решение, и, следовательно, существует величина, обратная к а. РАЗДЕЛ 10.4.
Свойства функции 437 Пусть число р — простое. Поскольку (1, 2,...,р — 1) — множество приведенных вычетов по модулю р, то [Ц, [2],..., [Р— Ц образуют, как это было показано в разделе 3.6, группу относительно умножения. Следующая теорема показывает, что произведение [Ц О [2) О О [Р— Ц всех ненулевых классов вычетов всегда является классом вычетов [Р— Ц = [ — Ц. На языке сравнимости это эквивалентно утверждению, что 1 2 (р — 1) = — 1 (гной р). ТЕОРЕМА 10.27. (Уилсон) Целое положительное число Р является простым тогда и только тогда, когда (р — 1)!: — — 1 (гаос1 р). ДОКАЗАТЕЛЬСТВО.
Если число р — простое, то р = О (пюй р) и р — 1 = — 1 (гной р). Когда р — простое, ненулевой класс вычетов по модулю р образует группу относительно умножения, так что каждый класс вычетов является спаренным со своим обращением и дает в произведении [Ц. Таким образом, если 1 < и < р — 1, то существует единственное целое число и ', 1 < и ' < р — 1 такое, что и и '— : 1 (той р).
Имеем и = и или и ~ и . Очевидно, что для и = 1 имеем и ' = 1, а также из = ии ' = 1 (той р). Если существует целое число а, 1 < а < р — 1 такое, что а~ = 1 (пюй р), то аз — 1 = (а — 1)(а+ 1) = О (пюй р) и р [ (а — 1)(а + 1). Таким образом, р ( (а — 1) или Р ( (а + 1).
Поскольку а — 1 эЕ О и а < р, получаем, что р ) (а — 1). Таким образом, р ] (а+ 1), откуда Р < а+ 1; и поскольку а < р — 1, это имеет следствием а+ 1 < р. Получаем, что р = а+ 1 или а = р — 1. Таким образом, для 1 < и < р — 1 только и = 1 и и = р — 1 обладают таким свойством, что из = 1 (гной р). Итак, получаем (Р 1). = 1(и1иг )(изиз ) ' ' '(иьин )(Р 1) = 1' 1'1 ' '' '1' (Р 1) = Р (пюй р), где и — одно из целых чисел 2, 3, ..., (р — 2), и к = (Р— 3)/2. Если число р не является простым, то р = т .
з, где 1 < т, в < р. Поскольку (Р— 1)! делится на т, то (р — 1)! = О (гной т), так что (Р— 1)! 7~ — 1 (твой т). Поэтому р должно быть простым. Например, пусть р = 5. Тогда (р — 1)! = 4! = 24 = — 1 (пюй 5). Заметим, что в теореме говорится о том, что произведение (р — 1)! не может быть сравнимо с — 1, если число р не является простым. Посредством теоремы можно проверять простоту числа р, устанавливая, справедливо ли сравнение (Р— 1)! = — 1 (пюй р). Однако, такой критерий не используется для больших значений р, т.к. вычисление (Р— 1)! (гной р) практически нецелесообразно. Теперь рассмотрим теорему Уилсона с алгебраической точки зрения.
Уже известно, что Яр — ([О)) образует группу относительно умножения. Поэтому каждый ненулевой элемент из кр имеет мультипликативную инверсию — обратный элемент относительно умножения. Доказательство приведенной выше теоремы Уилсона показывает, что только [Ц и [Р— Ц совпадают со своими обратными элементами.
Следовательно, в произведении (Ц[2][3) .[Р— Ц каждый элемент является спаренным со своим обратным элементом, так что (Ц[2][3) .[Р— Ц = [Ц[Р— Ц = [Р— Ц или, что то же самое, 1 2 3 . (Р— 1) : — р — 1 (пюй р) = -1 (пюй р). Легко показать, что в циклической группе четного порядка существуют только два элемента, которые совпадают со своими обратными элементами.
Этими элементами в данном случае являются [Ц и [Р— Ц. 438 ГПАВА 10. Некоторые специальные вопросы теории чисел Рассматриваемая нами функция ф названа в честь Леонарда Эйлера, перу которого принадлежит наибольшее количество математических трудов. Многие из доказанных им теорем встречаются на страницах этой книги. Творческое наследие Эйлера могло бы составить более 75 объемных томов. Ему принадлежат открытия практически во всех областях математики.
Только в теории чисел ему принадлежит более 140 оригинальных работ, включая доказательства целого ряда малых теорем Ферма. Он считается основоположником топологии, а также целых разделов математического анализа. Престижную премию Парижской Академии наук, присуждаемую раз в два года, Эйлер получал 12 раз. Многие из ныне существуюших систем математических обозначений введены Эйлером. Леонард Эйлер ((.еопагд Ец!ег, 1707-1783) был сыном лютеранского священника в Швейцарии.
Его отец был его первым учителем. Он хотел, чтобы сын также пошел в духовенство, но Эйлеру посчастливилось стать учеником Иоганна Бернулли (йеап Вегпоц!11), одного из лучших европейских математиков того времени. Не найдя в Швейцарии условий для научной деятельности, он вместе с другими европейскими математиками уехал работать в Россию, где незадолго до этого была основана Санкт-Петербургская Академия наук. Во время пребывания в России он ослеп на один глаз. Вскоре после прибытия Эйлера в Россию в стране начались политические репрессии, и после 14 лет жизни в России он уехал в Германию, чтобы возглавить математический отдел Берлинской Академии наук.
По-видимому, в этот период жизни в Германии на вопрос королевы-матери о том, почему он такой неразговорчивый, Эйлер ответил, что только что приехал из страны, где вешают всякого, кто разговаривает. Тем не менее, Эйлер оставался весьма уважаемым в России. Когда в 1760 году началась война между Россией и Германией, дом, где жил Эйлер, был разрушен, и когда об этом узнали в России, материальный ушерб был моментально возмешен, а императрица сделала ему подарок. После 25 лет пребывания в Германии, по причине разногласий с королем Фридрихом 11, Эйлер вернулся в Россию, приняв великодушное приглашение Екатерины 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
