Функция Эйлера. Вывод явной формулы для функции Эйлера. Теоремы Эйлера и Ферма

§ 4. Функция Эйлера

Рассмотрим некоторые свойства функции Эйлера.

1. Если р - простое, то р -1.

Доказательство.

1,2,3,…, p-1- числа, не превосходящие р и взаимно простые с p. Значит, по определению функции Эйлера, р -1.

2.

Доказательство.

Идея: от общего количества натуральных чисел, не превосходящих отнимем количество целых чисел, не взаимно простых с p. Числа, не взаимно простые с p, имеют вид kp, причем p Следовательно, количество таких чисел ровно , но тогда количество чисел, взаимно простых с будет равно

Определение. Функция f(n), определенная на множество натуральных чисел, называется мультипликативной, если для любых взаимно простых натуральных чисел aи b

F(a

3. Функция Эйлера мультипликативна, т.е. если (a,b)=1, .

доказатальство. Натуральные числа от 1 до ab расположим в виде таблицы:

1 2 … r … b

b+1 b+2 … b+r … 2b

2b+1 2b+2 … 2b+r … 3b

……………………………………………………………

(a-1)b+1 (a-1)b+2 … (a-1)b+r … ab

В таблице выписаны все натуральные числа, не превосходящие ab. Следовательно, согласно определению функции Эйлера, в таблице чисел, взаимно простых с ab,будет (чисел, не превосходящих ab, и взаимно простых с ab).

Подсчитаем это же число другим способом.

Заметим, что первая строка таблицы есть набор натуральных чисел, не превосходящих b, а значит среди них чисел,взаимно простых с b.Но если число rвзаимнo просто с b,то и все числа r-го столбца взаимно просты с b.Все числа r-го столбца сравнимы меду собой по модулю b,а сравнимые числа имеют одинаковый НОД с модулем b. Следовательно, в таблице столбцов чисел, взаимно простых с b. Пусть r-ый один из таких столбцов. Он представляет собой полную систему вычетов по модулю a (систему чисел вида bx+r, где х пробегает полную систему вычетов по модулю a: 0,1,2, …, a-1). Но тогда в этом столбце чисел,взаимно простых с а. Если число взаимно просто с b и с а, то оно взаимно просто с ab. Итак, в таблице столбцов чисел, взаимно простых с b, каждый такой столбец содержит чисел, взаимно простых с а. Значит в таблице чисел, взаимно простых как с а, так и с b, т. е. взаимно простых и с ab. Следовательно, =

4. Пусть n= – каноническое раз ложение натурального числа, тогда

Доказательство.

Т.к. функция Эйлера мультипликативная, то получаем:

Пример. N=12, 12=