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.

“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (1564–1616)

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