In number theory, Euler's theorem (also known as the Fermat-Euler theorem or Euler's totient theorem) states that if n is a positive integer and a is coprime to n, then This article needs to be cleaned up to conform to a higher standard of quality. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Coprime - Wikipedia /**/ @import /skins-1. ...

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

where φ(n) is Euler's totient function and "mod" denotes the congruence relation. In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less or equal than n and coprime to n. ... Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem. Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p... Carmichaels theorem states that if a is coprime to n, then , where is the Carmichael function. ...

The theorem may be used to easily reduce large powers modulo n. For example, consider finding the last decimal digit of 7²²², i.e. 7²²² (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7⁴ ≡ 1 (mod 10), and we get 7²²² ≡ 7^{4·55 + 2} ≡ (7⁴)⁵⁵·7² ≡ 1⁵⁵·7² ≡ 49 ≡ 9 (mod 10).

In general, when reducing a power of a modulo n (where a and n are coprime), one needs to work modulo φ(n) in the exponent of a:

if x ≡ y (mod φ(n)), then a^x ≡ a^y (mod n).

Proofs

Leonhard Euler published a proof in 1736. Using modern terminology, one may prove the theorem as follows: the numbers a which are relatively prime to n form a group under multiplication mod n, the group of units of the ring Z/nZ. This group has φ(n) elements, and the statement of Euler's theorem follows then from Lagrange's theorem. It has been suggested that Leonhard Euler/EB1911 biography be merged into this article or section. ... Events January 26 - Stanislaus I of Poland abdicates his throne. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... Lagranges theorem, in the mathematics of group theory, states that if G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. It is named after Joseph Lagrange. ...

Another direct proof: if a is coprime to n, then multiplication by a permutes the residue classes mod n that are coprime to n; in other words (writing R for the set consisting of the φ(n) different such classes) the sets { x : x in R } and { ax : x in R } are equal; therefore, their products are equal. Hence, P ≡ a^φ(n)P (mod n) where P is the first of those products. Since P is coprime to n, it follows that a^φ(n) ≡ 1 (mod n). Coprime - Wikipedia /**/ @import /skins-1. ...

The Mizar project has completely formalized and automatically checked a proof of Euler's theorem in the EULER_2 file. The Mizar system consists of a language for writing strictly formalized mathematical definitions and proofs, a computer program which is able to check proofs written in this language, and a library of definitions and proved theorems which can be referred to and used in new articles. ...

References

• MathWorld: Euler's Totient Theorem
• Euler's Theorem and Quadratic Reciprocity