Euler's Totient Function Calculator

📘 What is Euler's Totient Function?

Euler's totient function, also known as Euler's phi function (φ), is a fundamental concept in number theory. For a given positive integer `n`, the function `φ(n)` counts the number of positive integers up to `n` that are relatively prime to `n`. Two integers are considered relatively prime (or coprime) if their greatest common divisor (GCD) is 1.

• Emoji Definition: 🤝 Integers that share no common factors other than 1.
• Formal Definition: `φ(n)` is the count of integers `k` in the range `1 ≤ k ≤ n` for which `gcd(k, n) = 1`.
• Example: For `n = 9`, the numbers relatively prime to 9 are 1, 2, 4, 5, 7, and 8. There are 6 such numbers, so `φ(9) = 6`.

🧪 The Formula for Euler's Totient Function

The power of Euler's totient function comes from its elegant formula, which relies on the prime factorization of `n`. If the prime factorization of `n` is `n = p₁^k¹ * p₂^k² * ... * pᵣ^kᵣ`, where `p₁, p₂, ..., pᵣ` are the distinct prime factors of `n`, then the totient is calculated as:

φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/pᵣ)

This formula provides a direct method to compute `φ(n)` without having to manually check the GCD for every number up to `n`, which is highly efficient for large numbers.

🧮 Example Calculation: φ(36)

Let's use our Euler's Totient Function Calculator logic to find `φ(36)` step-by-step:

1. Step 1: Find the Prime Factorization of n.

   We need to break down 36 into its prime factors. `36 = 2 * 18 = 2 * 2 * 9 = 2² * 3²`. The distinct prime factors are `p₁ = 2` and `p₂ = 3`.

2. Step 2: Apply the Totient Formula.

   Using the formula `φ(n) = n * Π(1 - 1/pᵢ)`:

   • `φ(36) = 36 * (1 - 1/2) * (1 - 1/3)`
   • `φ(36) = 36 * (1/2) * (2/3)`
   • `φ(36) = 18 * (2/3)`
   • `φ(36) = 12`
3. Step 3: Verification (Optional).

   We can list the numbers from 1 to 36 and find those coprime to 36. The numbers are: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35. There are exactly 12 numbers, confirming that `φ(36) = 12`.

💡 Key Properties of Euler's Totient Function

The totient function has several beautiful and useful properties that are crucial in number theory and its applications.

• Totient of a Prime Number (p): If `p` is a prime number, then all numbers from 1 to `p-1` are relatively prime to `p`. Therefore, `φ(p) = p - 1`.
• Totient of a Prime Power (pᵏ): For a prime `p` and an integer `k ≥ 1`, the numbers not relatively prime to `pᵏ` are the multiples of `p` (i.e., `p, 2p, ..., pᵏ⁻¹p`). There are `pᵏ⁻¹` such numbers. Thus, `φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p)`.
• Multiplicative Property: This is one of its most important features. If two numbers `m` and `n` are relatively prime (`gcd(m, n) = 1`), then the totient of their product is the product of their totients: `φ(mn) = φ(m) * φ(n)`. This property allows us to easily compute the totient for any number from its prime factorization.
• Euler's Totient Theorem: This theorem states that if `a` and `n` are relatively prime integers, then `a^φ(n) ≡ 1 (mod n)`. This is a generalization of Fermat's Little Theorem and is the cornerstone of the RSA encryption algorithm.
• Sum of Totients of Divisors: For any positive integer `n`, the sum of the totient values for all its positive divisors equals `n` itself. Symbolically: `Σ_{d|n} φ(d) = n`. For example, for `n=12`, the divisors are 1, 2, 3, 4, 6, 12. `φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = 12`.

🛡️ Role in Cryptography: The RSA Algorithm

Euler's totient function is not just an abstract mathematical curiosity; it is the engine behind modern public-key cryptography, most famously the RSA algorithm. Here's how it works:

1. Key Generation:
   • Choose two large, distinct prime numbers, `p` and `q`.
   • Calculate the modulus `n = p * q`. This `n` is part of the public key.
   • Calculate Euler's Totient: Compute `φ(n) = φ(p * q)`. Because `p` and `q` are prime (and thus coprime), we can use the multiplicative property: `φ(n) = φ(p) * φ(q) = (p - 1) * (q - 1)`. This value is kept secret.
   • Choose a public exponent `e` such that `1 < e < φ(n)` and `gcd(e, φ(n)) = 1`.
   • Calculate the private exponent `d` as the modular multiplicative inverse of `e` modulo `φ(n)`. This means `d * e ≡ 1 (mod φ(n))`.
2. Encryption & Decryption:
   • The public key is `(n, e)` and the private key is `(n, d)`.
   • To encrypt a message `M`, the sender computes `C = M^e (mod n)`.
   • To decrypt the ciphertext `C`, the receiver computes `M = C^d (mod n)`.

The security of RSA relies on the fact that while `n` is public, factoring it back into `p` and `q` is computationally infeasible for large numbers. Without knowing `p` and `q`, an attacker cannot compute `φ(n)` and therefore cannot derive the private key `d`.

🐍 Python Euler's Totient Function Algorithm

Implementing Euler's totient function in a programming language like Python is a great way to understand the algorithm. The most common approach involves finding the prime factors of `n`.

def get_phi(n):
    """
    Calculates Euler's Totient Function φ(n) using prime factorization.
    """
    if not isinstance(n, int) or n < 1:
        raise ValueError("Input must be a positive integer.")
    
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    
    if n > 1:
        result -= result // n
        
    return result

# Example Usage:
print(f"φ(36) = {get_phi(36)}")  # Output: φ(36) = 12
print(f"φ(7) = {get_phi(7)}")    # Output: φ(7) = 6
print(f"φ(99) = {get_phi(99)}")  # Output: φ(99) = 60
                    

This euler's totient function algorithm first initializes the result as `n`. Then, it iterates through potential prime factors `p`. If `p` divides `n`, it updates the result by subtracting `result / p` and then removes all factors of `p` from `n`. This process correctly applies the formula `φ(n) = n * Π(1 - 1/p)`. Our online calculator uses a similar, highly optimized JavaScript algorithm for instant results.

🧐 Brief on Euler's Totient Function Proof

Proving the properties of `φ(n)` is a classic exercise in number theory. The proof for the multiplicative property (`φ(mn) = φ(m)φ(n)` for `gcd(m,n)=1`) is particularly elegant and often relies on the Chinese Remainder Theorem (CRT).

The core idea is to show there's a one-to-one correspondence (a bijection) between the set of numbers coprime to `mn` and the pairs of numbers where the first is coprime to `m` and the second is coprime to `n`. The CRT guarantees that for any pair of congruences `x ≡ a (mod m)` and `x ≡ b (mod n)`, there's a unique solution for `x` modulo `mn`. By mapping each number `k` coprime to `mn` to a pair `(k mod m, k mod n)`, we can show this mapping is a bijection, and thus the number of elements in both sets must be equal. Since there are `φ(m)` choices for the first element and `φ(n)` for the second, the total number of pairs is `φ(m)φ(n)`, proving the property.

🔢 Euler's Totient Function Table (n=1 to 25)

A totient table can help visualize how the function behaves for small numbers. Our calculator can generate a larger table for any range you specify.