It is enough to show that certain multiple of $q$ is equal to $2^k-1$. In other words $q$ divides $2^k-1$. Consider the numbers: $2,2^2,\ldots,2^q,2^{q+1}$. Since there are $q+1$ of them and number of residues modulo $q$ is $q$ then some two of them give the same residue. Let it be $2^s$ and $2^t$ where $1\leq s<t\leq q+1$. \[2^t\equiv 2^s \pmod q\] \[2^{t}-2^s \equiv 0 \pmod q\] \[2^{s}(2^{t-s}-1)\equiv 0\pmod q\] Because $q$ is odd we have \[q|2^{t-s}-1\]