# $p \mid q^r+1$, Prove that either $2r\mid p-1$ or $p \mid q^2-1$

Let $p$ be an odd prime. $q,r$ are primes such that $p \mid q^r+1$. Prove that either $2r\mid p-1$ or $p \mid q^2-1$ $\def \m {\; \text{mod}\;}$

My Work
$$q^r\equiv -1 \m p\\ q^{2r} \equiv 1 \m p$$
From Fermat's Little theorem we have - $$q^{p-1} \equiv 1 \m p$$
From this two equation -
$$q^{(2r,p-1)} \equiv 1 \m p$$
As $p$ is odd prime so $p-1$ is even. Then $(2r,p-1) = 2$. So - $$q^2 \equiv 1 \m p \implies p \mid q^2 -1$$
So, my solution is saying always $p \mid q^2-1$ but I was supposed to prove that only one of them is right. Where I am mistaken?
I'd also like to know different approaches to solve this problem.

$(2r,p-1)$ is not always $2$, since $r$ is a prime and $p-1$ is even, if it is not $2$, it means $r| p-1$, so $2r|p-1$.
• $\def \m {\; \text{mod}\; }$ $q^{2r} \equiv 1 \m p \\ (q^2)^r \equiv 1 \m p \\ p \mid q^2-1 \\ \text{Then both are true .. :|}$ – Rezwan Arefin Feb 5 '17 at 20:16
• If gcd is not $2$ then $r \mid p-1$... I think it is not obvious. – Rezwan Arefin Feb 5 '17 at 20:18
I got another approach. $\def \m {\; \text{mod}\;}$
Let $d$ be minimum positive integer such that $q^d \equiv 1 \m p$. Then $$q^r \equiv -1 \not \equiv 1 \m p\; \text{and}\\ q^{2r} \equiv -1 \m p$$
From above 3 equations- $d \mid 2r$ but $d \not \mid r$. Since $r$ is prime, then $d=2\; or\; 2r$.
If $d = 2$ then $q^2 \equiv 1 \m p \implies p \mid q^2-1$
If $d=2r$ then from Fermat's $q^{p-1} \equiv 1 \m p$. So from 1st congruence we have $2r \mid p-1$
Actually this is same solution indeed. But from this it is easily understandable why $(2r,p-1)$ can be $2r$.