Euler's theorem

﻿
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:$a^\left\{varphi \left(n\right)\right\} equiv 1 pmod\left\{n\right\}$where φ("n") is Euler's totient function and "... &equiv; ... (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 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 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" 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] .

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