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 phi of n, which counts the positive integers up to n that are relatively prime to n:

phi of n equals the absolute value of open brace k colon 1 is less than or equal to k is less than or equal to n comma the gcd of open paren k comma n close paren equals 1 close brace

Examples

phi of 1 equals 1 (only 1 is counted)

phi of 6 equals 2 (only 1 and 5 are coprime to 6)

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

phi of 10 equals 4 (the numbers 1, 3, 7, 9 are coprime to 10)

Formula for Totient

For a prime p:

phi of p equals p minus 1

For a prime power:

phi of open paren p to the k-th power close paren equals p to the k-th power minus p raised to the k minus 1 power equals p raised to the k minus 1 power times open paren p minus 1 close paren

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

phi of m n equals phi of m phi of n when the gcd of open paren m comma n close paren equals 1

Using the prime factorization, we get the general formula:

phi of n equals n the product over p divides n of open paren 1 minus 1 over p close paren

Statement of Eulers Theorem

Theorem: If a and n are positive integers with the gcd of open paren a comma n close paren equals 1, then:

a raised to the phi of n power is identical to 1 times mod n

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

Proof Outline

The proof uses the group of units modulo n. Let U of n be the set of integers between 1 and n that are coprime to n. This forms a group under multiplication modulo n, with the absolute value of U of n equals phi of n.

Consider the map x right arrow from bar a x times mod n on U of n. Since the gcd of open paren a comma n close paren equals 1this is a bijection. Therefore:

the product over x is a member of U of n of a x is identical to the product over x is a member of U of n of x times mod n

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

a raised to the phi of n power is identical to 1 times mod n

Fermats Little Theorem as a Special Case

When n equals p is prime, phi of p equals p minus 1, and Eulers theorem becomes Fermats little theorem:

a raised to the p minus 1 power is identical to 1 times mod p for the gcd of open paren a comma p close paren equals 1

Equivalently, for any integer a:

a to the p-th power is identical to a times mod p

This version holds even when a is divisible by p.

Applications

Computing Modular Inverses

If g c d of open paren a comma n close paren equals 1, then a has a multiplicative inverse modulo n. From Eulers theorem:

a times a raised to the phi of n minus 1 power is identical to 1 times mod n

So the inverse of a modulo n is a to the power phi of n minus 1. This provides one method for computing modular inverses.

RSA Cryptography

The RSA algorithm uses Euler's theorem directly. Given n equals p q (product of two large primes), we have phi of n equals open paren p minus 1 close paren times open paren q minus 1 close paren. Public and private keys e and d satisfy:

e d is identical to 1 times mod phi of n

For any message m with g c d of open paren m comma n close paren equals 1, encryption and decryption work because:

m to the e-th power to the d-th power equals m raised to the e d power equals m raised to the 1 plus k phi of n power equals m times m raised to the phi of n power to the k-th power is identical to m times 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:

a to the k-th power is identical to a raised to the k mod phi of n power times mod n

This dramatically simplifies computations with very large exponents.

Carmichael Function

The Carmichael function lamda of n is the smallest positive integer m such that a to the m-th power is identical to 1 times mod n for all a coprime to n. It divides phi of n and often equals it, but can be smaller.

For example, lamda of 8 equals 2 while phi of 8 equals 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 phi of n, first find the prime factorization n equals p sub 1 raised to the a sub 1 power p sub 2 raised to the a sub 2 power dot dot dot. Then:

phi of n equals the product over i of open paren p sub i raised to the a sub i minus 1 power close paren times open paren p sub i minus 1 close paren equals n the product over p divides n of open paren 1 minus 1 over p close paren

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.