# Euler's theorem

*This article is about Euler's theorem in number theory. For other meanings, see List of topics named after Leonhard Euler.*

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

*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 7

^{222}, i.e. 7

^{222}(mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7

^{4}≡ 1 (mod 10), and we get 7

^{222}≡ 7

^{4·55 + 2}≡ (7

^{4})

^{55}·7

^{2}≡ 1

^{55}·7

^{2}≡ 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**/

*n*

**Z**. 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,

*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*).

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

## References

- MathWorld: Euler's Totient Theorem

**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.

**.....**Click the link for more information.

**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.

**.....**Click the link for more information.

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, …).**.....**Click the link for more information. 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.**.....**Click the link for more information.**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**.

**.....**Click the link for more information.

**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**.

**.....**Click the link for more information.

For other theorems named after Pierre de Fermat, see .

**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*.

**.....**Click the link for more information.

In number theory, the

**Carmichael function**of a positive integer , denoted , is defined as the smallest integer such that**.....**Click the link for more information.**Leonhard Euler**

Portrait by Johann Georg Brucker

Born March 15 1707

Basel, Switzerland

Died September 18 [O.S.

**.....**Click the link for more information.

17th century -

1700s 1710s 1720s - 1730s - 1740s 1750s 1760s

1733 1734 1735 -

**18th century**- 19th century1700s 1710s 1720s - 1730s - 1740s 1750s 1760s

1733 1734 1735 -

**1736**- 1737 1738 1739**:***Subjects:*Archaeology - Architecture -**.....**Click the link for more information.**group**is a set with a binary operation that satisfies certain axioms, detailed below. For example, the set of integers with addition is a group. The branch of mathematics which studies groups is called group theory.

**.....**Click the link for more information.

In mathematics, a

**ring**is an algebraic structure in which addition and multiplication are defined and have properties listed below. The branch of abstract algebra which studies rings is called ring theory.**.....**Click the link for more information.**Lagrange's theorem**, in the mathematics of group theory, states that for any finite group

*G*, the order (number of elements) of every subgroup

*H*of

*G*divides the order of

*G*. Lagrange's theorem is named after Joseph Lagrange.

**.....**Click the link for more information.

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.**.....**Click the link for more information. 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.**.....**Click the link for more information.This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.