Функция Эйлера: онлайн-калькулятор и свойства

В теории чисел и дискретной математике функция Эйлера, обозначаемая греческой буквой $\varphi(n)$ (читается как «фи от эн»), играет одну из главных ролей. Она определяет количество натуральных чисел, которые меньше заданного числа $n$ и при этом являются взаимно простыми с ним.

Наш бесплатный онлайн-калькулятор поможет вам мгновенно найти значение функции Эйлера для любого числа вплоть до одного триллиона. Инструмент не просто выдаст ответ, но и покажет весь ход решения: от разложения на простые множители до применения главной формулы. А для небольших чисел вы даже увидите полный список этих взаимно простых чисел!

Что такое взаимно простые числа?

Два числа называются взаимно простыми, если их Наибольший Общий Делитель (НОД) равен единице. Простыми словами, у них нет общих делителей, кроме цифры $1$.

Пример: Давайте найдем $\varphi(12)$. Выпишем все числа от 1 до 12: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Какие из них не имеют общих делителей с числом 12 (которое делится на 2, 3, 4, 6)? Это числа: 1, 5, 7, 11. Их ровно четыре штуки. Значит, $\varphi(12) = 4$.

Для маленьких чисел этот способ перебора работает отлично. Но как найти $\varphi(360)$ или $\varphi(10000)$? Считать вручную будет слишком долго. Для этого существуют специальные математические формулы.

Формулы для вычисления $\varphi(n)$

1. Для простого числа ($p$)

Если число $n$ является простым (то есть делится только на 1 и на само себя), то абсолютно все числа, которые меньше его, будут взаимно простыми с ним.

$$\varphi(p) = p — 1$$

Например: $\varphi(7) = 7 — 1 = 6$. (Это числа 1, 2, 3, 4, 5, 6).

2. Для степени простого числа ($p^k$)

Если число является степенью простого числа, то применяется следующая формула:

$$\varphi(p^k) = p^k — p^{k-1} = p^k \left( 1 — \frac{1}{p} \right)$$

Например: $\varphi(8) = \varphi(2^3) = 2^3 — 2^2 = 8 — 4 = 4$.

3. Главная формула (Произведение Эйлера)

Это универсальная формула, которую использует наш онлайн-калькулятор. Чтобы найти $\varphi(n)$ для любого составного числа, его нужно сначала разложить на уникальные простые множители: $n = p_1^{a_1} \cdot p_2^{a_2} \dots p_k^{a_k}$.

Затем применяется формула произведения:

$$\varphi(n) = n \cdot \left( 1 — \frac{1}{p_1} \right) \cdot \left( 1 — \frac{1}{p_2} \right) \dots \left( 1 — \frac{1}{p_k} \right)$$

Пошаговый пример расчета для $\varphi(36)$:

1. Разложим 36 на множители: $36 = 2^2 \cdot 3^2$.
2. Уникальные простые делители — это $2$ и $3$.
3. Подставляем в формулу: $\varphi(36) = 36 \cdot \left( 1 — \frac{1}{2} \right) \cdot \left( 1 — \frac{1}{3} \right)$ $\varphi(36) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 36 \cdot \frac{2}{6} = 12$.

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

Одним из важнейших свойств этой функции является мультипликативность. Если два числа $a$ и $b$ взаимно просты (то есть $\text{НОД}(a,b) = 1$), то:

$$\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$$

Именно это свойство позволяет легко разбивать большие числа на блоки и считать значение по частям.

Зачем нужна функция Эйлера? (Теорема Эйлера и Криптография)

Возможно, вы задаетесь вопросом: «Зачем вообще нужно знать количество взаимно простых чисел?»

Ответ кроется в Теореме Эйлера, которая гласит, что если $a$ и $n$ взаимно просты, то: $a^{\varphi(n)} \equiv 1 \pmod n$

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

Без функции $\varphi(n)$ современная цифровая безопасность была бы невозможна!