Lesson 5

We will need one simple algebraic fact. If \(p\) is prime, then \[(a+b)^{p} \equiv a^{p}+b^{p} \pmod p \ .\] Indeed, by the binomial formula, \[(a+b)^{p}=a^{p}+\binom{p}{1}a^{p-1}b+\binom{p}{2}a^{p-2}b^{2}+\dotsb+\binom{p}{p-1}ab^{p-1}+b^{p}.\] For \(1 \le i \le p-1\), the coefficient \(\binom{p}{i}\) is divisible by \(p\): in \[\binom{p}{i}=\frac{p!}{i!(p-i)!},\] the numerator has one factor \(p\), while neither \(i!\) nor \((p-i)!\) is divisible by \(p\). Therefore all middle terms disappear modulo \(p\).

This identity is often called the freshman's dream: in usual arithmetic it is false, but modulo a prime it becomes true.