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

  • $\begingroup$ $\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 .. :|}$ $\endgroup$ – Rezwan Arefin Feb 5 '17 at 20:16
  • $\begingroup$ If gcd is not $2$ then $r \mid p-1$... I think it is not obvious. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.