# Let $p$ be an odd prime and $q$ be a prime such that $q \mid 2^p-1$ Prove that $p \mid \frac{q-1}2$

Let $$p$$ be an odd prime and $$q$$ be a prime such that $$q \mid 2^{p}-1.$$ Prove that $$p \mid \dfrac{q-1}{2}.$$

My attempt: By Euler's Theorem, $$2^{q-1} \equiv 1 (\text{mod} \ q),$$ so $$2^{\frac{q-1}{2}} \equiv \pm 1(\text{mod} \ q).$$ How do I relate this to the order of $$2$$ modulo $$q?$$

Appreciate any advice, thank you.

## 2 Answers

If ord$$_q2=d>1$$

$$d$$ must divide $$g=(p,q-1)$$

If $$p\nmid (q-1),g=1\implies d|1,d=?$$

Else $$p|(q-1)$$

As $$q-1$$ is even, odd $$p$$ will divide $$(q-1)/2$$ as well

$$2^{p-1}-1 ≡0\mod p$$$$2^p-2≡0\mod p$$$$2^p-1≡1\mod p=kp+1$$

$$q|2^p-1$$$$q| kp+1$$$$kp|q-1$$

$$q-1$$is even so p must divides the odd $$\frac{q-1}{2}$$