$q\mid 2^p-1\Rightarrow p\mid q-1$ [order divides prime $p \Rightarrow$ order $= p$ or $1$]

I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. I've tried a few cases and it seems to be true. How can it be proved?

Hint $\!\bmod q\!:\ 2^p,\, 2^{q-1}\! \equiv 1 \;\Rightarrow\; 2^{\gcd(p,q-1)} \equiv 1\,\Rightarrow\; \overbrace{\gcd(\color{#c00}p,\,q\!-\!1) = \color{#c00}p}^{\textstyle \Rightarrow\ p\mid q\!-\!1\ }\, $ (not $\color{#c00}1$ else $\rm \,q\mid 2^{\color{#c00}1}\!-1\:$)

Or $\!\bmod q\!:\ 2^p\equiv 1\ \,\smash[t]{\overset{\rm\color{#0a0}{o\,r}}\Rightarrow}\,\ 2\,$ has $\:\!\color{#c00}{\rm order }\,k\mid p\Rightarrow k = \color{#c00}p\; $ (not $\color{#c00}1$ else $\rm \,q\mid 2^{\color{#c00}1}\!-1)\,$ so by little Fermat $\ \bmod q\!:\,\ 2^{q-1}\equiv 1\,\ \smash[t]{\overset{\rm\color{#0a0}{o\,r}}\Rightarrow}\,\ \color{#c00}p\mid q-1,\,$ by $\,\rm\color{#0a0}{o\,r} =\,$ mod order reduction (or this Corollary).

Said in group theory language: if $\,g\ne 1$ has order dividing a prime $\,p\,$ then it must have order $= p.\,$ In ring theory language: if a principal ideal$\;\ne 1$ contains an irreducible element then that element generates the ideal (which is why the minimal polynomial is sometimes called the "irreducible polynomial"). $ $ Here the group / ideal is simply the so-called order ideal $\rm\; \{n : x^n = 1 \},\,$ which, being nonempty and closed under subtraction, comprises a subgroup / ideal of $\:\mathbb Z.\,$ The Euclidean algorithm implies that ideals in $\mathbb Z$ are principal, so every element of a nonzero ideal is a multiple of the least positive element. For an order ideal this simply says that every "possible" order is a multiple of the least possible order $\,\rm m,\ $ i.e. $\rm\; x^n = 1 \,\Rightarrow\, m\mid n.\,$ Compare this ring-theoretic proof to the ubiquitous group-theoretic proof using Lagrange's theorem.

An additive example an order ideal is a denominator ideal $\rm\ \{n : n\: x \in \mathbb Z \,\}$ of a fraction $\,x\in\Bbb Q.\,$ Here the above yields: if a proper fraction can be written with a prime denominator then it is the least possible denominator (in the multiplicative sense), i.e. it divides ever other denominator.

Denominator ideals and fractional ideals can yield significant number-theoretical simplifications - in much the same way that fractional arithmetic often serves to simplify integer arithmetic in elementary number theory. For example, see my post on irrationality proofs using the denominator ideal or, more generally, see my proof employing Dedekind's conductor ideal - a sort of universal denominator for an entire extension ring. Follow the links there for much further discussion.