$2^{prime} = {prime}*x+1$

Question

I've stumbled across something I think is true, but I don't know how to show it. It started to haunt me.

My conjecture is that for every prime $p$, if you look at $2^{p-1}-1$ this is divisible by $p$. For example: $p=7$. $\frac{2^6 - 1}{7} = \frac{64 -1}{7} = \frac{63}{7}= 9$ Another $p=29$: $\frac{2^{28} -1}{29} = \frac{268435455}{29} = 9256395$

It seems to only hold for primes. And I suspect it has some relation with that $2^{p-1}$ has only $2$ as prime factor?

It would be greatly appreciated if someone would be so kind to point me in the right direction. I'm not sure how to show to myself this indeed always holds.

Answer 1

Let $p$ be a prime and $a$ be an integer that is not divible by $p$.

Then the function $\phi: \mathbb{Z}_p\to\mathbb{Z}_p$, $\phi(n) = a\cdot n$ is bijective.

Indeed, if $\phi(x) = \phi(y) \Rightarrow ax=ay$

How $a$ is not divisible by $p$, then $a\ne 0$ in $\mathbb{Z}_p$ and how $\mathbb{Z}_p$ is a field, exists $a^{-1}\in\mathbb{Z}_p$. Hence

$ax=ay \Rightarrow a^{-1}ax=a^{-1}ay \Rightarrow x=y$. So $\phi$ is injective.

From $\phi(a^{-1}x) = aa^{-1}x = x$, we deduce that $\phi$ is surjective and therefore bijective.

How $\phi(0)=0$, then the restriction $\hat{\phi}: \mathbb{Z}_p-\lbrace 0\rbrace \to\mathbb{Z}_p-\lbrace 0\rbrace$, $\hat\phi(n) = a\cdot n$ is bijective.

So, in $\mathbb{Z}_n$, we have

$1\cdot 2\cdot \ldots \cdot(p-1) = \hat\phi(1)\cdot\hat\phi(2)\ldots\cdot\hat\phi(p-1) = a\cdot 1\cdot a \cdot 2\cdot\ldots\cdot a \cdot (p-1) = \\ a^{p-1} \cdot 1\cdot 2\cdot \ldots \cdot(p-1)$

$\Rightarrow \left(a^{p-1}-1\right)\cdot1\cdot 2\cdot \ldots \cdot(p-1) = 0$.

$\mathbb{Z}_p$ is a field and $1\cdot 2\cdot \ldots \cdot(p-1)\ne 0$, then $a^{p-1}-1=0$ in $\mathbb{Z}_p$.

Therefore $p|a^{p-1}-1$ (Fermat's Little Theorem)

In particular, for $a=2$, we have $p|2^{p-1}-1$ for all odd prime $p$.

Answer 2

We need to prove that $a^p\equiv a \pmod p ,\ \forall a$ such that $p\not{|} a$.

Proof by induction:

The claim is obviously true for $a=1$. Since $p\not{|}a$, $a\equiv 1,2,\cdots,\ p-1\pmod p$, and thus it is enough for the claim to hold for $a=1,2,\cdots,\ p-1$ to hold in general.

Let the claim holds for $a=1,2,\cdots,\ k$, for some $k$ with $1\le k\le p-2$. Then, note that $$(k+1)^p =\sum_{j=0}^p \binom{p}{j}k^j.$$ Now note that $p|\binom{p}{j}$ whenever $1\le j\le p-1$. To see this note that if $\binom{p}{j}\equiv k\pmod p$, then $p!\equiv j!(p-j)!k\pmod p\implies j!(p-j)!k\equiv 0 \pmod p\implies k\equiv 0\pmod p$ since $j!, (p-j)!$ are relatively prime to $p$ whenever $1\le j\le p-1$.

Thus, we get $$(k+1)^p\equiv 1+k^p \pmod p\equiv 1+k\pmod p$$ where the last step follows from induction hypothesis.$\blacksquare$