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.

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.

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

up vote 1 down vote accepted

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.

share|improve this answer

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.

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.