Proof for: $(a+b)^{p} \equiv a^p + b^p \pmod p$

Your second idea is good, so let's work a little bit on it: We have that $(a+b)^p=a^p+b^p+\sum\limits_{k=1}^{p-1}{p\choose k}a^{k}b^{p-k}$. Obviously it is enough to show that each term of this sum is divisible by $p$ in order to get that the whole sum is $\equiv 0\mod p$.

So why is that the case? For $1\leq k\leq p-1$ we have that ${p\choose k}=\frac{p\cdot (p-1)!}{k!(p-k)!}$ and since $p$ is prime, no factor in the denominator divides $p$, so the denominator does not divide $p$ at all: Hence we have that already $\frac{(p-1)!}{k!(p-k)!}$ is integer and so $p\mid{p\choose k}$. Of course then ${p\choose k}a^kb^{p-k}$ is divisible by $p$ and hence the whole sum is too.

First of all, $a^p \equiv a \pmod p$ and $b^p \equiv b \pmod p$ implies $a^p + b^p \equiv a + b \pmod p$.

Also, $(a+b)^p \equiv a + b \pmod p$.

By transitivity of modulo, combine the above two results and get $(a+b)^p \equiv a^p + b^p \pmod p$.

Done.