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

-

1
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

1
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

1
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

## 2 Answers

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 66, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9368992447853088, "perplexity_flag": "head"}