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

3. Thanks!