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.

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|improve this question

2 Answers 2

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|improve this answer
    
Excellent, thank you! –  Domonic Mei 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|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.