4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The linear-algebra and numerical-linear-algebra tags seem to be a little out of place... $\endgroup$ – Emily Aug 10 '12 at 18:06
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Aug 10 '12 at 18:14
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks. Didn't remind Fermats Theorem. $\endgroup$ – Peter Aug 10 '12 at 18:40
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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