HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if and are coprime positive integers, and \varphi(n) is
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
, then raised to the power \varphi(n) is congruent to
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
; that is :a^ \equiv 1 \pmod. In 1736,
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
published a proof of Fermat's little theorem (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where is a prime number. Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where is not prime. The converse of Euler's theorem is also true: if the above congruence is true, then a and n must be coprime. The theorem is further generalized by
Carmichael's theorem In number theory, Carmichael's theorem, named after the American mathematician R. D. Carmichael, states that, for any nondegenerate Lucas sequence of the first kind ''U'n''(''P'', ''Q'') with relatively prime parameters ''P'',&nbs ...
. The theorem may be used to easily reduce large powers modulo n. For example, consider finding the ones place decimal digit of 7^, i.e. 7^ \pmod. The integers 7 and 10 are coprime, and \varphi(10) = 4. So Euler's theorem yields 7^4 \equiv 1 \pmod, and we get 7^ \equiv 7^ \equiv (7^4)^ \times 7^2 \equiv 1^ \times 7^2 \equiv 49 \equiv 9 \pmod. In general, when reducing a power of a modulo n (where a and n are coprime), one needs to work modulo \varphi(n) in the exponent of a: :if x \equiv y \pmod, then a^x \equiv a^y \pmod. Euler's theorem underlies the
RSA cryptosystem RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publi ...
, which is widely used in
Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, p ...
communications. In this cryptosystem, Euler's theorem is used with being a product of two large
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, and the security of the system is based on the difficulty of factoring such an integer.


Proofs

1. Euler's theorem can be proven using concepts from the theory of groups: The residue classes modulo that are coprime to form a group under multiplication (see the article Multiplicative group of integers modulo ''n'' for details). The
order Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
of that group is . Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case . If is any number coprime to then is in one of these residue classes, and its powers modulo form a subgroup of the group of residue classes, with . Lagrange's theorem says must divide , i.e. there is an integer such that . This then implies, :a^ = a^ = (a^)^M \equiv 1^M =1 \equiv 1 \pmod. 2. There is also a direct proof: Let be a reduced residue system () and let be any integer coprime to . The proof hinges on the fundamental fact that multiplication by permutes the : in other words if then . (This law of cancellation is proved in the article Multiplicative group of integers modulo ''n''.See Bézout's lemma) That is, the sets and , considered as sets of congruence classes (), are identical (as sets—they may be listed in different orders), so the product of all the numbers in is congruent () to the product of all the numbers in : : \prod_^ x_i \equiv \prod_^ ax_i = a^\prod_^ x_i \pmod, and using the cancellation law to cancel each gives Euler's theorem: : a^\equiv 1 \pmod.


See also

*
Carmichael function In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that :a^m \equiv 1 \pmod holds for every integer coprime to . In algebraic terms, is the exponent of the multi ...
*
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then : a^ \equiv \begin \;\;\,1\pmod& \textx ...
* Fermat's little theorem *
Wilson's theorem In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of m ...


Notes


References

The '' Disquisitiones Arithmeticae'' has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes. * * * * *


External links

*
Euler-Fermat Theorem
a
PlanetMath
{{Portal bar, Mathematics Modular arithmetic Theorems in number theory Articles containing proofs Leonhard Euler