# Proof - What conditions are necessary on q for it to be a divisor of a^p+1 if...

• Mar 16th 2009, 01:06 PM
gummy_ratz
Proof
What conditions are necessary on q for it to be a divisor of a^p+1 if p and q are both prime?
• Mar 17th 2009, 11:57 AM
ThePerfectHacker
Quote:

Originally Posted by gummy_ratz
What conditions are necessary on q for it to be a divisor of a^p+1 if p and q are both prime?

We notice that $\displaystyle a\not \equiv 0(\bmod q)$. We will also assume that $\displaystyle p,q$ are odd primes.

If $\displaystyle a^p +1\equiv 0(\bmod q) \implies a^{2p}\equiv 1(\bmod q)$. Let $\displaystyle k$ be the order of $\displaystyle a$ mod $\displaystyle q$. This forces $\displaystyle k|2p \implies k=1,2,p,2p$. If $\displaystyle k=1$ then $\displaystyle a\equiv 1(\bmod q)$ and so $\displaystyle a^p + 1 \equiv 2\not \equiv 0 (\bmod q)$, thus $\displaystyle k\not = 1$. If $\displaystyle k=2$ then $\displaystyle a^2\equiv 1(\bmod q)\implies a\equiv -1(\bmod q)$. And so $\displaystyle a^p + 1\equiv 0(\bmod q)$, however, this is an unintersting case because there is no restriction on $\displaystyle p$. Thus, we can safely assume that $\displaystyle k=p\text{ or }2p$. Thus, $\displaystyle p|(q-1) \text{ or }2p|(q-1)$ in either case $\displaystyle p|(q-1)$ since $\displaystyle (2,p)=1\text{ and }2|(q-1)$. Thus, we require that $\displaystyle p$ divides $\displaystyle q-1$.
• Mar 17th 2009, 07:49 PM
gummy_ratz
Thanks!