Функция Эйлера φ(n)
Вычисление функции Эйлера для теории чисел и криптографии с разложением на простые множители
Калькулятор функции Эйлера φ(n) онлайн с пошаговым решением
Онлайн калькулятор вычисляет функцию Эйлера φ(n) — количество натуральных чисел от 1 до n, взаимно простых с n. Например, φ(12) = 4, потому что с 12 взаимно просты только 1, 5, 7 и 11. Для простого p ответ всегда равен p − 1, для составного — формула считается по разложению на простые множители.
Инструмент показывает результат за доли секунды, выводит каноническое разложение n на простые множители, расписывает формулу φ(n) = n × ∏(1 − 1/p), а для n ≤ 100 ещё и список всех взаимно простых чисел. Подходит студентам, преподавателям, олимпиадникам и тем, кто разбирается с алгоритмом RSA.
- Вычисление φ(n) для любого натурального n от 1 до 5 000 000
- Каноническое разложение n на простые множители
- Пошаговое применение мультипликативной формулы Эйлера
- Список всех взаимно простых чисел с n (для n ≤ 100)
- Проверка простоты числа как побочный результат
- Копирование готового решения для домашней работы или реферата
Что такое функция Эйлера и зачем она нужна
Функция Эйлера φ(n) (другие названия: тотиент, phi-функция, totient function) была введена Леонардом Эйлером в 1763 году. По определению φ(n) — число целых k в диапазоне 1 ≤ k ≤ n таких, что НОД(k, n) = 1, то есть взаимно простых с n.
Сегодня φ(n) — фундамент модулярной арифметики и асимметричной криптографии. Без функции Эйлера невозможен RSA, цифровая подпись, протоколы Диффи–Хеллмана. Она же возникает в задачах подсчёта примитивных корней, порядков элементов в группе (Z/nZ)*, числа несократимых дробей со знаменателем не больше n.
Формула и свойства функции Эйлера
Если каноническое разложение числа n = p₁^a₁ × p₂^a₂ × … × p_k^a_k, то φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/p_k). Эквивалентная запись через степени: φ(p^k) = p^k − p^(k−1) = p^(k−1)(p − 1).
Главные свойства, которые часто спрашивают на экзаменах: φ(1) = 1 (по определению), для простого p φ(p) = p − 1, мультипликативность φ(m × n) = φ(m) × φ(n) при НОД(m, n) = 1, тождество Гаусса ∑φ(d) = n по всем делителям d числа n, теорема Эйлера a^φ(n) ≡ 1 (mod n) при взаимно простых a и n.
- φ(1) = 1, φ(2) = 1, φ(p) = p − 1 для любого простого p
- φ(p^k) = p^(k−1) × (p − 1) для степени простого
- φ(m × n) = φ(m) × φ(n) при НОД(m, n) = 1 — мультипликативность
- Сумма φ(d) по всем делителям n равна n (тождество Гаусса)
- Теорема Эйлера обобщает малую теорему Ферма на составные модули
- φ(n) всегда чётно для n ≥ 3 (это следствие из формулы)
Применение функции Эйлера в криптографии RSA
В RSA выбирают два больших простых числа p и q, считают модуль n = p × q и φ(n) = (p − 1)(q − 1). Открытый ключ e — любое целое, взаимно простое с φ(n) (обычно e = 65537). Закрытый ключ d — мультипликативно обратный к e по модулю φ(n): d = e⁻¹ mod φ(n). Шифрование: c = m^e mod n. Расшифровка: m = c^d mod n — работает благодаря теореме Эйлера.
Безопасность RSA держится на трудности факторизации: зная n, нельзя за разумное время найти p, q и φ(n). Для 2048-битных модулей это NP-сложная задача даже для суперкомпьютеров. Поэтому в учебной задаче с маленькими p, q калькулятор φ(n) показывает всё разложение, а в реальной криптографии — только знание простых даёт φ(n).
Пример из жизни: настройка ключей RSA
Студент-криптограф собирает учебную пару ключей RSA: берёт два простых p = 61 и q = 53. Нужно вычислить φ(n), чтобы выбрать открытый ключ e и найти закрытый d.
Вычислил модуль n = p × q = 61 × 53 = 3233
Через калькулятор посчитал φ(3233) = (61 − 1) × (53 − 1) = 60 × 52 = 3120
Подобрал открытый ключ e = 17 — оно взаимно просто с 3120 (проверил через калькулятор взаимно простых чисел)
Нашёл закрытый ключ d = 17⁻¹ mod 3120 = 2753 (через расширенный алгоритм Евклида)
Пара ключей готова: открытый (e=17, n=3233), закрытый (d=2753, n=3233). Знание φ(n) — обязательный шаг: без него нельзя вычислить d и расшифровать сообщение.
Знаете ли вы?
Леонард Эйлер ввёл φ(n) в 1763 году в работе «Theoremata arithmetica nova methodo demonstrata». Сам символ φ для функции предложил Гаусс почти через 40 лет — в «Disquisitiones Arithmeticae».
Каждый HTTPS-сайт, банковский перевод, цифровая подпись и SSH-ключ работают через RSA или подобные алгоритмы — и значит, через функцию Эйлера. Без φ(n) безопасный интернет был бы невозможен.
Тождество Гаусса: сумма φ(d) по всем делителям числа n равна самому n. Например, для n = 12 делители 1, 2, 3, 4, 6, 12 дают φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = 12.
Найти φ(n) для произвольного n так же сложно, как разложить n на множители. Именно поэтому RSA-2048 безопасен: даже зная n = p × q, без знания p и q вычислить φ(n) — нерешаемая задача.
Числа n, у которых φ(n) = m, называются «полу-числами Тотиента». Например, для m = 8 такие числа: 15, 16, 20, 24, 30. А вот для m = 14 ни одного n не существует — это число называется «нетотиентом».
Среднее значение φ(n)/n для случайного n стремится к 6/π² ≈ 0,6079. Это значит, что в среднем около 60,8% чисел от 1 до n взаимно просты с n. Связь функции Эйлера с числом π — одна из красивейших в математике.
Значения φ(n) для n от 1 до 30
| n | Разложение | φ(n) | Тип числа |
|---|---|---|---|
| 1 | 1 | 1 | единица |
| 2 | 2 | 1 | простое |
| 3 | 3 | 2 | простое |
| 4 | 2² | 2 | квадрат простого |
| 5 | 5 | 4 | простое |
| 6 | 2 × 3 | 2 | свободное от квадратов |
| 7 | 7 | 6 | простое |
| 8 | 2³ | 4 | степень простого |
| 9 | 3² | 6 | квадрат простого |
| 10 | 2 × 5 | 4 | свободное от квадратов |
| 12 | 2² × 3 | 4 | составное |
| 15 | 3 × 5 | 8 | свободное от квадратов |
| 16 | 2⁴ | 8 | степень простого |
| 20 | 2² × 5 | 8 | составное |
| 24 | 2³ × 3 | 8 | составное |
| 25 | 5² | 20 | квадрат простого |
| 30 | 2 × 3 × 5 | 8 | примориал |
| 100 | 2² × 5² | 40 | составное |
| 1000 | 2³ × 5³ | 400 | составное |
Быстрый признак простоты
Если калькулятор показал φ(n) = n − 1 — значит n простое число. Обратное тоже верно: ни для какого составного n равенство φ(n) = n − 1 не выполняется. Это самый простой (хотя и не самый быстрый) тест простоты.
Как пользоваться калькулятором функции Эйлера
Шаг 1. Введите число
Любое целое от 1 до 5 000 000. Можно ввести вручную или выбрать один из готовых примеров: 12, 17 (простое), 36 (квадрат), 100, 65537 (стандартный e в RSA).
Шаг 2. Нажмите «Вычислить φ(n)»
Или клавишу Enter. Калькулятор сразу разложит число на простые множители и применит формулу Эйлера.
Шаг 3. Изучите пошаговое решение
В блоке результата видно разложение n на простые, подстановку в формулу и финальный ответ. Это можно списать в тетрадь или вставить в реферат.
Шаг 4. Посмотрите взаимно простые числа
Для n ≤ 100 калькулятор показывает все k от 1 до n с НОД(k, n) = 1. Для больших n этот список не выводится — он слишком длинный, но количество всегда равно φ(n).
Шаг 5. Скопируйте результат
Кнопка «Копировать» сохранит в буфер обмена и значение φ(n), и разложение, и все шаги решения — удобно для домашних заданий.
Примеры вычисления φ(n)
📚 Школьный пример: φ(24)
24 = 2³ × 3. φ(24) = 24 × (1 − 1/2) × (1 − 1/3) = 24 × 1/2 × 2/3 = 8. Взаимно простые: 1, 5, 7, 11, 13, 17, 19, 23.
🔢 Простое число: φ(97)
97 — простое, поэтому φ(97) = 97 − 1 = 96. Все 96 чисел от 1 до 96 взаимно просты с 97.
📐 Степень простого: φ(64)
64 = 2⁶. φ(64) = 2⁶ − 2⁵ = 64 − 32 = 32. Это все нечётные числа от 1 до 63 — ровно половина.
🔐 Криптография: φ(3233)
p = 61, q = 53, n = 3233. φ(n) = (61 − 1) × (53 − 1) = 60 × 52 = 3120. Дальше выбирают e и считают d = e⁻¹ mod 3120.
🌐 Стандарт RSA: e = 65537
65537 = 2¹⁶ + 1 — простое число Ферма. φ(65537) = 65536. Это значение по умолчанию используется как открытая экспонента e в большинстве реализаций RSA.
🧩 Олимпиадный случай: φ(1000)
1000 = 2³ × 5³. φ(1000) = 1000 × 1/2 × 4/5 = 400. Из 1000 чисел 400 взаимно просты с 1000 — это в точности 6/π² × 1000 ≈ 608 в среднем, но конкретно для 1000 ровно 400.
Часто задаваемые вопросы о функции Эйлера
Что такое функция Эйлера простыми словами?
Какая формула для функции Эйлера?
Чему равна φ(1)?
Зачем функция Эйлера нужна в RSA?
Чем функция Эйлера отличается от функции Кармайкла λ(n)?
До какого числа считает этот калькулятор?
Почему φ(n) для больших составных чисел сложно посчитать?
Данные с калькулятора уходят на сервер?
Полезная информация
Расчёт выполняется в браузере — введённые числа и результат не уходят на сервер.
Алгоритм работает за O(√n) — даже для n = 5 000 000 ответ появляется мгновенно. Для бо́льших чисел используют пробное деление со списком простых либо алгоритмы Полларда.
Смежные инструменты по теории чисел
Эти калькуляторы понадобятся, если вы изучаете криптографию RSA, разбираете олимпиадные задачи или готовитесь к экзамену по дискретной математике.