Euler's Totient
Counts integers up to n coprime to n.
Formula
Variables
Example
φ(12) = 4
How it works
Euler’s totient function [0m[0mcounts how many integers from 1 to n have no common factor with n other than 1. The product formula works because for each prime divisor p of n, exactly a 1/p fraction of the numbers up to n are multiples of p, so removing those multiples for every distinct prime factor leaves the count of numbers coprime to n. This is an inclusion-exclusion result in compact multiplicative form.
When to use it
Use this when you need the size of the reduced residue system modulo n, especially in modular arithmetic, RSA, and other number-theory problems involving coprimality. It is also useful for simplifying expressions like a^φ(n) mod n when using Euler’s theorem.
Worked example, step by step
Find [0m[0m[0m[0mφ(18). 18 = 2 × 3^2, so the distinct prime divisors are 2 and 3. Apply the formula: φ(18) = 18(1 - 1/2)(1 - 1/3) Compute each factor: φ(18) = 18 × 1/2 × 2/3 Multiply: φ(18) = 18 × 1/3 = 6 So, φ(18) = 6.
Common mistakes to avoid
- Using repeated prime factors more than once; only distinct prime divisors appear in the product
- Forgetting that the formula applies to positive integers n, not to individual prime powers directly unless factored first
- Assuming φ(n) counts numbers not divisible by any prime dividing n, instead of numbers that are coprime to n
Did You Know?
Euler's totient counts the numbers coprime to n — the secret sauce inside RSA key generation.
Share this formula
More in Number Theory
View allEuclidean Algorithm
BasicRecursively finds the greatest common divisor.
Modular Congruence
Basica and b have the same remainder when divided by m.
Fermat's Little Theorem
AdvancedHolds when p is prime and gcd(a,p)=1.
Prime Number Theorem
AdvancedApproximates the number of primes below x.
LCM from GCD
BasicLeast common multiple via the greatest common divisor.
Sum of First n Integers
BasicClosed form for the sum of the first n natural numbers.