Prove that if $q | 2^{p} - 1$ then $q \mid 2^{q-1} - 1$ and $q = 1+2kp$ 
Let a prime $p\ge 3$ and let $q$, a prime such that $q \mid 2^p - 1$. prove that $q \mid 2^{q-1} - 1$ and show that it has the form $q = 1+2kp$,  $k\in\mathbb N$.

Note: I have been asked to show first that $q\mid \gcd \left( 2^p - 1, 2^{q-1} -1 \right)$ and to use the lemma:$ \gcd \left( N^a -1 , N^b - 1 \right) = N^{\gcd(a,b)} - 1$
So I followed the hint:
$$\gcd\left( 2^p -1, 2^{q-1}-1 \right) = 2^{\gcd(p,q-1)} - 1$$
Then we have to show that $q\mid 2^{\gcd(p,q-1)}$.
Now, since $p$ is a prime: $\gcd(p,q-1)\in\{1,p\}$.  If $\gcd(p,q-1) = p$ then it works out since $q\mid 2^p - 1$ by definition. But, it may be that $\gcd(p,q-1) = 1$. Isn't it? That would imply $q=1$ - A contradiction to the primality of $q$.
I guess I need to somehow eliminate the option that $\gcd(p,q-1)=1$.
How?
 A: You are assuming that $2^p\equiv1\pmod q$. But you know that $2^{q-1}\equiv1\pmod q$. It is easy to see that if $k$ is the smallest natural such that $2^k\equiv1\pmod q$, then every natural $N$ such that $2^N\equiv1\pmod q$ is a multiple of $k$. But, clearly, $k\neq1$. Therefore, since $p$ is prime, $k=p$ and so $p\mid q-1$. In other words, $q=1+Mp$ for some natural number $M$. If $M$ was  odd, $q$ would be even. But the only even prime is $2$ and $2\nmid2^p-1$. Therefore, $q$ is odd and $M=2k$ for some natural $k$.
A: Given that $q | 2^{p} - 1,$ it follows that $q$ is a primitive factor of the $pth$ Mersenne number. Hence, $q$ must be of the form $1 + 2kp$ as all primitive prime divisors of Mersenne numbers of prime index have this form.
Finally, as long as $q$ is greater than $3$ (which is the case here), it must divide $M_{q-1}$; and so, $q | 2^{q-1} - 1.$ 
Remark: The latter divisibility property is not always true for Lucas sequences in general; for example, in the Fibonacci sequence, $q > 5 $ will divide either F_{q-1} or F_{q+1} but not both.
