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

Функция Эйлера (или функция φ (фи) Эйлера) — это важная арифметическая функция в теории чисел. Она определяет количество положительных целых чисел, меньших данного числа 𝑛 n, которые взаимно просты с 𝑛 n. Формально, функция Эйлера 𝜙 ( 𝑛 ) ϕ(n) определена как количество целых чисел от 1 до 𝑛 − 1 n−1, которые являются взаимно простыми с 𝑛 n. Формула Если 𝑛 n имеет разложение на простые множители: 𝑛 = 𝑝 1 𝑘 1 ⋅ 𝑝 2 𝑘 2 ⋯ 𝑝 𝑚 𝑘 𝑚 n=p 1 k 1 ⋅p 2 k 2 ⋯p m k m где 𝑝 1 , 𝑝 2 , … , 𝑝 𝑚 p 1 ,p 2 ,…,p m — простые числа, то функция Эйлера вычисляется по формуле: 𝜙 ( 𝑛 ) = 𝑛 ( 1 − 1 𝑝 1 ) ( 1 − 1 𝑝 2 ) ⋯ ( 1 − 1 𝑝 𝑚 ) ϕ(n)=n(1− p 1 1 )(1− p 2 1 )⋯(1− p m 1 )