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


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
for every integer that is coprime to .
..... Click the link for more information.
Leonhard Euler

Portrait by Johann Georg Brucker
Born March 15 1707(1707--)
Basel, Switzerland
Died September 18 [O.S.
..... Click the link for more information.
17th century - 18th century - 19th century
1700s  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.