Калькулятор функции Эйлера φ(n)

Калькулятор функции Эйлера φ(n)

Растущий AI Skill PRO

Введите расчет

Математическая формула

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
Статистика использования

Реклама

Результаты

Функция Эйлера φ(32)
16
целых чисел, взаимно простых с 32 in [1, n]
Число n 32
Различные простые множители 2

Сообщить об ошибке на этой странице

Что такое функция Эйлера?

Функция Эйлера, которую обозначают \(\varphi(n)\), показывает, сколько натуральных чисел в диапазоне от 1 до n не имеют с n общих делителей, кроме единицы, — то есть являются взаимно простыми с n. Например, \(\varphi(9) = 6\), потому что числа 1, 2, 4, 5, 7 и 8 взаимно просты с девяткой. Эта функция — одно из ключевых понятий теории чисел, и она широко применяется в криптографии. Самый известный пример — алгоритм RSA, где значение \(\varphi(n)\) определяет обратный элемент по модулю, используемый при генерации ключей.

Сетка целых чисел от 1 до 12 с выделенными взаимно простыми с 12
Функция Эйлера считает целые числа до n, не имеющие общих делителей с n.

Как пользоваться калькулятором

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

Разбираем формулу

Самый эффективный способ вычислить функцию Эйлера — формула произведения:

$$\varphi\!\left(n\right) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$, где произведение берётся по всем различным простым числам p, на которые делится n.

Важны именно различные простые множители, а не их кратности. Каждый сомножитель \(\left(1 - \frac{1}{p}\right)\) «отсекает» долю чисел, которые делятся на это простое число.

Реклама
Схема: n раскладывается на простые множители и умножается на члены (1 минус 1 на p)
Формула произведения умножает n на множитель \(\left(1 - \frac{1}{p}\right)\) для каждого различного простого делителя p.

Пример с решением

Возьмём n = 36. Его разложение на простые множители — \(2^2 \times 3^2\), то есть различные простые числа здесь 2 и 3. Тогда:

$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}.$$

Значит, ровно 12 целых чисел от 1 до 36 взаимно просты с 36.

Частые вопросы

Чему равно \(\varphi(1)\)? По соглашению \(\varphi(1) = 1\), поскольку единица взаимно проста сама с собой.

Чему равно φ от простого числа p? Для любого простого p выполняется \(\varphi(p) = p - 1\), ведь каждое число от 1 до p−1 взаимно просто с p.

Мультипликативна ли функция Эйлера? Да. Если \(\gcd(a, b) = 1\), то \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\). Именно поэтому и работает формула произведения по различным простым множителям.

Реклама

Ещё примеры вычислений

Пример 1: простое число, φ(13)

13 — простое число, поэтому его единственный простой делитель — это само 13:

\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Это совпадает с простым правилом \(\varphi(p) = p-1\).

Пример 2: степень простого числа, φ(32)

Разложение: \(32 = 2^5\). Единственное различное простое число здесь — 2.

\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.

Эквивалентная форма для степени простого числа: \(\varphi(p^k) = p^k - p^{k-1}\), поэтому \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Это в точности нечётные числа от 1 до 31.

Пример 3: три или более различных простых числа, φ(210)

Разложение: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).

  1. Начинаем с \(210\).
  2. Умножаем на \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
  3. Умножаем на \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
  4. Умножаем на \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
  5. Умножаем на \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).

Итак, \(\varphi(210) = \)48. Обратите внимание, что правило произведения использует каждое различное простое число только один раз. Например, \(60 = 2^2 \cdot 3 \cdot 5\) даёт \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).

Интерпретация φ(n) и её применения

  • Связь с простотой: для \(n \ge 2\) равенство \(\varphi(n) = n-1\) выполняется тогда и только тогда, когда \(n\) простое. Каждое число, меньшее простого, взаимно просто с ним. Если \(n\) составное, хотя бы одно меньшее число имеет с ним общий делитель, поэтому \(\varphi(n) < n-1\).
  • Группа обратимых элементов: \(\varphi(n)\) — это количество элементов в группе обратимых элементов по модулю \(n\), то есть вычетов, имеющих мультипликативный обратный по модулю \(n\). Для \(n = 15\) это 1, 2, 4, 7, 8, 11, 13, 14, что даёт 8 элементов.
  • Теорема Эйлера: если \(\gcd(a, n) = 1\), то \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Пример: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, и \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Малая теорема Ферма — частный случай при \(n = p\), где \(p\) простое.
  • RSA: если \(n = pq\) для различных простых \(p\) и \(q\), то \(\varphi(n) = (p-1)(q-1)\). При \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). Открытый показатель \(e\) должен быть взаимно прост с \(\varphi(n)\), а закрытый показатель \(d\) удовлетворяет \(ed \equiv 1 \pmod{\varphi(n)}\). В настоящем RSA используются простые числа длиной в сотни цифр. Тот, кто может разложить \(n\) на множители, может вычислить \(\varphi(n)\), поэтому безопасность опирается на то, что факторизация трудна.
  • Отношение зависит только от различных простых делителей: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Показатели степеней не важны. Например, у 6 и 12 одно и то же множество простых делителей {2, 3}, поэтому \(\varphi(6)/6 = 2/6 = 1/3\) и \(\varphi(12)/12 = 4/12 = 1/3\).
Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика