Изучаем математику вместе!

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

Функция Эйлера $\varphi(m)$ — функция, равная количеству чисел ряда $0,\ldots, m-1$ , взаимно простых с $m$ . Заметим, что из определения $\varphi(1)=1$ .

Пояснение: взаимно простыми называются числа, которые не имеют общих делителей, отличных от 1. Так как делителями нуля являются все натуральные числа, то 0 взаимно прост только с 1.

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

Представим число $a$ в виде

$a = p_{1}^{\alpha _1} p_{2}^{\alpha _2}\ldots p_{k}^{\alpha _k},$

где числа $p_1, p_2,\ldots, p_k$ простые и попарно различные. Тогда

$\varphi(a)=a\prod_{i=1}^{k} \left(1-\frac{1}{p_i}\right)=(p_{1}^{\alpha _1}-p_{1}^{\alpha _1-1})\ldots (p_{k}^{\alpha _k}-p_{k}^{\alpha _k-1}).$

Мультипликативность функции Эйлера

Для взаимно простых чисел $a$ и $b$ справедливо

$\varphi(ab)=\varphi(a)\varphi(b).$

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

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

Программа вычисляет функцию Эйлера онлайн для любого числа, меньшего $9\cdot 10^{15}$ .

См. также: разложение числа на простые множители.

Добавить комментарий Отменить ответ