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

My Question is the above question:

Let $p,q\in \mathbb{P}$ and $r\in\mathbb{Z}$ with $r\not\equiv 1 \mod p$ and $r^q\equiv 1 \mod p$. Then $p\equiv 1 \mod q$. Hence $q|p-1$.

I was calculating to get a proof, but i didn't get it. So maybe someone knows the solution. Thanks.

share|cite|improve this question
The linear-algebra and numerical-linear-algebra tags seem to be a little out of place... – Emily Aug 10 '12 at 18:06
From $r^q\equiv 1\pmod{p}$, we conclude that the order of $r$ modulo $p$ divides $q$. But since $q$ is prime and the order is not $1$, the order must be $q$. Thus $q$ divides $p-1$. – André Nicolas Aug 10 '12 at 18:14

$r^{p-1} \equiv 1 \pmod p \quad \quad \text{Fermat's Theorem}$
and $r^q \equiv 1 \pmod p$
$\implies q|p-1$

share|cite|improve this answer
Thanks. Didn't remind Fermats Theorem. – Peter Aug 10 '12 at 18:40

Let $d=\gcd(p-1,q)$. Then there exist integers $x$ and $y$ such that $(p-1)x+qy=d$. From $r^{p-1}\equiv 1\pmod p$ (Fermat) and $r^p\equiv 1\pmod{p}$ we conclude that $r^d\equiv 1 \pmod{p}$.

We know $r\not\equiv 1\pmod{p}$, so $d \ne 1$. The only other divisor of $q$ is $q$.

share|cite|improve this answer

Let $f$ be the least positive integer such that $r^f \equiv 1$ (mod $p$). Let $q = fk + l$, where $0 \leq l < f$. Since $r^l \equiv 1$ (mod $p$), $l = 0$. Hence $f|q$. Since $q$ is prime, $q = f$. Since $r^{p-1} \equiv 1$ (mod $p$) by Fermat, the similar argument as above shows $f|p - 1$, hence $q|p - 1$ and we are done.

share|cite|improve this answer
Thank you very much. – Peter Aug 10 '12 at 18:41

Hint $\ $ The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:r^n \equiv 1\:$ is closed under positive subtraction, i.e.

$$\rm \color{#C00}n>\color{#0A0}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#C00}{r^n} \equiv r^{n-m}\, \color{#0A0}{r^m} \equiv r^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$

So, by the Theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \! $ := order of $\rm\,r.$ Therefore $\,\ell\,$ divides the prime $\rm\,q\in\cal O,\:$ thus $\,\ell = 1\,$ or $\rm\,\ell = q.\:$ But if $\ \ell = 1\,$ then $\rm\,r^1\equiv 1\,$ contra hypothesis. Thus $\rm\ \ell = q.\:$ By little Fermat $\rm\,p\!-\!1\in \cal O,\:$ hence $\rm\,q\,$ divides $\rm\,p\!-\!1\,$ by the Theorem.

Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\ n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$

Proof $\ $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \ $ QED

For more on the key innate structure see this post on order ideals and denominator ideals.

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.