Proof Using Group Theory
This proof requires the most basic elements of group theory.
The idea is to recognise that the set G = {1, 2, …, p − 1}, with the operation of multiplication (taken modulo p), forms a group. The only group axiom that requires some effort to verify is that each element of G is invertible. Taking this on faith for the moment, let us assume that a is in the range 1 ≤ a ≤ p − 1, that is, a is an element of G. Let k be the order of a, so that k is the smallest positive integer such that
By Lagrange's theorem, k divides the order of G, which is p − 1, so p − 1 = km for some positive integer m. Then
Read more about this topic: Proofs Of Fermat's Little Theorem
Famous quotes containing the words proof, group and/or theory:
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“Remember that the peer group is important to young adolescents, and there’s nothing wrong with that. Parents are often just as important, however. Don’t give up on the idea that you can make a difference.”
—The Lions Clubs International and the Quest Nation. The Surprising Years, I, ch.5 (1985)
“Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
—Willard Van Orman Quine (b. 1908)