Euler\'s theorem - Citizendia

This article is about Euler's theorem in number theory. For other meanings, see List of topics named after Leonhard Euler. In Mathematics and Physics, there are a large number of topics named in honour of Leonhard Euler ( pronounced '''''Oiler''''')

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^{\varphi (n)} \equiv 1 \pmod{n}$

where φ(n) is Euler's totient function and ". 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 The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than In Number theory, the totient \varphi(n of a Positive integer n is defined to be the number of positive integers less than or equal to . . ≡ . . . (mod n)" denotes congruence modulo n. In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem. 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 In Number theory, the Carmichael function of a Positive integer n denoted \lambda(nis defined as the smallest positive integer

The theorem may be used to easily reduce large powers modulo n. For example, consider finding the last decimal digit of 7²²², i. e. 7²²² (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7⁴ ≡ 1 (mod 10), and we get 7²²² ≡ 7^{4x55 + 2} ≡ (7⁴)⁵⁵x7² ≡ 1⁵⁵x7² ≡ 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). In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than

Proofs

Leonhard Euler published a proof in 1736. Year 1736 ( MDCCXXXVI) was a Leap year starting on Sunday (link will display the full calendar of the Gregorian calendar (or a Leap year 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. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real This group has φ(n) elements, and the statement of Euler's theorem follows then from Lagrange's theorem. Lagrange's theorem, in the Mathematics of Group theory, states that for any Finite group G, the order (number of elements of

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. In Mathematics, the Integers a and b are said to be coprime or relatively prime if they have no common factor other than 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. 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

External links

Eric W. Weisstein, Euler's Totient Theorem at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
Euler's theorem at PlanetMath. PlanetMath is a free, collaborative online Mathematics Encyclopedia.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |