Euler Totient Function: Mathematical Algorithm Deep Dive

Introduction and Core Concepts

The euler totient function, denoted as φ(n) or phi(n), is one of the most fundamental arithmetic functions in number theory. Introduced by Leonhard Euler in the 18th century, it counts the number of integers up to a given integer n that are relatively prime to n. In other words, φ(n) counts how many numbers k in the range 1 ≤ k ≤ n satisfy gcd(k, n) = 1. By convention, φ(1) = 1, since gcd(1, 1) = 1, and this base case is essential for multiplicative properties.

At first glance, the euler totient function may seem like a purely theoretical curiosity, but its importance extends far beyond abstract mathematics. It is the cornerstone of modern public-key cryptography, particularly the RSA cryptosystem, and plays a critical role in understanding the structure of modular arithmetic. The function reveals deep information about the multiplicative group of integers modulo n, specifically its size and cyclic properties. If you understand φ(n), you understand how many invertible elements exist modulo n.

Formally, for n ≥ 1, the definition is: φ(n) = |{ k : 1 ≤ k ≤ n, gcd(k, n) = 1 }|. For example, φ(9) = 6 because the numbers 1, 2, 4, 5, 7, and 8 are coprime to 9, while 3, 6, and 9 are not. Similarly, φ(10) = 4 (1, 3, 7, 9) and φ(7) = 6 because 7 is prime and every number less than it is coprime to it. This leads to a crucial observation that drives many optimizations: if p is prime, then φ(p) = p - 1, and if p is prime, φ(p^k) = p^k - p^(k-1) = p^k * (1 - 1/p).

Why the Euler Totient Function Matters

The euler totient function matters because it quantifies coprimality, which is the foundation of modular inverses and exponentiation. Euler's theorem states that if a and n are coprime, then a^φ(n) ≡ 1 (mod n). This is a powerful generalization of Fermat's Little Theorem, which is the special case where n is prime and φ(p) = p - 1, giving a^(p-1) ≡ 1 (mod p). Without φ(n), we would have no efficient way to reduce large exponents modulo n, a technique used billions of times per day in secure communications.

Beyond cryptography, the totient function appears in the analysis of algorithms, cyclic group theory, and even in the distribution of prime numbers. It is multiplicative, meaning that if m and n are coprime, then φ(m*n) = φ(m)*φ(n). This property allows us to compute φ(n) efficiently from its prime factorization, rather than by brute-force counting. Understanding this function is therefore essential for any computer scientist working with hashing, random number generation, primality testing, or discrete mathematics.

Key Properties to Remember

• Multiplicativity: If gcd(m, n) = 1, then φ(m*n) = φ(m) * φ(n).
• Prime Power Formula: For prime p and k ≥ 1, φ(p^k) = p^k * (1 - 1/p).
• Euler's Product Formula: For n = p1^k1 * p2^k2 * ... * pr^kr, φ(n) = n * ∏(1 - 1/pi) over distinct primes pi dividing n.
• Sum Property: The sum of φ(d) over all divisors d of n equals n. That is, ∑_{d|n} φ(d) = n.
• Evenness: For n > 2, φ(n) is always even.

How It Works

The mechanism behind the euler totient function is best understood through Euler's product formula. The naive definition suggests counting coprime numbers one by one, which is intuitive but computationally expensive. The product formula transforms this counting problem into a factorization problem. Instead of testing every k from 1 to n, we only need to know the distinct prime factors of n. This insight reduces the problem from O(n) gcd operations to O(√n) trial divisions.

Consider why the product formula works. For a prime p, exactly 1/p of the numbers from 1 to n are divisible by p. So the proportion of numbers NOT divisible by p is (1 - 1/p). If n has two distinct prime factors p and q, we use the principle of inclusion-exclusion. The fraction of numbers coprime to both p and q is (1 - 1/p) * (1 - 1/q). Extending this to all distinct prime factors gives φ(n) = n * ∏(1 - 1/p). This multiplicative filtering is the core intuition: each distinct prime factor independently eliminates a fraction of candidates.

The multiplicative property itself can be proven using the Chinese Remainder Theorem. If m and n are coprime, the ring Z_{mn} is isomorphic to Z_m × Z_n. An element is invertible modulo mn if and only if it is invertible modulo both m and n. Counting invertible elements on both sides yields φ(m*n) = φ(m)*φ(n). This is why we can compute φ(n) by factoring n into coprime prime powers, computing φ for each prime power separately, and multiplying the results. For example, 36 = 2^2 * 3^2, so φ(36) = φ(4) * φ(9) = 2 * 6 = 12, which matches 36 * (1 - 1/2) * (1 - 1/3) = 36 * 1/2 * 2/3 = 12.

The Role of Prime Factorization

Prime factorization is the engine that makes efficient computation of the euler totient function possible. Every integer n > 1 has a unique prime factorization, and the totient depends only on the set of distinct primes, not their multiplicities beyond the initial scaling by n. For instance, φ(12) where 12 = 2^2 * 3 is 12 * (1 - 1/2) * (1 - 1/3) = 4. Note that the exponent 2 on the prime 2 does not appear directly in the product term; it is already accounted for in the leading n. This means that numbers with many small repeated prime factors are not harder to process than square-free numbers with the same distinct primes.

This factorization dependence also explains the function's behavior. Highly composite numbers with many small prime factors have relatively small totients because each factor (1 - 1/p) significantly reduces the result. Conversely, primes and products of large primes have large totients close to n. This distribution is critical for RSA, where we deliberately choose n = p*q for two large primes, ensuring φ(n) = (p-1)*(q-1) is large, hard to guess, and trapdoor-dependent on knowing p and q.

Connection to Euler's Theorem

The deepest theoretical mechanism is Euler's theorem: a^φ(n) ≡ 1 (mod n) for any a coprime to n. This theorem is not just a consequence of the totient function; it is the reason the function is so useful. It tells us that exponentiation modulo n is periodic with period φ(n). Therefore, we can reduce any exponent e modulo φ(n) when working modulo n. For example, to compute 7^222 mod 10, we note φ(10) = 4 and 222 mod 4 = 2, so 7^222 ≡ 7^2 ≡ 49 ≡ 9 (mod 10). This exponent reduction is the basis for fast modular exponentiation and for the correctness of RSA decryption.

Implementation

Implementing the euler totient function in Python can be done at several levels of sophistication, from a naive gcd-based counter suitable for learning to an optimized prime-factorization approach for production use, and finally to a sieve that computes φ for every integer up to N in near-linear time. Below are four canonical implementations, each with detailed comments and analysis.

Naive Implementation: Counting with GCD

This approach directly implements the definition. It iterates through all numbers from 1 to n and counts those with gcd equal to 1. While easy to understand, it is far too slow for n larger than 10^5 and should never be used in practice except for verification.

import math

def phi_naive(n: int) -> int:
    """
    Naive euler totient function using definition.
    Time: O(n log n) due to n gcd computations.
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    count = 0
    # Check every k in [1, n]
    for k in range(1, n + 1):
        if math.gcd(k, n) == 1:
            count += 1
    return count

# Example: phi_naive(9) returns 6
# phi_naive(10) returns 4

Optimized Single-Value Implementation: Prime Factorization

This is the standard method for computing φ(n) for a single large n. It uses Euler's product formula and trial division up to √n. We maintain a result variable initialized to n and for each distinct prime factor p, we apply result = result - result // p, which is equivalent to result *= (1 - 1/p) but avoids floating-point errors.

import math

def phi_optimized(n: int) -> int:
    """
    Optimized euler totient using Euler's product formula.
    Time: O(sqrt(n)), Space: O(1)
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    result = n  # Start with n
    temp_n = n
    
    # Check factor 2 separately to allow increment by 2 later
    if temp_n % 2 == 0:
        while temp_n % 2 == 0:
            temp_n //= 2
        result -= result // 2  # result *= (1 - 1/2)
    
    # Check odd factors from 3 to sqrt(temp_n)
    p = 3
    # Use p * p <= temp_n to avoid sqrt recalculation
    while p * p <= temp_n:
        if temp_n % p == 0:
            # p is a prime factor, remove all occurrences
            while temp_n % p == 0:
                temp_n //= p
            result -= result // p  # Apply (1 - 1/p)
        p += 2  # Only odd numbers
    
    # If temp_n > 1, then it is a prime factor greater than sqrt(n)
    if temp_n > 1:
        result -= result // temp_n
    
    return result

# Example: phi_optimized(36) = 36 * (1-1/2)*(1-1/3) = 12
# phi_optimized(1000000007) returns 1000000006 (prime)

Sieve Implementation: Computing All Totients up to N

When you need φ(k) for all k ≤ N, such as for competitive programming or for building lookup tables, a sieve is dramatically faster than computing each value individually. This algorithm is analogous to the Sieve of Eratosthenes and runs in O(N log log N) time.

def phi_sieve(n: int) -> list[int]:
    """
    Compute euler totient for all numbers 0..n using sieve.
    Time: O(n log log n), Space: O(n)
    Based on Euler's product formula.
    """
    if n < 0:
        return []
    phi = list(range(n + 1))  # phi[i] = i initially
    phi[0] = 0
    if n >= 1:
        phi[1] = 1
    
    # For each prime p, update its multiples
    for p in range(2, n + 1):
        if phi[p] == p:  # p is prime (not yet updated)
            # p is prime, apply (1 - 1/p) to all multiples of p
            for multiple in range(p, n + 1, p):
                phi[multiple] -= phi[multiple] // p
    return phi

# Example: phi_sieve(10) returns [0,1,1,2,2,4,2,6,4,6,4]
# phi[6]=2, phi[7]=6, phi[10]=4

Linear Sieve Implementation: O(N) Time

The linear sieve computes φ for all numbers up to N in true O(N) time by ensuring each composite is processed exactly once by its smallest prime factor. It also stores primes explicitly, which is useful for many number-theoretic tasks.

def phi_linear_sieve(n: int) -> list[int]:
    """
    Linear sieve for euler totient function.
    Time: O(n), Space: O(n)
    Each composite is sieved by its smallest prime factor.
    """
    if n < 1:
        return [0] * (n + 1)
    phi = [0] * (n + 1)
    phi[1] = 1
    primes = []
    is_composite = [False] * (n + 1)
    
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            phi[i] = i - 1  # phi(p) = p - 1 for prime p
        for p in primes:
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                # p divides i, so p is smallest prime factor of i*p
                # phi(i*p) = phi(i) * p
                phi[i * p] = phi[i] * p
                break
            else:
                # p does not divide i, i and p are coprime
                # phi(i*p) = phi(i) * phi(p) = phi(i) * (p - 1)
                phi[i * p] = phi[i] * (p - 1)
        # loop continues
    return phi

# Example: phi_linear_sieve(20)[12] == 4, phi[18] == 6

Step-by-Step Example

To solidify understanding, let us walk through a complete manual computation of the euler totient function for n = 36 using both the definition and the product formula. This dual approach highlights why the formula is so much more efficient and how the multiplicative property works in practice.

Method 1: Brute-force counting. We list numbers from 1 to 36 and compute gcd(k, 36) for each. The prime factorization of 36 is 2^2 * 3^2, so any number divisible by 2 or 3 is not coprime to 36. The numbers from 1 to 36 that are divisible by 2 are: 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36 (18 numbers). Those divisible by 3 are: 3,6,9,12,15,18,21,24,27,30,33,36 (12 numbers). Those divisible by both 2 and 3 (i.e., by 6) are: 6,12,18,24,30,36 (6 numbers). By inclusion-exclusion, numbers divisible by 2 or 3 = 18 + 12 - 6 = 24. Therefore numbers coprime to 36 = 36 - 24 = 12. The 12 numbers are: 1,5,7,11,13,17,19,23,25,29,31,35.

Method 2: Euler's product formula. Factor 36 = 2^2 * 3^2. The distinct primes are 2 and 3. Apply φ(36) = 36 * (1 - 1/2) * (1 - 1/3). Compute stepwise: 36 * (1/2) = 18. Then 18 * (2/3) = 12. The result matches the brute-force count but required only factoring and two multiplications. For larger n, the savings are enormous.

Tracing the Optimized Code for n = 84

Let us trace phi_optimized(84) to see the algorithm in action. Input n = 84, result = 84, temp_n = 84. First, check p = 2: 84 % 2 == 0, so we divide out all 2s: 84 //= 2 → 42, 42 //= 2 → 21. Now temp_n = 21. Apply result -= result // 2 → result = 84 - 42 = 42. Next p = 3: 3*3 = 9 <= 21 and 21 % 3 == 0, so divide out 3s: 21 //= 3 → 7. result -= result // 3 → 42 - 14 = 28. Next p = 5: 5*5 = 25 > 7, loop exits. Since temp_n = 7 > 1, it is a remaining prime factor, so result -= result // 7 → 28 - 4 = 24. Return 24. Verification: 84 = 2^2 * 3 * 7, so φ(84) = 84 * 1/2 * 2/3 * 6/7 = 24. Correct.

This trace also demonstrates handling of repeated prime factors: we divide out all occurrences of p before applying the (1 - 1/p) correction exactly once per distinct prime. Failing to do this and applying the correction for each multiplicity would produce an incorrect, overly small result. The final check for temp_n > 1 is crucial because a prime factor larger than √original_n would otherwise be missed. For n = 2 * prime_large, this case always triggers.

Visualizing the Sieve for N = 10

Consider phi_sieve(10). Initialization: phi = [0,1,2,3,4,5,6,7,8,9,10]. p=2 is prime (phi[2]==2), so update multiples of 2: phi[2]=1, phi[4]=2, phi[6]=3, phi[8]=4, phi[10]=5. p=3 is prime (phi[3]==3), update multiples of 3: phi[3]=2, phi[6]=2, phi[9]=6. p=4 is not prime (phi[4]!=4), skip. p=5 is prime (phi[5]==5), update multiples: phi[5]=4, phi[10]=4. p=6,8,9,10 are composite, skip. p=7 is prime, update phi[7]=6. Final array: [0,1,1,2,2,4,2,6,4,6,4]. This matches known values and shows how each prime's contribution propagates.

Complexity Analysis

Understanding the time and space complexity of different approaches to computing the euler totient function is essential for choosing the right implementation for your constraints, whether you need a single value for a 64-bit integer or all values up to 10^7 for a batch query.

The naive method that tests every k for gcd(k, n) == 1 performs n gcd operations. Each gcd using the Euclidean algorithm costs O(log n), so total time is O(n log n) and space is O(1). This is only feasible for n < 10^5. The optimized trial division method factors n by testing divisors up to √n. In the worst case where n is prime, we test all numbers up to √n, giving O(√n) time and O(1) space. If we precompute primes up to √n via a sieve, the average case improves significantly because we only test prime divisors, roughly O(√n / log √n) divisions.

The sieve methods trade space for time when many queries are needed. The classic sieve computing φ for all n ≤ N runs in O(N log log N) time and O(N) space, which is nearly linear and optimal for moderate N up to 10^6 or 10^7. The linear sieve achieves true O(N) time by ensuring each composite is marked once, at the cost of slightly more complex logic and storing the primes array, still O(N) space. For cryptographic sizes where n is 1024-bit or larger, none of these methods work because factoring is infeasible; instead, φ(n) is computed as (p-1)*(q-1) directly from the known primes p and q during key generation, which is O(1) given p and q.

Detailed Complexity Table

Best, average, and worst cases for trial division depend heavily on the size of the smallest prime factor. If n is even, we find a factor immediately, but we still must continue to factor the remaining cofactor, so the best case is not truly O(1) unless n is a power of 2. For sieve methods, the complexity is deterministic and independent of input distribution, making them predictable for performance budgeting in web servers or database preprocessing jobs.

Practical Performance Considerations

In practice, constant factors matter. Using i += 2 after handling factor 2 halves the trial divisions. Using p * p <= temp_n instead of p <= sqrt(temp_n) avoids expensive floating-point sqrt calls inside the loop. For Python, precomputing primes with a simple sieve up to 10^6 can speed up repeated phi computations for many queries by an order of magnitude. When N exceeds 10^7, memory for the sieve array (phi array of ints) becomes the bottleneck, requiring about 80 MB for N=10^7 in Python lists, so consider using array('I') or numpy for large N, or switching to a segmented sieve approach.

Variations and Optimizations

The euler totient function has several important variations and optimizations that extend its utility and improve performance in specialized contexts. Understanding these helps you adapt the core idea to related problems and avoid reinventing the wheel.

One common optimization is memoization with caching. If your application repeatedly queries φ(n) for the same n, such as in a web service handling cryptographic handshakes or a database query planner, caching results in a dictionary can turn repeated O(√n) work into O(1) lookups. Another optimization is early exit for even numbers or small primes: checking divisibility by 2, 3, 5 before entering the general loop eliminates many composites quickly.

For very large n that does not fit in 64-bit integers, such as 2048-bit RSA moduli, trial division is impossible. Instead, Pollard's Rho algorithm is used for factorization, which has expected time O(n^(1/4)) and can factor 64-bit numbers quickly. When combined with Miller-Rabin primality testing, this yields a probabilistic but highly efficient phi computation for large integers in cryptographic libraries.

Related Arithmetic Functions

Several functions generalize or complement the euler totient function. Jordan's totient function J_k(n) counts k-tuples of integers between 1 and n that form a coprime set with n, with J_1(n) = φ(n). The Carmichael function λ(n) gives the exponent of the multiplicative group modulo n, which is the smallest m such that a^m ≡ 1 (mod n) for all a coprime to n. While φ(n) is always a multiple of λ(n), λ(n) often gives a tighter exponent reduction and is preferred in some cryptographic optimizations. The Dedekind psi function ψ(n) = n * ∏_{p|n} (1 + 1/p) is similar in form but with a plus sign.

Another variation is the totient summatory function Φ(n) = ∑_{i=1}^{n} φ(i), which counts the number of fractions in the Farey sequence of order n and appears in the analysis of the distribution of coprime pairs. Computing Φ(n) efficiently for large n up to 10^11 requires Dirichlet hyperbola methods and memoization, far beyond simple sieves, and is a classic advanced competitive programming problem.

Optimization Techniques Summary

• Wheel Factorization: Skip multiples of 2, 3, 5 by stepping through a wheel pattern (e.g., increments of 6 for 2 and 3), reducing trial divisions by 66%.
• Precomputed Smallest Prime Factor (SPF): Build an SPF table up to N in O(N) time, then factor any n ≤ N in O(log n) by repeatedly dividing by SPF[n].
• Segmented Sieve: For N up to 10^12 but interval length small, compute φ for a range [L, R] without storing up to R.
• Binary GCD (Stein's Algorithm): Use binary gcd for naive counting to avoid modulo operations, slightly faster in low-level languages.
• Using PyPy / Numba: For sieve loops, JIT compilation with Numba can achieve 10-50x speedup over pure Python.

Real-World Applications

The euler totient function is not merely academic; it underpins critical infrastructure in computing and communications. Its most famous application is in public-key cryptography, but its reach extends to hashing, random number generation, and network protocols.

In RSA cryptography, the security relies on the difficulty of computing φ(n) without knowing the factorization of n. Key generation proceeds as follows: choose two large secret primes p and q, compute n = p * q and φ(n) = (p-1)*(q-1). Choose public exponent e coprime to φ(n), typically 65537, and compute private exponent d as the modular inverse of e modulo φ(n), i.e., e*d ≡ 1 (mod φ(n)). Encryption is c = m^e mod n, decryption is m = c^d mod n, and correctness follows from Euler's theorem because e*d = 1 + k*φ(n), so c^d = m^(1 + k*φ(n)) ≡ m (mod n). Anyone who can compute φ(n) from n alone can derive d and break the system, which is as hard as factoring n.

Beyond RSA, the totient function is used in Diffie-Hellman key exchange and ElGamal encryption to determine the size and structure of multiplicative groups, and in primality testing where φ(n) = n-1 if and only if n is prime. In practice, this property is used as a probabilistic check alongside other tests.

Applications in Systems and Networks

In web servers and databases, the totient function appears in the design of hash tables and consistent hashing. Choosing a hash table size that is prime ensures φ(size) = size-1 is maximal, which maximizes the number of distinct probe sequences in open addressing and reduces clustering. Similarly, in distributed databases, partition counts that are coprime to the number of nodes ensure uniform data distribution.

In networking, the function helps in constructing cyclic redundancy checks and in analyzing the period of linear congruential generators (LCGs) for pseudorandom numbers. An LCG with modulus m has maximal period m if and only if certain conditions related to φ(m) hold, including that the multiplier is coprime to m. Understanding φ(m) therefore helps in selecting parameters for random number generation in simulations and games.

Use Case Summary Table

Comparison with Alternatives

While the euler totient function is the standard tool for counting coprime residues and reducing exponents, several related approaches and alternative functions exist. Choosing the right one depends on whether you need group size, exponent period, or just a coprimality test.

The most direct alternative for counting coprimes is brute-force GCD counting, which is conceptually simple but computationally infeasible for large n. Another alternative is the Carmichael function λ(n), which gives the minimal universal exponent. For many n, λ(n) is much smaller than φ(n), providing a tighter exponent reduction. For example, n = 8, φ(8) = 4 but λ(8) = 2, so a^2 ≡ 1 mod 8 for odd a, not just a^4. Using λ(n) can halve exponent size in some RSA optimizations, though computing λ(n) also requires factorization.

For primality testing, alternatives like trial division or Miller-Rabin are more direct than checking φ(n) = n-1, because computing φ(n) itself requires factorization. In hashing, simply choosing a prime table size without explicitly computing φ is often sufficient; the totient reasoning justifies why primes are good choices. Understanding these trade-offs prevents over-engineering.

In summary, use φ(n) when you need the size of the multiplicative group or for standard RSA. Use λ(n) when you need the minimal exponent and can afford slightly more complex logic. Use naive counting only for testing small values or teaching. Use Jordan's totient when counting higher-dimensional coprime structures, such as the number of invertible k×k matrices over Z_n.

Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the euler totient function, especially around edge cases, integer overflow, and handling of prime multiplicities. Awareness of these pitfalls is crucial for writing correct and efficient code.

A frequent mistake is forgetting that φ(1) = 1, not 0. Many sieve initializations incorrectly set phi[1] = 0, which breaks the summatory property ∑_{d|n} φ(d) = n. Another common error is applying the (1 - 1/p) factor for each occurrence of p rather than once per distinct prime. For n = 12 = 2^2 * 3, applying the factor twice for p=2 would give 12 * 1/2 * 1/2 * 2/3 = 2, which is wrong; the correct is 12 * 1/2 * 2/3 = 4. Always divide out all powers of p before updating the result.

Integer overflow is a concern in languages like C++ or Java when computing n * (p-1) / p using 32-bit ints for n up to 10^9; the intermediate n * (p-1) may overflow. The safe pattern result -= result // p avoids overflow by using division first. In Python this is less of an issue due to arbitrary-precision integers, but the pattern is still more efficient and clearer. Another pitfall is using floating-point arithmetic like result *= (1 - 1.0/p), which introduces rounding errors for large n and should never be used.

Best Practices Checklist

• Handle Edge Cases Explicitly: Return 0 for n=0, 1 for n=1, and n-1 for prime n. Add assertions for negative inputs.
• Use Integer Arithmetic Only: Always use result -= result // p instead of floating point.
• Optimize Trial Division: Handle factor 2 separately, then iterate over odd p only. Consider a 2-3-5 wheel for further speed.
• Cache Results: Use lru_cache or a dict for repeated queries in server environments.
• Test with Known Values: Verify against φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4, and φ(36)=12.
• For Sieve, Use Zero-Based Lists Carefully: Ensure phi array size is n+1 and phi[0] is defined.
• Document Complexity: Comment time and space complexity for future maintainers.

Debugging Tips

If your phi function returns incorrect results for numbers like 72 (expected 24), print the distinct prime factors found and compare to the true factorization. If you get 0 for large primes, check for infinite loops when p * p overflows or when using sqrt with floats. Use Python's math.isqrt for exact integer square root when needed: while p <= math.isqrt(temp_n). This avoids floating-point inaccuracies for n near 10^18. Finally, for sieve implementations, validate the sum property for small n: sum(phi[d] for d in divisors(n)) should equal n.

Interview Questions

Interviewers frequently use the euler totient function to test understanding of number theory, algorithm optimization, and the ability to apply mathematical insights to coding problems. Below are common questions with guiding answers.

Question 1: How would you compute φ(n) efficiently for n up to 10^12?

Answer: For a single n up to 10^12, √n is 10^6, so trial division up to 10^6 is feasible. I would implement the optimized factorization method: handle factor 2, then iterate odd p up to √temp_n, dividing out all powers of each prime and updating result -= result // p. If temp_n > 1 after the loop, it is a large prime factor. This runs in O(√n) worst-case but much faster on average, and uses O(1) space. I would mention handling n=1 and using integer arithmetic to avoid floating errors. For multiple queries, I would precompute primes up to 10^6 via sieve to reduce divisions to primes only.

Question 2: Explain why φ(n) is even for n > 2 and prove it.

Answer: For n > 2, if k is coprime to n, then n - k is also coprime to n and distinct from k unless k = n/2, which cannot be coprime when n > 2. Thus coprime residues pair up (k, n-k), giving an even count. Formally, if gcd(k,n)=1 then gcd(n-k,n)=1, and k ≠ n-k mod n for n > 2 because 2k ≡ 0 mod n would imply n divides 2k, impossible when 1 ≤ k < n and gcd(k,n)=1 unless n=2. Therefore φ(n) is even. This also follows from the product formula: if n has an odd prime factor p, then (p-1) is even, and if n is a power of 2 greater than 2, φ(2^k)=2^(k-1) is even.

Question 3: How is the euler totient function used in RSA? What happens if you can compute φ(n) quickly?

Answer: In RSA, n = p*q with p,q large primes, φ(n) = (p-1)*(q-1) is kept secret. The public exponent e and private exponent d satisfy e*d ≡ 1 mod φ(n). If an attacker can compute φ(n) from n, they can compute d = e⁻¹ mod φ(n) and decrypt messages, breaking RSA. Computing φ(n) is computationally equivalent to factoring n, which is believed hard for large n (1024+ bits). So the security of RSA rests on the hardness of factoring and thus of computing φ(n) without knowing p and q. During key generation, φ(n) is computed trivially from p and q in O(1).

Question 4: Given an array of queries, how would you answer φ for each query efficiently?

Answer: If queries are many and max_n is moderate (e.g., up to 10^6 or 10^7), precompute all φ values up to max_n using a sieve in O(N log log N) or linear sieve O(N), then answer each query in O(1). If max_n is large (10^12) but number of queries is small (e.g., <10^4), compute each φ individually via trial division with precomputed primes up to √max_n. I would discuss trade-offs: sieve uses O(N) memory, so for N=10^7 it needs ~80MB in Python, which may be heavy, so consider using array('I') or PyPy. I would also mention caching repeated queries with a dictionary.

Question 5: Compute φ(100) and explain the steps. What is the sum of φ(d) for all divisors d of 100?

Answer: Factor 100 = 2^2 * 5^2. Distinct primes are 2 and 5. φ(100) = 100 * (1 - 1/2) * (1 - 1/5) = 100 * 1/2 * 4/5 = 40. Divisors of 100 are 1,2,4,5,10,20,25,50,100. Their totients: φ(1)=1, φ(2)=1, φ(4)=2, φ(5)=4, φ(10)=4, φ(20)=8, φ(25)=20, φ(50)=20, φ(100)=40. Sum = 1+1+2+4+4+8+20+20+40 = 100, which verifies ∑_{d|n} φ(d) = n. This property can be used to test correctness of an implementation.