- Простые числа, на прямой φ(p) = p − 1
- Другие числа
- Ваше n
Калькулятор функции Эйлера
Из чисел от 1 до 12 только 1, 5, 7 и 11 не имеют общих делителей с 12, поэтому φ(12) = 4. Функция Эйлера считает такие взаимно простые числа для любого n. Введите число до 10^18, чтобы получить φ(n) с простыми делителями и расписанной формулой произведения, увидеть числа от 1 до n с выделенными взаимно простыми, проверить теорему Эйлера, построить φ(k) сразу для 100 000 чисел или найти все n с заданным φ(n). Введите целое число n до 10^18 или выберите разобранный пример. Плитки показывают φ(n), простые делители n, долю чисел от 1 до n, взаимно простых с n, и количество делителей, а шаги расписывают формулу произведения на ваших числах. До n = 500 числа от 1 до n рисуются: взаимно простые с n закрашены, остальные окрашены в цвет наименьшего простого числа, общего у них с n. Наведите на число, чтобы увидеть его НОД с n, и щёлкните по нему, чтобы использовать его как a в теореме Эйлера. «График» показывает φ(k) для каждого k до заданной границы; щёлкните по точке, чтобы открыть это число. «Обращение» перечисляет все n с φ(n) = m; щёлкните по одному из них, чтобы открыть его.
Как это работает
- Введите целое число n до 10^18 или выберите разобранный пример, например φ(60), модуль RSA или число Кармайкла 561.
- Посмотрите φ(n), простые делители и формулу произведения на ваших числах. До 500 наведите на числа от 1 до n, чтобы увидеть их НОД с n, и щёлкните по одному из них, чтобы проверить на нём теорему Эйлера.
- Переключитесь на «График», чтобы увидеть φ(k) для каждого k до 100 000, или на «Обращение», чтобы перечислить все n с φ(n) = m.
Как вычисляется φ(n)
Разложите n на простые множители и умножьте n на (1 − 1/p) для каждого простого p, на которое делится n. Для 60 = 2² × 3 × 5 получается 60 × 1/2 × 2/3 × 4/5 = 16. Вычёркивание даёт тот же результат: из 60 чисел 30 чётные; из 30 нечётных 10 кратны 3; из 20 оставшихся 4 кратны 5, и остаётся 16. Для степени простого формула выглядит как φ(p^k) = p^(k−1)(p − 1), а значения перемножаются: φ(60) = 2 × 2 × 4. Трудная часть — разложение. Калькулятор использует пробное деление, тест простоты Миллера — Рабина и ро-метод Полларда, так что даже 18-значное произведение двух 9-значных простых чисел занимает долю секунды.
Где используется функция Эйлера
φ(n) считает дроби k/n между 0 и 1, которые уже несократимы, длины шагов, при которых стрелка часов с n делениями проходит через каждое деление (1, 5, 7 и 11 на 12-часовом циферблате), и числа, имеющие обратный элемент по модулю n. Эйлер доказал, что a^φ(n) ≡ 1 (mod n) для каждого a, взаимно простого с n, и на этом держится шифрование RSA: при n = 3233 = 61 × 53 имеем φ(n) = 60 × 52 = 3 120, а у открытого показателя 17 закрытый партнёр 2 753, потому что 17 × 2 753 = 15 × 3 120 + 1.
Часто задаваемые вопросы
Что такое функция Эйлера?
φ(n) — количество целых чисел от 1 до n, у которых нет общих делителей с n, кроме 1. φ(9) = 6, потому что 1, 2, 4, 5, 7 и 8 взаимно просты с 9, а у 3, 6 и 9 есть общий множитель 3. По соглашению φ(1) = 1. Эйлер изучал эту функцию в 1760-х годах; Гаусс дал ей обозначение φ в 1801 году, а Джеймс Джозеф Сильвестр — английское название totient в 1879 году.
Чему равна φ простого числа?
p − 1, потому что каждое число от 1 до p − 1 взаимно просто с простым p, так что φ(97) = 96. Для степени простого φ(p^k) = p^k − p^(k−1), потому что общий делитель с ней есть только у кратных p: φ(81) = 81 − 27 = 54.
Что утверждает теорема Эйлера?
Если a и n взаимно просты, то a^φ(n) даёт остаток 1 при делении на n. Для n = 60 и a = 7: φ(60) = 16, и 7^16 ≡ 1 (mod 60). Малая теорема Ферма — это случай простого n. Часто хватает и меньшего показателя: 7^4 = 2 401 = 40 × 60 + 1. Наименьший показатель, который подходит для всех a, взаимно простых с n, — функция Кармайкла λ(n); для 60 она равна 4.
Может ли у двух чисел быть одинаковое значение φ?
Да, и обычно таких чисел несколько: φ(n) = 24 при n = 35, 39, 45, 52, 56, 70, 72, 78, 84 и 90. Некоторые чётные числа никогда не бывают значением φ, наименьшее из них — 14, и ни одно нечётное число больше 1 тоже не бывает, потому что φ(n) чётно начиная с n = 3. Роберт Кармайкл утверждал в 1907 году, что никакое значение не принимается ровно один раз. Это до сих пор не доказано, а Кевин Форд показал в 1998 году, что исключение должно быть больше 10^(10^10).
Насколько большое число можно ввести?
Любое целое число до 10^18. Калькулятор раскладывает его точной целочисленной арифметикой прямо в браузере, поэтому φ(10^18) = 4 × 10^17 и φ(999 999 866 000 004 473) = 999 999 864 000 004 608 верны до последней цифры. Числа от 1 до n рисуются до 500, график доходит до 100 000, а обращение работает для значений до 10^10.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор