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

Question

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.

Answer 1

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$.

Answer 2

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$.

Answer 3

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.

Answer 4

Fermat's little theorem states that if $p$ is a prime, then $(a^p-a)$ is an integer multiple of $p$ for any integer $a$, which can be expressed as: $a^{p} \equiv a \pmod p$. Since $a^p-a=a(a^{p-1}-1)$, then Fermat's little theorem is equivalent to the statement that $(a^{p-1}-1)$ is an integer multiple of $p$, if $a$ is not divisible by $p$. It can be expressed as: $a^{p - 1} \equiv 1 \pmod p$. If $a=2$, this condition is fulfilled since $2$ is not equal to $p$. Thus, $2^{p} \equiv 2 \pmod p$. Or, $(2^{p}-2)$ is divisible by $p$. In addition, this can also be proven using one of theorems about Mersenne numbers. In WIKIPEDIA it is stated as "If $p$ is an odd prime, then every prime $q$ that divides $(2^p − 1)$ must be $1$ plus a multiple of $2p$. This holds even when $(2^p − 1)$ is prime" under Mersenne prime.