5

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.

fitzmerl duron
  • 1,495
Casper Thalen
  • 51
  • 5
    This is Euler's or Fermat's Little theorem. – Randall Feb 20 '18 at 00:09
  • 1
    Start here: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem – Randall Feb 20 '18 at 00:10
  • And not restricted to $2$ - it is true for all positive integers – Henry Feb 20 '18 at 00:14
  • Do we need odd primes? Because $2^{2-1} - 1 = 1 \not \equiv 0 (\mod 2)$ – AJY Feb 20 '18 at 00:15
  • The base needs to be relatively prime to the modulus. You cannot use all positive integers. – Randall Feb 20 '18 at 00:19
  • Yeah... either $b = kp$ or $b$ is relatively prime to $p$. If $b$ is relatively prime to $p$ we have $b^{p-1} \equiv 1 \mod p$. For any $p$ and any $b$ that is not a multiple of $p$. If $b$ is* a multiple of $p$ then $b^m = (k*p)^m \equiv 0 \mod p$ for any power and the result rather trivially doesn't work. – fleablood Feb 20 '18 at 00:27
  • Liebnitz (17th century AD) asserted that if $2\leq n\in \Bbb N$ and $2^n-1$ is divisible by $n+1$ then $n+1$ is prime, but later admitted his mistake. $341=(11)(31)$ is not prime and $341$ divides $2^{340}-1.$ – DanielWainfleet Feb 20 '18 at 06:11

2 Answers2

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

Tiago Emilio Siller
  • 1,116
1

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$

Samrat Mukhopadhyay
  • 16,277