Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

Question

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?

Answer 1

Hint: The binomial theorem states that $$ (a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k} $$ where $$ \binom{n}{k}=\frac{n!}{k!(n-k)!} $$ Can you prove that $n$ divides $\binom{n}{k}$ for $1\leq k\leq n-1$? This is where $n$ being prime is needed.

Answer 2

From Euler's theorem,we know that:

$$a^n \equiv a \pmod n$$ $$b^n \equiv b \pmod n$$ $$(a+b)^n \equiv a+b \pmod n$$

So,we conclude that:$$ (a+b)^n \equiv a^n+b^n \pmod n$$