# Need help with this primitive roots question

Question:

If p and q are odd primes and $({a^p+1})/q$, show that either $(a+1)/q$ or $q= 2kp + 1$ for some integer $k$

I read the theorem that says If p and q are odd primes and $({a^p-1})/q$, show that either $(a-1)/q$ or $q= 2kp + 1$ for some integer $k$. I tried to follow a similar method as the proof of that theorem, but I can't seem to be able to come up with a solution.

-
Sorry: what do you mean by "and $(a^p+1)/q$"? And $\frac{a^p+1}{q}$ what? Or is that supposed to mean "$q$ divides $a^p+1$"? (I guessed it might mean "$a^p+1$ divides $q$, but that would be silly: it would mean $a=0$ or $a^p+1=q$). –  Arturo Magidin Mar 15 '12 at 19:31
Apparently Google thinks you mean $q \mid (a^p + 1).$ This exact problem is verbatim If p and q are odd primes and q | a^(p) + 1, Show that either q | a+1 or q=2kp +1 for some integer k.? here on: answers.yahoo.com/question/index?qid=20090714022447AAXZQrK –  user2468 Mar 15 '12 at 19:36
Isn't this just a matter of replacing $a$ with $-a$? –  anon Mar 15 '12 at 19:36
I think the notation may be supposed to mean that the fractions are integers - but it needs clarifying to make sense of the problem. –  Mark Bennet Mar 15 '12 at 19:37

Suppose that $q$ divides $a^p+1$. Then $a^p \equiv -1 \pmod q$. Note that $(a^p)^2=a^{2p}$. So $a^{2p}\equiv 1 \pmod q$.

Let $e$ be the smallest positive integer such that $a^e\equiv 1 \pmod q$. Then $e$ divides $2p$. In principle, there are $4$ possibilities to examine: (i) $e=1$; (ii) $e=2$; (iii) $e=p$; (iv) $e=2p$.

Possibility (i): If $e=1$, then $a \equiv 1\pmod{q}$. This cannot happen, because we were told that $a^p \equiv -1\pmod{q}$. But $1\not\equiv -1\pmod{q}$, since $q$ is odd.

Possibility (ii): If $e=2$, then $a\equiv -1\pmod{q}$, so $q$ divides $a+1$.

Possibility (iii) If $e=p$, we reach a contradiction, since $a^p\equiv -1 \pmod{q}$, and $1\not\equiv -1\pmod{q}$.

Possibility (iv): Recall that by the minimality of $e$, the number $e$ must divide any $k$ such that $a^k\equiv 1\pmod{q}$. Since $a$ cannot be divisible by $p$, we have, by Fermat's Theorem, $a^{q-1}\equiv 1\pmod{q}$. Thus if $e=2p$, the number $2p$ must divide $q-1$. Let $q-1=(2p)k$. Then $q=2kp+1$.

So the only live possibilities are (ii) and (iv). One yields that $q$ divides $a+1$, and the other yields that $q$ is of the shape $2kp+1$. Both can happen.

-

Suppose by hypothesis that $a^p+1\equiv0 \;(q)$. Then $(-a)^p-1\equiv0 \;(q)$, so by the original theorem we may conclude that either $(-a)-1\equiv 0 \;(q)$, which is $a+1\equiv0\;(q)$, or $q=2kp+1$, as desired.

-