3. Функция Эйлера. Еще раз о теореме Ферма.
Говорят, что два целых числа а и
взаимно простые, если их общий наибольший делитель равен 1:
Например, числа 24 и 35 — взаимно простые, но числа 12 и 18 — не взаимно простые.
Если а и
взаимно простые, то можно подобрать такие целые числа к и I, что
Это следует из свойства
, отмеченного на стр. 75.
Упражнение. Докажите теорему: если произведение
делится на
причем
и а — взаимно простые, то
делится на
(Указание. Если
и а — взаимно простые, то можно найти такие целые числа к и I, что
Затем умножьте обе части равенства на
Эта теорема обобщает лемму на стр. 76, так как простое число
в том и только в том случае является взаимно простым с а, если а не делится на
Пусть
произвольное целое положительное число; обозначим через
число таких целых чисел в пределах от 1 до
которые являются взаимно простыми с числом
Выражение
впервые введенное Эйлером, представляет собой очень важную теоретико-числовую функцию. Легко подсчитать значения
для нескольких первых значений
Заметим, что
если
простое число; в самом деле, у числа
нет делителей, кроме
и потому все числа
являются взаимно простыми с
Если
составное, причем его разложение на простые множители имеет вид
где числа
обозначают различные простые множители, причем каждое из них возводится в некоторую степень, то тогда
Например, из разложения
следует
что легко проверить и непосредственно. Доказательство приведенной теоремы совершенно элементарно, но мы его не приводим.