Euler's theorem

:This article is about Euler's theorem in number theory. For other meanings, see Euler function (disambiguation).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Number theory - Integer - Coprime

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:aφ(n) ≡ 1 (mod n)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where φ(n) is Euler's totient function and "mod" denotes the congruence relation.

Related Topics:
Euler's totient function - Congruence

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

Related Topics:
Fermat's little theorem - 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 ≡ 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).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~