Euler's theorem

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

Proofs

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.

Related Topics:
Leonhard Euler - 1736 - Group - Ring - 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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~