Euler's Totient
Counts integers below n coprime to it, for n = pq — used to make RSA keys.
Formula
Live Calculator
MembersVariables
Example
p=3, q=11: φ = 2×10 = 20
How it works
For a number n that is the product of two different primes, n = pq, Euler’s totient counts how many whole numbers from 1 up to n - 1 share no common factor with n. Because a number is coprime to pq exactly when it is not divisible by p or q, the count is the total numbers below n minus the multiples of p and q, which simplifies to (p - 1)(q - 1). This is a key step in RSA, because the totient gives the size of the group of invertible numbers modulo n.
When to use it
Use this when working with RSA-style cryptography problems where the modulus is built from two primes. It is also useful in number theory whenever you need the count of integers coprime to a semiprime.
Worked example, step by step
Let p = 5 and q = 17 n = pq = 5 × 17 = 85 φ(n) = (p - 1)(q - 1) φ(85) = (5 - 1)(17 - 1) φ(85) = 4 × 16 φ(85) = 64
Common mistakes to avoid
- Using φ(n) = (p + 1)(q + 1) instead of subtracting 1 from each prime
- Applying this formula when n is not exactly the product of two primes
- Forgetting that φ(n) counts numbers less than n, not including n itself
Did You Know?
Choosing e coprime to φ(n) and finding its inverse d is exactly how an RSA key pair is generated.
Share this formula
More in Cryptography & Security
View allModular Exponentiation
IntermediateCore operation of RSA encryption — raise a message to a power, modulo n.
RSA Decryption
AdvancedRecovers the message using the private exponent d.
Shannon Entropy
AdvancedAverage information content — and the theoretical strength of a random source.
Password Entropy
IntermediateBits of security from password length and character-set size.
Key Space Size
IntermediateNumber of possible keys for a b-bit key.
Birthday Bound
AdvancedCollisions become likely after about √ of the hash space.