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

Функция Эйлера \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}.

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

Один ответ к “Функция Эйлера онлайн”

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

одиннадцать + шестнадцать =