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.

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|improve this question
    
The linear-algebra and numerical-linear-algebra tags seem to be a little out of place... –  Arkamis Aug 10 '12 at 18:06
1  
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

4 Answers 4

$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|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|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|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|improve this answer

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.