Binomial Expansion Using Modular Arithmetic

 1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5    10    10    5    1

1    6    15    20    15    6    1

1    7    21    35    35    21    7    1

Above we see the beginning of Pascal's Triangle, that is of great assistance is working out the coefficients of the terms in the binomial expansion of $(a+b)^n$ for various positive integer values of $n$. The first line corresponds to $n=0$, then $n=1$, $n=2$ and so on. For example:

$$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$$ A common mistake that's made by beginner's is to write the following: $$(a+b)^n=a^n+b^n$$ What is regarded as a mistake actually turns out to true for certain values of $n$ when modular arithmetic is involved.

Let's consider mod 2 where only two numbers exist: 0 and 1. Any numbers larger than 1 reduce to either 0 or 1. Thus $2 \equiv 0 \, mod \, 2$ and $3 \equiv 1 \, mod \, 2$ etc. Let's look at the expansion of $(a+b)^2$ in this light. We have:

$$\begin{align} (a+b)^2 &=a^2+2ab+b^2\\ &=a^2+b^2 \end{align}$$ In the case of mod 2, the $2ab$ term must equal zero What about mod 3? The only numbers here are 0, 1 and 2 with $3 \equiv 0 \,mod \,3$. The binomial expansion for the case of $n=3$ becomes: $$\begin{align} (a+b)^3 &=a^3+3a^3b+3ab^2+b^3\\ &=a^3+b^3 \end{align}$$ Here the $3a^2b$ and $3ab^2$ terms equal zero. We seem to on a roll. Let's consider the case of $n=4$ or mod 4. Here the only numbers are 0, 1, 2 and 3 with $4 \equiv 0 \, mod \, 4$, $5 \equiv 1 \, mod \, 4$, $6 \equiv 2 \, mod \, 4$ and so on. Thus we have: $$\begin{align} (a+b)^4 &= a^4 + 4a^3b+6a^2b^2+4ab^3+b^4\\ &=a^4 + 2a^2b^2+b^4 \end{align}$$ In this case, things don't quite work out because the middle term $6a^2b^2$ after conversion to $2a^2b^2$.

What about the case of $n=5$ or mod 5? Here the numbers are 0, 1, 2, 3 and 4 and the expansion of $(a+b)^5$ works out as follows:

$$\begin{align} (a+b)^5 &= a^5 + 5a^4b + 10a^3b^2+10a^2b^3+5ab^4+b^5 \\ &=a^5+b^5 \end{align}$$ The central terms all disappear because $5 \equiv 0 \, mod \,5$ and $10 \equiv 0 \, mod \, 5$. If we consider the case of mod 6, the simplification fails but works again for mod 7. The generalisation from all of this is that if $p$ is prime and we are working with mod $p$ then the following always holds true: $$(a+b)^p=a^p+b^p$$ I'm thankful to this YouTube video for informing me of this interesting twist on the binomial expansion.