## 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)$

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}

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}$.