Eulers Theorem

Eulers Theorem

Eulers theorem is a fundamental result in number theory that generalizes Fermats little theorem. It establishes a relationship between modular exponentiation and the totient function, with profound applications in cryptography and computational number theory.

Named after Leonhard Euler, this theorem is the mathematical foundation underlying the RSA cryptosystem.

The Euler Totient Function

Before stating the theorem, we need the Euler totient function ϕ(n), which counts the positive integers up to n that are relatively prime to n:

ϕ(n)=|{k:1≤k≤n,gcd(k,n)=1}|

Examples

φ(1)=1 (only 1 is counted)

φ(6)=2 (only 1 and 5 are coprime to 6)

φ(7)=6 (all of 1, 2, 3, 4, 5, 6 are coprime to the prime 7)

φ(10)=4 (the numbers 1, 3, 7, 9 are coprime to 10)

Formula for Totient

For a prime p:

ϕ(p)=p−1

For a prime power:

ϕ(pk)=pk−p(k−1)=p(k−1)*(p−1)

For coprime integers m and n, the totient is multiplicative:

ϕ(m*n)=ϕ(m)*ϕ(n)*when *gcd(m,n)=1

Using the prime factorization, we get the general formula:

ϕ(n)=n*(∏_p|n^)(1−1/p)

Statement of Eulers Theorem

Theorem: If a and n are positive integers with gcd(a,n)=1, then:

aφ(n)≡1*(mod(n))

In words: if a is coprime to n, then a raised to the power φ(n) leaves remainder 1 when divided by n.

Proof Outline

The proof uses the group of units modulo n. Let U(n) be the set of integers between 1 and n that are coprime to n. This forms a group under multiplication modulo n, with |U(n)|=φ(n).

Consider the map x↦a*x*(mod(n)) on U(n). Since gcd(a,n)=1this is a bijection. Therefore:

(∏_x∈U(n)^)(a*x)≡(∏_x∈U(n)^)(x)*(mod(n))

The left side equals a to the ϕ(n) times the product of all x. Canceling the product from both sides (valid since each x is coprime to (n) gives:

aϕ(n)≡1*(mod(n))

Fermats Little Theorem as a Special Case

When n=p is prime, ϕ(p)=p-1, and Eulers theorem becomes Fermats little theorem:

a(p−1)≡1*(mod(p)) for gcd(a,p)=1

Equivalently, for any integer a:

ap≡a*(mod(p))

This version holds even when a is divisible by p.

Applications

Computing Modular Inverses

If g*c*d(a,n)=1, then a has a multiplicative inverse modulo n. From Eulers theorem:

a⋅a(ϕ(n)−1)≡1*(mod(n))

So the inverse of a modulo n is a to the power ϕ(n)-1. This provides one method for computing modular inverses.

RSA Cryptography

The RSA algorithm uses Euler's theorem directly. Given n=p*q (product of two large primes), we have φ(n)=(p−1)*(q−1). Public and private keys e and d satisfy:

e*d≡1*(mod(ϕ(n)))

For any message m with g*c*d(m,n)=1, encryption and decryption work because:

(me)d=m(e*d)=m(1+k*ϕ(n))=m⋅(mϕ(n))k≡m*(mod(n))

Reducing Large Exponents

Eulers theorem allows us to reduce exponents in modular arithmetic. To compute a to a large power k modulo n:

ak≡a(k*mod(ϕ(n)))*(mod(n))

This dramatically simplifies computations with very large exponents.

Carmichael Function

The Carmichael function λ(n) is the smallest positive integer m such that am≡1*(mod(n)) for all a coprime to n. It divides φ(n) and often equals it, but can be smaller.

For example, λ(8)=2 while φ(8)=4. The Carmichael function provides the tightest bound for the exponent in modular arithmetic.

Generalizations

Euler's theorem can be generalized in several ways. For any group G, the order of any element divides the order of the group. When G is the group of units modulo n, this gives Euler's theorem.

The theorem also extends to polynomial rings and other algebraic structures, forming part of the broader theory of groups and rings.

Computing the Totient Function

To compute φ(n), first find the prime factorization n=(p_1)(a_1)*(p_2)(a_2)⋯. Then:

ϕ(n)=(∏_i^)((p_i)((a_i)−1))*((p_i)−1)=n*(∏_p|n^)(1−1/p)

For example, phi(12) = phi(4) times phi(3) = 2 times 2 = 4, or equivalently 12 times (1 - 1/2) times (1 - 1/3) = 12 times 1/2 times 2/3 = 4.

Historical Note

Euler published this theorem in 1763, generalizing Fermats little theorem from 1640. The proof demonstrates Eulers mastery of combining algebraic and number-theoretic ideas.

The theorem remains central to computational number theory and is one of the most practically important results in mathematics, securing trillions of dollars in electronic transactions through its role in RSA encryption.