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

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

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

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

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

Упражнение. Докажите теорему: если произведение делится на причем и а — взаимно простые, то делится на (Указание. Если и а — взаимно простые, то можно найти такие целые числа к и I, что

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

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

Заметим, что если простое число; в самом деле, у числа нет делителей, кроме и потому все числа являются взаимно простыми с Если составное, причем его разложение на простые множители имеет вид

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

Например, из разложения следует

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

Упражнение. Пользуясь функцией Эйлера обобщить теорему ферма, приведенную на стр. 65. Обобщенная теорема формулируется следующим образом: если целое число и а — взаимно простое с то