When is $(a+b)^n \equiv a^n+b^n$?

Solution 1:

This is sometimes called the beginner's binomial theorem or Freshman's dream. It holds in fields of characteristic $n$, which only exist if $n$ is prime.

It holds in particular modulo $n$ (for $n$ prime) because most of the binomial coefficients are divisible by $n$ in this case, so modulo $n$ they all vanish and the binomial formula simplifies to $$(a+b)^n = \sum_{i=0}^n \binom{n}{i} a^i b^{n-i} = a^n + b^n \mod n.$$

Note that if $n$ is not prime, the statement about binomial coefficients is not true. For example $\binom{4}{2} = 6$ is not divisible by $4$.

Solution 2:

Fermat's Little Theorem states that:

For any integer $k$ and any prime $p$, we have $k^{p} \equiv k \mod p$.

Suppose $p$ is prime, and we have integers $a$ and $b$.

If you consider $k = a + b$, which is still an integer, then the above says:

$(a+b)^{p} \equiv a+b \mod p$.

Note also that $a^{p} \equiv a \mod p$ and $b^{p} \equiv b \mod p$; so $a^p + b^p \equiv a + b \mod p$.

Combining the previous two lines yields your equivalence:

$$(a+b)^{p} \equiv a+b \mod p \equiv a^p + b^p \mod p$$

Note 1: Sometimes one uses a fact like the one in your question to prove Fermat's Little Theorem; this is not the only proof, but do be sure that you don't find yourself reasoning circularly!

Note 2: It is not too hard to conjecture that Fermat's Little Theorem yields equivalence for prime exponents. We can even check the first couple of cases by hand. Let $n$ be an integer.

$p = 2$: This says that $n^2 \equiv n \mod 2$, i.e., $2$ divides $n^2 - n = n(n-1)$, which is clearly the case: The product of two consecutive integers must be divisible by two, because one of them is even!

$p = 3$: This says that $n^3 \equiv n \mod 3$, i.e., $3$ divides $n^3 - n = n(n^2 - 1) = (n-1)n(n+1)$, which should also be clear: Any three consecutive integers has one of them divisible by three, and so their product is divisible by $3$.

$p = 4$: This says that $n^4 \equiv n \mod 4$. But this is false already for $n=2$.

$p = 5$: You can work this one out with a bit of factoring and some case work, and then find another counterexample for $p = 6$. At that point, you may conjecture that for $p > 1$, Fermat's Little Theorem holds only at the primes.