Свойства. Вычисление функции Эйлера

Вычисление функции Эйлера

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

Тогда функция Эйлера может быть вычислена по формуле

При этом полагается, что

Функцию Эйлера можно также представить в виде так называемого произведения Эйлера:

где — простое число и пробегает все значения, участвующие в разложении на простые сомножители.

Также иногда функцией Эйлера называют функцию от рационального числа :

однако в этой статье о ней речь не идет.

1. , если — простое число. В частности, при имеем ;

2. , если и взаимно просты. То есть Функция Эйлера мультипликативна;

3. , если и взаимно просты. Так называемая теорема Эйлера;

4.

5. , если — наименьшее общее кратное, a — наибольший общий делитель.

33. Теорема Эйлера и ее доказательства, малая теорема Ферма: примеры.

Теоре́ма Э́йлера в теории чисел гласит:

Если и взаимно просты, то , где — функция Эйлера.

Дата добавления: 2015-04-24