# If the order divides a prime P then the order is 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?

-
Let $k$ be minimal natural number, such that $2^k\equiv 1\mod{q}$. Then its easy to see that $k|p$ and $k|(q-1)$(from the little theorem of Fermat). But, because $p$ is prime, there just 2 cases: 1)$k=1$ - impossible. 2)$k=p\to p|(q-1)$ – Nurdin Takenov Sep 15 '10 at 13:54
That was neat. болшое спасибо, Такенов. – Weltschmerz Sep 15 '10 at 14:04

Hint $\rm\displaystyle\,\ mod\,\ q\!:\,\ 2^p,\, 2^{q-1}\! \equiv 1 \;\Rightarrow\; 2^{gcd(p,q-1)} \equiv 1\,\Rightarrow\; gcd(\color{#c00}p,\,q\!-\!1) = \color{#c00}p\;$ (not $\color{#c00}1$ else $\rm \,q\mid 2^{\color{#c00}1}\!-1\:$)
Said in group theory language: if $\,g\ne 1$ has order dividing a prime $\,\rm p\,$ then it must have order $= \rm 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.