# $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?

• 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)$ Sep 15, 2010 at 13:54
• That was neat. болшое спасибо, Такенов. Sep 15, 2010 at 14:04

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.