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

1. ## Proof

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

2. 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 $a\not \equiv 0(\bmod q)$. We will also assume that $p,q$ are odd primes.

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

3. Thanks!