Функция Эйлера: Считаем взаимно простые числа

Функция Эйлера, часто обозначаемая как φ (n), — это важная арифметическая функция в теории чисел. Она подсчитывает количество натуральных чисел, не превосходящих n, которые взаимно просты с n. Другими словами, φ(n) показывает, сколько чисел от 1 до n имеют наибольший общий делитель с n равный 1.

Определение

Функция Эйлера φ(n) для положительного целого числа n определяется как количество целых чисел k в диапазоне 1 ≤ k ≤ n, для которых НОД(n, k) = 1.

Простыми словами

φ(n) — это количество чисел от 1 до n, которые «не имеют общих делителей» с n, кроме единицы.

Примеры

φ(1) = 1 (только число 1 взаимно просто с 1)
φ(2) = 1 (только число 1 взаимно просто с 2)
φ(3) = 2 (числа 1 и 2 взаимно просты с 3)
φ(4) = 2 (числа 1 и 3 взаимно просты с 4)
φ(5) = 4 (числа 1, 2, 3 и 4 взаимно просты с 5)
φ(6) = 2 (числа 1 и 5 взаимно просты с 6)

Формула вычисления функции Эйлера

Существует удобная формула для вычисления φ(n), основанная на разложении числа n на простые множители.

Если разложение числа n на простые множители имеет вид:

$n =p_1^{k_1}p_2^{k_2}\cdot ...\cdot p_r^{k_r}$

, где $p_1, p_2, ... , p_r$ — различные простые числа, а $k_1, k_2, …, k_r$ — их соответствующие показатели степеней, то: φ(n) $= n \left(1 - \frac{1}{p_1}\right) \left( 1 - \frac{1}{p_1} \right) … \left( 1 - \frac{1}{p_1} \right)$

Примеры использования формулы

φ(12): $12 = 2^2 \cdot 3$ . Поэтому φ $(12) = 12 \cdot \left( 1 - \frac{1}{2} \right) \cdot \left(1 - \frac{1}{3}\right) = 4$
φ(360): $360 = 2^3 \cdot 3^2 \cdot 5$ . Поэтому φ $(360) = 360 \cdot \left( 1 - \frac{1}{2} \right) \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{5}\right) = 96$

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

φ $(p) = p - 1$ , если $p$ — простое число. Все числа от 1 до $p-1$ взаимно просты с $p$ .
φ $(p^k) = p^{k-1}(p-1)$ , если $p$ — простое число, а $k$ — натуральное число.
Если m и n взаимно просты, то φ $(m \cdot n)$ = φ $(m) \cdot$ φ $(n)$ . Это свойство позволяет упростить вычисление функции Эйлера для больших чисел, если известно их разложение на простые множители.