Fermat’s Little Theorem implies Wilson’s Theorem

I came across this novel argument in a book last year. It basically exploits the identity,

\displaystyle \sum_{i=0}^{n} (-1)^{i}{{n}\choose{i}} (x-i)^{n}=n!\ \forall{\ n\geq{0},x\in{\mathbb{R}}}

Wilson’s theorem states that

\displaystyle (p-1)!\equiv -1 \ (mod \ p)

The result is true for p=2. So we may assume p>2. We then conveniently consider the above expression for n=p-1.

\displaystyle\sum_{i=0}^{p-1} (-1)^{i}{{p-1}\choose{i}} (x-i)^{p-1}=(p-1)!

Choosing x=0 we get

\displaystyle\sum_{i=0}^{p-1} (-1)^{i}{{p-1}\choose{i}} (-i)^{p-1}=(p-1)!

Using Fermat’s little theorem and the fact that ‘p’ is odd we get,

\displaystyle\sum_{i=1}^{p-1} (-1)^{i}{{p-1}\choose{i}} \equiv (p-1)! \ (mod \ p)

The Pascal’s identity,

\displaystyle{{p}\choose{i}}={{p-1}\choose{i}}+{{p-1}\choose{i-1}}

then implies,

\displaystyle{{p-1}\choose{i}}\equiv-{{p-1}\choose{i-1}}(mod\ p)

And since {{p-1}\choose{0}}\equiv 1 it follows that

\displaystyle{{p-1}\choose{i}}\equiv{(-1)^{i}}

Therefore,

\displaystyle\sum_{i=1}^{p-1} (-1)^{i}{{p-1}\choose{i}}\equiv\sum_{i=1}^{p-1} (-1)^{i}(-1)^{i}=\sum_{i=1}^{p-1}1\equiv (p-1)!

And thus,

\displaystyle(p-1)!\equiv (p-1)\equiv -1 (mod\ p)

Published in: on May 2, 2009 at 8:44 am  Leave a Comment  
Tags: , , , ,

Counting and the Lagrange identity.

This is a prime example of how a proof for a general argument can be worked out by considering simple cases. The Lagrange identity for \mathbb{C} says that

\displaystyle |\sum_{i=0}^{n} a_{i}b_{i}|^{2}=\sum_{i=0}^{n} |a_{i}|^{2}\sum_{i=0}^{n} |b_{i}|^{2}-\sum_{1 \leq{i}<j\leq{n}} |a_{i}\overline{b_{j}}-a_{j}\overline{b_{i}}|^{2}\ \ \ \ \ (1)

We will analyze the case for n=3. It will provide a beautiful outline for a general proof.

The left hand side of the equality (1) will be equal to

\displaystyle |a_{1}b_{1} +a_{2}b_{2}+a_{3}b_{3}|^{2}=(a_{1}b_{1} +a_{2}b_{2}+a_{3}b_{3})(\overline{a_{1}b_{1}}+\overline{a_{2}b_{2}}+\overline{a_{3}b_{3}})\ \  (2)

It would be helpful indeed to consider the following 3 x 3 matrix for the sum of all the elements of this matrix is equal to the LHS of (2).

\displaystyle \left(\begin{array}{ccc}a_{1}\overline{a_{1}}b_{1}  \overline{b_{1}}&a_{1}\overline{a_{2}}b_{1}\overline{b_{2}}&a_{1}\overline{a_{3}}b_{1}\overline{b_{3}}\\ a_{2}\overline{a_{1}}b_{2}\overline{b_{1}}&a_{2}\overline{a_{2}}b_{2}\overline{b_{2}}&a_{2}\overline{a_{3}}b_{2}\overline{b_{3}}\\ a_{3}\overline{a_{1}}b_{3}\overline{b_{1}}&a_{3}\overline{a_{2}}b_{3}\overline{b_{2}}&a_{3}\overline{a_{3}}b_{3}\overline{b_{3}}\end{array}\right)

In fact, the elements of the matrix are the terms on the RHS in (2).

Each term of the matrix above can thus be represented as

\displaystyle A_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}

Now consider the first term on the RHS in (1). For n=3, it is

\displaystyle (|a_{1}|^{2}+|a_{2}|^{2}+|a_{3}|^{2})(|b_{1}|^{2}+|b_{2}|^{2}+|b_{3}|^{2})

\displaystyle=(a_{1}\overline{a_{1}}+a_{2}\overline{a_{2}}+a_{3}\overline{a_{3}})(b_{1}\overline{b_{1}}+b_{2}\overline{b_{2}}+b_{3}\overline{b_{3}})\ \ \ (3)

Again, as above, it would be helpful to consider the following matrix.

\displaystyle \left(\begin{array}{ccc}a_{1}\overline{a_{1}}b_{1}\overline{b_{1}}&a_{1}\overline{a_{1}}b_{2}\overline{b_{2}}&a_{1}\overline{a_{1}}b_{3}\overline{b_{3}}\\ a_{2}\overline{a_{2}}b_{1}\overline{b_{1}}&a_{2}\overline{a_{2}}b_{2}\overline{b_{2}}&a_{2}\overline{a_{2}}b_{3}\overline{b_{3}}\\ a_{3}\overline{a_{3}}b_{1}\overline{b_{1}}&a_{3}\overline{a_{3}}b_{2}\overline{b_{2}}&a_{3}\overline{a_{3}}b_{3}\overline{b_{3}}\end{array}\right)

The elements of this matrix are again the terms on RHS in (3).

We can thus call each of them

\displaystyle B_{ij}=a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}

The last term in (1) is

\displaystyle -(|a_{1}\overline{b_{2}}-a_{2}\overline{b_{1}}|^{2}+|a_{1}\overline{b_{3}}-a_{3}\overline{b_{1}}|^{2}+|a_{2}\overline{b_{3}}-a_{3}\overline{b_{2}}|^{2})\ \ \ (4)

This time we use two matrices to organize the terms in (4).

\displaystyle \left(\begin{array}{ccc}0&a_{1}\overline{a_{2}}b_{1}\overline{b_{2}}&a_{1}\overline{a_{3}}b_{1}\overline{b_{3}}\\ a_{2}\overline{a_{1}}b_{2}\overline{b_{1}}&0&a_{2}\overline{a_{3}}b_{2}\overline{b_{3}}\\ a_{3}\overline{a_{1}}b_{3}\overline{b_{1}}&a_{3}\overline{a_{2}}b_{3}\overline{b_{2}}&0\end{array}\right)

and

\displaystyle \left(\begin{array}{ccc}0&a_{1}\overline{a_{1}}b_{2}\overline{b_{2}}&a_{1}\overline{a_{1}}b_{3}\overline{b_{3}}\\ a_{2}\overline{a_{2}}b_{1}\overline{b_{1}}&0&a_{2}\overline{a_{2}}b_{3}\overline{b_{3}}\\ a_{3}\overline{a_{3}}b_{1}\overline{b_{1}}&a_{3}\overline{a_{3}}b_{2}\overline{b_{2}}&0\end{array}\right)

And we thus define elements of the first and the second matrix respectively as

\displaystyle C_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}

\displaystyle D_{ij}=a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}

where we define \sigma_{ij} as

\displaystyle \sigma_{ij}=0\ \mathrm{if}\ i=j

\displaystyle \sigma_{ij}=1\ \mathrm{if}\ i\not=j

Now let

\displaystyle T_{ij}=A_{ij}+D_{ij}-B_{ij}-C_{ij}

Therefore,

\displaystyle T_{ij}=A_{ij}(\delta_{ij}+\sigma_{ij})+D_{ij}-B_{ij}(\delta_{ij}+\sigma_{ij})-C_{ij}

where we have used \delta_{ij}+\sigma_{ij}=1 (\delta_{ij} is the Kronecker delta)

And so,

\displaystyle T_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\delta_{ij}+a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}+a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}

\displaystyle -a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\delta_{ij}-a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}-a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}

or

\displaystyle T_{ij}=a_{i}\overline{a_{i}}b_{i}\overline{b_{i}}-a_{i}\overline{a_{i}}b_{i}\overline{b_{i}}=0

Since each T_{ij} is zero the sum

\displaystyle \sum_{i,j=1}^{n}T_{ij}=0

which automatically implies the Lagrange Identity in \mathbb{C}.

Published in: on April 29, 2009 at 6:04 pm  Leave a Comment  
Tags: , ,