Функція Ейлера онлайн
Обчисліть функцію Ейлера φ(n) та знайдіть взаємно прості числаОбчислення функції Ейлера
Введіть натуральне число n:
Теорія функції Ейлера
Що таке функція Ейлера?
Функція Ейлера φ(n) визначає кількість натуральних чисел, які менші за n та взаємно прості з n.
Формула обчислення:
Якщо n = p₁ᵏ¹ × p₂ᵏ² × ... × pₘᵏᵐ, де pᵢ - прості числа, то:
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₘ)
Властивості:
- φ(1) = 1
- φ(p) = p - 1, якщо p - просте число
- φ(pᵏ) = pᵏ - pᵏ⁻¹, якщо p - просте число
- φ(m × n) = φ(m) × φ(n), якщо m та n взаємно прості
Приклади обчислення
Приклад 1: n = 12
Розклад на прості множники: 12 = 2² × 3¹
φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4
Взаємно прості числа: 1, 5, 7, 11
Приклад 2: 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
Приклад 3: n = 100
Розклад на прості множники: 100 = 2² × 5²
φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × 1/2 × 4/5 = 40
Застосування функції Ейлера
Криптографія:
Функція Ейлера використовується в алгоритмі RSA для обчислення приватного ключа та забезпечення безпеки шифрування.
Теорія чисел:
Допомагає вирішувати рівняння в кільці лишків та знаходити порядок елементів у мультиплікативних групах.
Комбінаторика:
Використовується для підрахунку кількості об'єктів з певними властивостями та розв'язання задач на перестановки.