Proofs of Fermat's Little Theorem - Proof Using The Multinomial Expansion

Proof Using The Multinomial Expansion

The proof is a very simple application of the Multinomial formula which is brought here for the sake of simplicity.

$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1,k_2,\ldots,k_m} {n \choose k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}.$

The summation is taken over all sequences of nonnegative integer indices k₁ through k_m such the sum of all k_i is n.

Thus if we express a as a sum of 1s (ones), we obtain

$a^p = \sum_{k_1,k_2,\ldots,k_a} {p \choose k_1, k_2, \ldots, k_a}$

Clearly, if p is prime, and if k_j not equal to p for any j, we have

and

if k_j equal to p for some j

Since there are exactly a elements such that the theorem follows.

Read more about this topic: Proofs Of Fermat's Little Theorem

Famous quotes containing the words proof and/or expansion:

“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)

“Artistic genius is an expansion of monkey imitativeness.”
—W. Winwood Reade (1838–1875)