# Suppose $p$, $q$ are distinct odd primes, $a\in\mathbb{Z}$, and $q|a^p-1$ but $q\nmid a-1$

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!

-

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?

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

-