✦ScienexySCIENCE KNOWLEDGE LIBRARY
theorem · SCI-MAT-002-079

Euler's Theorem and Euler's Totient Function

Euler's Theorem generalizes Fermat's Little Theorem to relatively prime integers, using Euler's totient function to describe the number of positive integers up to n that are relatively prime to n.

φ(n) = n∏(1 − 1/p), where p runs over distinct prime factors of n; if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

Explanation

Euler's totient function, written φ(n), counts the positive integers from 1 to n that are relatively prime to n. For example, the positive integers relatively prime to 8 are 1, 3, 5, and 7, so φ(8) = 4. If p is prime, then φ(p) = p − 1. If p and q are distinct primes, then φ(pq) = (p − 1)(q − 1). More generally, if n has prime factorization n = p₁^a₁p₂^a₂...pₖ^aₖ, then φ(n) = n∏(1 − 1/pᵢ), where the product is taken over the distinct prime factors. Euler's Theorem states that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). It extends Fermat's Little Theorem because when n is prime, φ(n) = n − 1. The theorem is especially important in modular exponentiation and public-key cryptography.

Variables

Φ(n)

Euler's totient function evaluated at n.

N

A positive integer.

A

An integer relatively prime to n.

P

A distinct prime factor of n.

Gcd(a, n)

The greatest common divisor of a and n.

Example or application

Problem

Calculate φ(10) and use Euler's Theorem to evaluate 3^4 modulo 10.

Solution

The positive integers from 1 to 10 relatively prime to 10 are 1, 3, 7, and 9. Thus, φ(10) = 4. Since gcd(3, 10) = 1, Euler's Theorem gives 3^4 ≡ 1 (mod 10). Direct calculation confirms that 3^4 = 81 ≡ 1 (mod 10).

Answer

φ(10) = 4 and 3^4 ≡ 1 (mod 10)

Text

Euler's Theorem connects the multiplicative behavior of integers modulo n with the number of residue classes relatively prime to n. Its coprimality condition is essential: gcd(a, n) must equal 1.

Key Points

  • Euler's totient function counts positive integers up to n that are relatively prime to n.

  • For a prime p, φ(p) = p − 1.

  • If gcd(m, n) = 1, then φ(mn) = φ(m)φ(n).

  • For n = p₁^a₁...pₖ^aₖ, φ(n) = n∏(1 − 1/pᵢ).

  • Euler's Theorem requires gcd(a, n) = 1.

  • The theorem states that a^φ(n) ≡ 1 (mod n) under its conditions.

  • Fermat's Little Theorem is a special case of Euler's Theorem.

Applications

  • RSA public-key cryptography.

  • Calculating modular powers.

  • Finding modular inverses.

  • Studying the structure of integers modulo n.

  • Solving problems involving relatively prime integers.

Learning Outcomes

  • Define Euler's totient function.

  • Calculate φ(n) for simple positive integers.

  • Apply Euler's Theorem when its coprimality condition holds.

  • Explain the relationship between Euler's Theorem and Fermat's Little Theorem.

Practice Questions

  • Calculate φ(12).

  • Find φ(15) using the prime-factor formula.

  • Evaluate 2^6 modulo 9 using Euler's Theorem.

  • Determine whether Euler's Theorem can be applied to 6^k modulo 15.

  • Explain why Fermat's Little Theorem is a special case of Euler's Theorem.

Related Concepts

  • Euler's Totient Function

  • Fermat's Little Theorem

  • Prime Factorization

  • Greatest Common Divisor

  • Modular Exponentiation

  • RSA Cryptography

Common Mistakes

  • Counting integers that are not relatively prime to n when calculating φ(n).

  • Assuming φ(n) always equals n − 1.

  • Applying Euler's Theorem when gcd(a, n) is not 1.

  • Confusing the totient function with the number of divisors of n.

  • Forgetting to use distinct prime factors in the product formula.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory