Euler's Theorem - Proofs

Proofs

1. Euler's theorem can be proven using concepts from the theory of groups: The residue classes (mod n) that are coprime to n form a group under multiplication (see the article Multiplicative group of integers modulo n for details.) Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case φ(n). If a is any number coprime to n then a is in one of these residue classes, and its powers a, a2, ..., ak ≡ 1 (mod n) are a subgroup. Lagrange's theorem says k must divide φ(n), i.e. there is an integer M such that kM = φ(n). But then,

a^{\varphi(n)} = a^{kM} = (a^{k})^M \equiv 1^M = 1 \pmod{n}.

2. There is also a direct proof: Let R = {x1, x2, ..., xφ(n)} be a reduced residue system (mod n) and let a be any integer coprime to n. The proof hinges on the fundamental fact that multiplication by a permutes the xi: in other words if axj ≡ axk (mod n) then j = k. (This law of cancellation is proved in the article Multiplicative group of integers modulo n.) That is, the sets R and aR = {ax1, ax2, ..., axφ(n)}, considered as sets of congruence classes (mod n), are identical (as sets - they may be listed in different orders), so the product of all the numbers in R is congruent (mod n) to the product of all the numbers in aR:

\prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} ax_i \equiv a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n}, and using the cancellation law to cancel the xis gives Euler's theorem:
a^{\varphi(n)}\equiv 1 \pmod{n}.

Read more about this topic:  Euler's Theorem

Famous quotes containing the word proofs:

    “I do not think that a Physician should be admitted into the College till he could bring proofs of his having cured, in his own person, at least four incurable distempers.”
    —Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    “To invent without scruple a new principle to every new phenomenon, instead of adapting it to the old; to overload our hypothesis with a variety of this kind, are certain proofs that none of these principles is the just one, and that we only desire, by a number of falsehoods, to cover our ignorance of the truth.”
    —David Hume (1711–1776)

    “Trifles light as air
    Are to the jealous confirmation strong
    As proofs of holy writ.”
    —William Shakespeare (1564–1616)