What is Euler's theorem in number theory?

Euler's theorem states that if two positive integers, n and a, are coprime, then raising a to the power of Euler's totient function of n leaves a remainder of 1 when divided by n. Also known as the Fermat-Euler theorem or Euler's totient theorem, it generalizes Fermat's little theorem to cases where the modulus is not prime. It is frequently used to simplify large modular exponentiation problems.

What we know

• If n and a are coprime positive integers, then the phi(n)-th power of a is congruent to 1 modulo n, where phi denotes Euler's totient function. [1, 2]
• Leonhard Euler published a proof of Fermat's little theorem in 1736 and later proved the generalized theorem for non-prime moduli in 1763. [2]
• The converse of Euler's theorem is true, meaning that if a to the power of phi(n) is congruent to 1 modulo n, then a and n must be coprime. [2]
• Euler's theorem can be used to easily reduce large powers modulo n, such as finding the ones place digit of 7 to the 222nd power. [2]

Where to go next

• compared withWhat is Fermat's little theorem?
• how it workedHow does Euler's totient function work?
• how we knowWhat are Carmichael's theorems?
• whoHow did Leonhard Euler contribute to number theory?
• the bigger pictureWhere else is modular arithmetic applied?
• an unexpected connectionHow does the Euler characteristic relate to topology?Although Leonhard Euler is famous for number theory theorems like the totient theorem, his name is also attached to the topological invariant used to classify polyhedra and spaces.

Sources

• [1]Euler's theorem (Wikidata Q193910) · CC0 1.0
• [2]Euler's theorem · CC BY-SA 4.0
• [3]Euler characteristic · CC BY-SA 4.0
• [4]Euler's identity · CC BY-SA 4.0
• [5]List of theorems · CC BY-SA 4.0