Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 11 down vote accepted

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.

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.