euler function calculator

What is the Euler function?

Euler’s totient function, written as φ(n), tells you how many integers between 1 and n are relatively prime to n. Two numbers are relatively prime if their greatest common divisor is 1. This function is one of the foundational tools in number theory and appears in topics from modular arithmetic to public-key cryptography.

For example, if n = 10, the numbers from 1 to 10 that are coprime with 10 are 1, 3, 7, and 9. So, φ(10) = 4.

How this euler function calculator works

This calculator uses prime factorization to evaluate φ(n) efficiently. If the distinct prime factors of n are p₁, p₂, ..., p_k, then:

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/p_k)

After you click Calculate, the tool displays:

• The value of φ(n)
• The prime factorization of n
• The exact formula used for your value
• A small coprime list for small n so you can verify the result

Why prime factorization helps

Directly checking each number from 1 to n can be slow for larger n. Factoring n first lets us use a compact formula. This is especially powerful for numbers with only a few prime factors.

Quick examples

Example 1: n = 13 (prime)

Since 13 is prime, every number from 1 to 12 is coprime with 13. Therefore φ(13) = 12.

Example 2: n = 36

36 = 2² × 3², so the distinct prime factors are 2 and 3.

φ(36) = 36 × (1 - 1/2) × (1 - 1/3) = 36 × 1/2 × 2/3 = 12.

Example 3: n = 100

100 = 2² × 5².

φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × 1/2 × 4/5 = 40.

Important properties of φ(n)

• φ(1) = 1 by convention.
• If p is prime, φ(p) = p - 1.
• If p is prime and k ≥ 1, φ(p^k) = p^k - p^k-1.
• If a and b are coprime, then φ(ab) = φ(a)φ(b) (multiplicative property).
• For n > 2, φ(n) is even.

Why Euler’s function matters in real life

1) Cryptography (RSA)

RSA key generation depends on totients. For two primes p and q, we use n = pq and compute φ(n) = (p-1)(q-1). This value is central to choosing encryption/decryption exponents.

2) Modular arithmetic and cycles

Totients describe how many values are invertible modulo n. That helps when solving congruences, finding modular inverses, and studying periodic behavior in sequences.

3) Theoretical and educational value

Euler’s function is a gateway to deeper topics like Euler’s theorem, Carmichael function comparisons, primitive roots, and analytic number theory.

Common questions

Is φ(0) defined?

Not in the usual elementary definition used in this calculator. Here, n must be a positive integer.

Can I enter very large numbers?

You can enter large integers, but extremely large values are slower because factorization gets harder. This page sets a practical limit for smooth in-browser use.

What does “coprime” mean again?

Two integers are coprime when their greatest common divisor is 1. They do not share any prime factor.

Final thoughts

If you are learning number theory, this is one of the most useful functions to master. Try several values, inspect the factorization, and compare results for primes, prime powers, and composite numbers. Patterns appear quickly, and those patterns are exactly what make Euler’s function so powerful.