Enter a positive integer n to calculate φ(n) — count of integers ≤ n and coprime with n
Result
φ()
Step-by-Step Derivation
Euler Totient Formula
If n = p₁a₁ × p₂a₂ × … × pkak
Then φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/pk)
Where p₁, p₂, …, pk are distinct prime factors of n
Euler's totient function is critical in number theory and forms the mathematical basis of the RSA encryption algorithm.
⚠The totient function only depends on the distinct prime factors of n, not their exponents. For example, φ(12) = 12×(1-1/2)×(1-1/3) = 4.
What is Euler Totient Function?
Euler's totient function φ(n) counts the positive integers up to n that are coprime with n. It is a core function in number theory and plays a key role in modern public-key cryptography.
Definition
φ(n) counts integers from 1 to n-1 coprime with n. Example: φ(6)=2 (numbers 1 and 5).
Calculation Formula
If n = p₁^a₁×...×p_k^a_k, φ(n)=n×(1-1/p₁)×...×(1-1/p_k). Only distinct primes are used.
Key Properties
For prime p: φ(p)=p-1. For coprime m,n: φ(mn)=φ(m)φ(n). Euler's theorem: a^φ(n)≡1(mod n).
Cryptography Use
The totient function enables RSA encryption. It calculates private keys using Euler's theorem and large-number factorization.
💡 Example: Calculate φ(12). 12=2²×3, distinct primes: 2,3. φ(12)=12×(1-1/2)×(1-1/3)=4. Verified: 1,5,7,11 are coprime with 12.
Euler's totient function φ(n) counts positive integers up to n that are coprime with n. Example: φ(12)=4 (1,5,7,11).
What is the totient function formula?▼
If n = p₁^a₁×p₂^a₂×…×p_k^a_k, φ(n) = n×(1-1/p₁)×(1-1/p₂)×…×(1-1/p_k). Only distinct prime factors are used.
What is φ(1)?▼
φ(1) = 1 by mathematical definition. Only the number 1 is coprime with itself.
How is φ(n) used in cryptography?▼
The totient function is the foundation of RSA encryption. It uses Euler's theorem and prime factorization difficulty to generate secure encryption keys.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.