# Euler's theorem

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
where φ(n) is Euler's totient function and "... ≡ ... (mod n)" denotes congruence modulo n.

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

The theorem may be used to easily reduce large powers modulo n. For example, consider finding the last decimal digit of 7222, i.e. 7222 (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 74 ≡ 1 (mod 10), and we get 7222 ≡ 74·55 + 2 ≡ (74)55·72 ≡ 155·72 ≡ 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 xy (mod φ(n)), then axay (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.

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, Paφ(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).

The Mizar project has completely formalized and automatically checked a proof of Euler's theorem in the EULER_2 file.

## References

Euler's formula, Euler's function, or Euler's identity. Euler's work touched upon so many fields that he is often the earliest written reference on a given matter.
Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study.
The integers (from the Latin integer, which means with untouched integrity, whole, entire) are the set of numbers including the whole numbers (0, 1, 2, 3, …) and their negatives (0, −1, −2, −3, …).
In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1.
totient of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. For example, since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9. The function so defined is the totient function.
Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus.

Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a prime number, then for any integer a, will be evenly divisible by p.
In number theory, the Carmichael function of a positive integer , denoted , is defined as the smallest integer such that
for every integer that is coprime to .
Leonhard Euler

Portrait by Johann Georg Brucker
Born March 15 1707
Basel, Switzerland
Died September 18 [O.S.
17th century - 18th century - 19th century
1700s  1710s  1720s  - 1730s -  1740s  1750s  1760s
1733 1734 1735 - 1736 - 1737 1738 1739

:
Subjects:     Archaeology - Architecture -