- 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 positiveinteger and "a" iscoprime to "n", then:$a^\{varphi\; (n)\}\; equiv\; 1\; pmod\{n\}$where φ("n") isEuler'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^{4x55 + 2}≡ (7^{4})^{55}x7^{2}≡ 1^{55}x7^{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 in1736 . 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" forthe 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 [

*http://www.mizar.org/JFM/Vol10/euler_2.html EULER_2 file*] .**External links***

* [*http://planetmath.org/encyclopedia/EulersTheorem.html Euler's Theorem*] at [*http://planetmath.org PlanetMath*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Euler'sches Theorem**— Ausschöpfungstheorem, Adding up Theorem. Bei linear homogenen Produktionsfunktionen gilt: wobei: f´i = partielle Grenzproduktivität des Faktors i, ri = gesamte Einsatzmenge des Faktors i, Q = Output. Bei vollständiger Konkurrenz ist das… … Lexikon der Economics**Euler's theorem (differential geometry)**— In the mathematical field of differential geometry, Euler s theorem is a result on the curvature of curves on a surface. The theorem establishes the existence of principal curvatures and associated principal directions which give the directions… … Wikipedia**Euler's theorem in geometry**— In geometry, Euler s theorem, named after Leonhard Euler, states that the distance d between the circumcentre and incentre of a triangle can be expressed as : d^2=R (R 2r) ,where R and r denote the circumradius and inradius respectively (the… … Wikipedia**Euler's totient function**— For other functions named after Euler, see List of topics named after Leonhard Euler. The first thousand values of φ(n) In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal … Wikipedia**Euler's formula**— This article is about Euler s formula in complex analysis. For Euler s formula in algebraic topology and polyhedral combinatorics see Euler characteristic. Part of a series of articles on The mathematical constant e … Wikipedia**Euler's rotation theorem**— In kinematics, Euler s rotation theorem states that, in three dimensional space, any displacement of a rigid body such that a point on the rigid body remains fixed, is equivalent to a rotation about a fixed axis through that point. The theorem is … Wikipedia**Euler-Bernoulli beam equation**— Euler Bernoulli beam theory, or just beam theory, is a simplification of the linear theory of elasticity which provides a means of calculating the load carrying and deflection characteristics of beams. It was first enunciated circa 1750, but was… … Wikipedia**Euler's sum of powers conjecture**— Euler s conjecture is a disproved conjecture in mathematics related to Fermat s last theorem which was proposed by Leonhard Euler in 1769. It states that for all integers n and k greater than 1, if the sum of n k th powers of positive integers is … Wikipedia**Euler's criterion**— In mathematics, Euler s criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime. DefinitionEuler s criterion states: Let p be an odd prime and a an integer coprime to p . Then a is a… … Wikipedia**Euler pseudoprime**— An odd composite integer n is called an Euler pseudoprime to base a , if a and n are coprime, and : a^{(n 1)/2} equiv pm 1pmod{n}(where mod refers to the modulo operation).The motivation for this definition is the fact that all prime numbers p… … Wikipedia