|
In number theory, Euler's theorem (also known as the
Fermat-Euler theorem) states that if n is a positive integer and a is relatively prime to
n, then
- aφ(n) = 1 (mod
n)
where φ(n) denotes Euler's totient
function.
The theorem is a generalization of Fermat's little
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 x = y (mod φ(n)), then ax = ay
(mod n).
Proofs of Euler's theorem
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, 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 .
-
|