Euler's theorem

In number theory, Euler's theorem states that, if and are coprime positive integers, then is congruent to modulo, where denotes Euler's totient function; that is
In 1736, Leonhard Euler published a proof of Fermat's little theorem, 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 and must be coprime.
The theorem is further generalized by some of Carmichael's theorems.
The theorem may be used to easily reduce large powers modulo. For example, consider finding the ones place decimal digit of, i.e.. The integers 7 and 10 are coprime, and. So Euler's theorem yields, and we get.
In general, when reducing a power of modulo , one needs to work modulo in the exponent of :
Euler's theorem underlies the RSA cryptosystem, which is widely used in Internet communications. In this cryptosystem, Euler's theorem is used with being a product of two large prime numbers, 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. The order 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,
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. That is, the sets and, considered as sets of congruence classes, are identical, so the product of all the numbers in is congruent to the product of all the numbers in :