1
$\begingroup$

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
    I think the notation may be supposed to mean that the fractions are integers - but it needs clarifying to make sense of the problem.2012-03-15

2 Answers 2

1

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.

0

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.