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:

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

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

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