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:

    “A man’s women folk, whatever their outward show of respect for his merit and authority, always regard him secretly as an ass, and with something akin to pity. His most gaudy sayings and doings seldom deceive them; they see the actual man within, and know him for a shallow and pathetic fellow. In this fact, perhaps, lies one of the best proofs of feminine intelligence, or, as the common phrase makes it, feminine intuition.”
    —H.L. (Henry Lewis)

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

    “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)