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 k1 through km such the sum of all ki 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 kj not equal to p for any j, we have

and

if kj 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 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)

    “Every expansion of government in business means that government in order to protect itself from the political consequences of its errors and wrongs is driven irresistibly without peace to greater and greater control of the nation’s press and platform. Free speech does not live many hours after free industry and free commerce die.”
    —Herbert Hoover (1874–1964)