Q:

Proof that $2^p-2$ is divisible by $p$?

I'd like to prove that $2^p-2$ is divisible by $p$ when $p$ is prime. This is true for thousands of primes $p$ that I tested, but I can't figure out or find a proof.

A:

A minimal proof,
$$2^p -2 = \sum_{k=1}^{p-1} \binom{p}{k}$$
and note that that each term 
$$ \binom{p}{k} = \frac{p!}{(p-k)! k!}$$ 
is divisible by $p$. Here, the fact that $p$ is prime is essential: since $p$ is prime, it will be relatively prime to any $l$, $1\le l \le p-1$, and so relatively prime with $(p-k)! k!$. Now, $p$ divides the product ($p!)$ of the integers $(p-k)! k!$ and $\frac{p!}{(p-k)! k!}$, while being relatively prime to $(p-k)! k!$ so it divides  $\frac{p!}{(p-k)! k!}= \binom{p}{k}$ for every $1\le k \le p-1$. 
$\bf{Added:}$ There are other proofs in the linked provided that use the action of the group $\mathbb{Z}/p$ on a set of necklaces, a "counting orbits" argument. So let's prove in a similar way that $\binom{p}{k}$ is divisible by $p$. Question: how to group the subsets with $k$ elements of ${0,1,\ldots, p-1}$ in groups of $p$? Put in the same group a subset $\{a_1, \ldots, a_k\}$ and all its shifts modulo $p$ by some $s$, where $1\le s \le p-1$. Note that we do get indeed $p$ different subsets: for if 
$$\{a_1+s, \ldots, a_k+s\} = \{a_1+t, \ldots, a_k+t\}$$ then taking the sum on both sides we get
$$(\sum_{i=1}^k a_i)+ k s = (\sum_{i=1}^k a_i) + kt \mod p$$
and, since $p$ is prime and $1\le k \le p-1$, we must have $s = t \mod p$.

A:

I report here one of the proofs Wikipedia gives of Fermat's little theorem, which is equivalent to your statement. I find this to be the most accessible. You are free to go read and/or copy other proofs as answers.
First, we need to know that:
$$(x+y)^p=\sum_{i=1}^p\binom{p}{i}x^iy^{p-i}.$$
That can be proven by induction for arbitrary integers $k$ as exponents, not just primes $p$.
Using this, and reducing modulo $p$ the above equation, we see that the only terms on the right that remain are $x^p+y^p$, since all other coefficients are divisible by $p$ and hence zero modulo $p$. That is:
$$(x+y)^p\equiv x^p+y^p\pmod p.$$
Let us now come to our claim:
$$a^p\equiv a\pmod p,$$
for any integer $a$ and prime $p$. We prove this by induction. The base case $a=1$ is trivial. Let us assume it holds for $k$. Then:
$$(k+1)^p\equiv k^p+1^p\equiv k+1\pmod p,$$
where the first passage is what we proved with the binomial expansion at the start of this proof, and the second passage is base case + induction hypothesis. So we have proved the $k+1$ case assuming the $k$ case and the $1$ case. Hence, this holds for any integer $a$, including, in particular, $2$.

A:

This follows from Fermat's little theorem readily, as Clement C. pointed out in a comment.
If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p - 1} \equiv 1 \pmod p$. Since $a^p = a^{p - 1} a$, then $a^p \equiv 1a \pmod p$ (I write "$1a$" rather than just "$a$" for extra clarity). If $a = 2$, then we have $2^p \equiv 2 \pmod p$ and $2^p - 2 \equiv 0 \pmod p$, which is another way of saying what you have already observed.

