Теорема

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

Функция Эйлера φ (n), где n – натуральное число, дает количество натуральных чисел, не превышающих n и взаимно простых с n. Иначе говоря, φ (n)= k, где 0< k £ n; (k, n)=1.

, где p_i – все простые делители n. (- произведение по всем простым делителям числа n).

# В теореме Лежандра заменим a_i на p_i, где p_i – простые делители n.

Тогда (так как p_i делят n нацело).

По теореме Лежандра

. #

Пример. Определим, сколько чисел, не превышающих 100, взаимно простые с 100. Разложим число 100 на простые сомножители: 100=2·2·5·5=2²5². Таким образом, у числа 100 два простых делителя – 2 и 5. По формуле Эйлера получаем

.

Таким образом, среди первой сотни есть 40 чисел, взаимно простых с 100.

Дата добавления: 2014-01-05