Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
6  
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
1  
That was neat. болшое спасибо, Такенов. –  Weltschmerz Sep 15 '10 at 14:04
add comment

1 Answer

up vote 8 down vote accepted

$\rm\displaystyle\;\ 2^p,\; 2^{q-1} \equiv 1 \;\Rightarrow\; 2^{gcd(p,q-1)} \equiv 1\ (mod\ q)\;\Rightarrow\; gcd(p,q-1) = p\; $ (not $1$ else $\rm \:q|2^1-1\:$)

Said in group theory language: if an element $\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\:|\:n\;$. Compare this ring-theoretic proof to the ubiquitous group-theoretic proof using Lagrange's theorem.

Here is a simple additive example: the order ideal of a fraction is the denominator ideal $\rm\; \{n : n\: x \in \mathbb Z \:\}\:$. Here the analogous result is that 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 possible 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 to my sci.math posts for much further discussion on this and related topics.

share|improve this answer
add comment

Your Answer

 
discard

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.