Let $p$ be prime number, and d is the natural number. Prove that if $d\mid 2^p−1$, then $p\mid d−1$

Question

Let $p$ be prime number, and d is the natural number. Prove that if $d\mid 2^p−1$, then $p\mid d−1$.

I'm looking on proof number 3 mentioned there and few things are unclear for me: https://en.wikipedia.org/wiki/Mersenne_prime

How it was concluded that $q$ is a factor of $2^{pc}-1$ for all positive integers $c$. Fermat theorem says that $p\mid a^{q-1}-1$ if $q$ is not a divisor of $a$, in this case, let $b=a^c$ and it's true indeed, but in case of this proof exponent is $p$, not $p-1$.

Second thing is why is there mentioned, that $q$ is not a factor of $2^1-1$ and how it leads to conclusion that $p$ is smallest positive integer $x$ that $q$ is a factor of $2^x-1$.

Answer 1

We know that $2^p\equiv1\pmod q$. But then, for any natural number $c$,$$2^{pc}=(2^p)^2\equiv1^c=1\pmod q.$$

Now, let $n$ be the smallest natural number such that $q\mid 2^n-1$. You know that $n\neq1$. Suppose that $n\nmid p$. Then $p$ can be written as $nc+r$, for some $r\in\{1,2,\ldots,n-1\}$. But then$$1\equiv2^p=2^{nc+r}\equiv2^r\pmod q,$$which is impossible, since $n$ is the smallest natural with that property and $r<n$. So, $n\mid p$. Since $p$ is prime and $n\neq1$, $n=p$.

Answer 2

To show that a prime factor $\ q\mid 2^p-1\ $ , where $\ p $ is a prime number , must be of the form $\ kp+1\ $ , the key is to consider the smallest positive number $u$ , such that $$2^u\equiv 1\mod q$$ holds, the so-called order of $2$ modulo $q$. Since $$2^p\equiv 1\mod q$$ holds, we can conclude $u\mid p$.

Hence, we have $\ u=1\ $ or $\ u=p\ $. Since $\ u=1\ $ can be ruled out, we must have $\ u=p\ $

Since $q$ must be odd, we also have $$2^{q-1}\equiv 1\mod q$$ because of Fermat's little theorem. Since $u$ must divide $q-1$, we finally can conclude $p\mid q-1$.