if $q \mid (2^p -1)$ then $q \equiv 1 \pmod{p}$

Question

Let $p,q$ be two primes, if $q \mid (2^p -1)$ then $q \equiv 1 \pmod{p}$.

My work: So far what i have done is noticed that since $q \mid (2^p - 1)$ we have that $2^p \equiv 1 \pmod{q}$ Therefore, $ord_{q}(2)\mid p$ and since $p$ is prime we must have that $ord_{q}(2)=p$. Similarly $ord_{q}(2) \mid \phi(q)=q-1$ and so $p\mid(q-1)$ in other words $q \equiv 1 \pmod{p}.$

The previous question on my homework asked me to prove,

If $m=a^n-1$, where $a,n$ are positive integers. Show that $ord_{m}(a)=n$

The question I proved above tells me to use this result which makes me think there is an error in my proof since I didn't seem to use it. Could someone take a look at my proof and let me know if it holds or not, thanks!

Answer 1

Your proof is correct, assuming ...

---

1. You know how to prove "Therefore, $ord_q(2)\mid p$" part. With more details if $\gcd(a,q)=1$ $$a^n \equiv 1 \pmod{q} \Rightarrow ord_q(a)\mid n$$ Let's assume this is not true and apply Euclidean division, i.e. $n =ord_q(a)\cdot t + r$ where $0< r < ord_q(a)$. Then $$1 \equiv a^n \equiv a^{ord_q(a)\cdot t + r}=a^r \pmod{q}$$ and because $0< r < ord_q(a)$, this contradicts the definition of $ord_q(a)$. So $r=0$.

---

2. You show that (as per the comment @Max left), given $a=2$ and $q$ is prime, $ord_q(2)>1$. Otherwise $2\equiv 1 \pmod{q} \Rightarrow q \mid 1$.