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.

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

From the assumptions above, I am trying to prove that $q=1+kp$ for some integer $k$ and that $k$ is even.

My thoughts thus far: Since $a^p\equiv 1$ mod $q$, I know that by a corollary of Fermat's little theorem that $a^p\equiv a$ mod $q$. So $q|a$ or $q|a^{p-1}-1$, but $q\nmid a$, so $q|a^{p-1}-1$.

And this is where I'm not sure where to go. If I can prove that $q\equiv 1$ mod $p$, then the conclusion would follow, and hopefully $k$ being even would follow as well. But I'm not sure.

Thoughts are greatly appreciated!

share|cite|improve this question
up vote 1 down vote accepted

This is homework, so I'll get you started.

We must have $q\not\mid a$, as otherwise $a^p\equiv 0\not\equiv 1\mod{q}$. Let $d$ be the order of $a$ modulo $q$, that is, the least positive integer such that $a^d\equiv 1\mod{q}$.

From here, what can we say about $d$? We have two conditions: the given one $a^p\equiv 1\mod{q}$ and Fermat's Little Theorem $a^{q-1}\equiv 1\mod{q}$. What do these tell us about $d$?

Once we know that $q=kp+1$ for some integer $k$, what happens if $k$ is odd?

share|cite|improve this answer
Excellent, thank you! – madisonfly Nov 26 '12 at 3:37

Let $b$=$a$mod$q$. By considering the order of $a$ in $U_q$, we find that $|a|$ divides $q-1$. Since, |a| is different from 1 and divides p. Thus, |a|=p. Hence p|(q-1). Now it follows that q=1+kp

K has to be even. If k is odd we will find that 1+kp is even. This contradicts the fact that q is odd.

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.