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.