Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

3. Функция Эйлера φ(n). Еще раз о теореме Ферма

Говорят, что два целых числа а и b - взаимно простые, если их общий наибольший делитель равен 1:

(а, b) = 1.

Например, числа 24 и 35 взаимно простые, но числа 12 и 18 не взаимно простые.

Если а и b - взаимно простые, то можно подобрать такие целые числа k и l, что

ka + lb = 1.

Это следует из свойства (а, b), отмеченного на стр. 70.

Упражнение. Докажите теорему: если произведение ab делится на r, причем r и а - взаимно простые, то b делится на r. (Указание. Если r и а - взаимно простые, то можно найти такие целые числа k и l, что

kr + la = 1.

Затем умножьте обе части равенства на b.) Эта теорема обобщает лемму со стр. 71, так как простое число р в том и только в том случае является взаимно простым с а, если а не делится на р.

Пусть n - произвольное целое положительное число; обозначим через φ(n) число таких целых чисел в пределах от 1 до n, которые являются взаимно простыми с числом n. Выражение φ (n), впервые введенное Эйлером, представляет собой очень важную теоретико-числовую функцию. Легко подсчитать значения φ (n) для нескольких первых значений n:


и т. д.

Заметим, что φ (р) = р - 1, если р - простое число; в самом деле, у числа р нет делителей, кроме 1 и р, и потому все числа 1,2,..., р-1 являются взаимно простыми с р. Если n - составное, причем его разложение на простые множители имеет вид

n = p1α1p2α2...prαr

где числа р обозначают различные простые множители, причем каждое из них возводится в некоторую степень, то тогда


Например, из разложения 12 = 22*3 следует


что легко проверить непосредственно. Доказательство приведенной теоремы совершенно элементарно, но мы его не приводим.

Упражнение. Пользуясь функцией Эйлера φ(n), обобщить теорему Ферма, приведенную на стр. 61. Обобщенная теорема формулируется следующим образом: если n - целое число и а - взаимно простое с n, то

аφ(n) ≡ 1 (mod n).

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru