Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that $$r=\frac{p^m+1}{2}$$ is a prime number, where $p$ is also prime. Does the equation $$p^{2}-2\equiv 0 \pmod{r}$$ have any solutions?

Thanks in advance.

share|cite|improve this question
Is the $p$ in the definition of $r$ the same as the $p$ in the equation? In other words, are you asking whether there are any primes $p$ such that both $(p^m+1)/2$ is a prime, and $p^2\equiv 2\pmod{(p^m+1)/2}$ holds? Or are you just asking whether $2$ is a square modulo $(p^m+1)/2$ when both $p$ and $(p^m+1)/2$ are primes? – Arturo Magidin Jun 5 '12 at 18:56
@Arturo I think the latter $p$ is meant to be $x$, given the title of the post. – alex.jordan Jun 5 '12 at 23:53
@alex.jordan: That was not the original title. If you look at the edit history, you will see that the original title was Question in number theory. That title was put in by M Turgeon in his edit. – Arturo Magidin Jun 6 '12 at 3:23
Are there any conditions on $m$? Or certainly there will be counterexamples. – awllower Jun 7 '12 at 14:31
up vote 2 down vote accepted

I'm going to assume the question as posed is the question intended.

$p^2-2\equiv0\pmod r$ requires $r\lt p^2$. But $r=(p^m+1)/2$ almost requires $r\gt p^2$, so the two relations are nearly mutually exclusive. The only ways they can both hold are

  1. $m=1$. Then $r=(p+1)/2$; $p=2r-1$; $p^2-2=4r^2-4r-1\equiv-1\pmod r$, so no solutions here.

  2. $m=2$. Then $r=(p^2+1)/2$; $p^2=2r-1$; $p^2-2=2r-3\equiv-3\pmod r$; so the only way this is going to work is if $-3\equiv0\pmod r$, which says $r=3$, but this leads to $p=\pm\sqrt5$, which is nonsense, so no solutions here, either.

And that's it. If $m\ge3$ then you'll find that $r=(p^m+1)/2\gt p^2$, so there are no other cases to look at.

In summary, with the problem as posed, the congruence has no solutions.

share|cite|improve this answer

For any prime $\,q\,$, the equation $\,x^2=2\pmod q\,$ has a solution iff $\,q=\pm 1\mod 8\,$ . As I am assuming that in "$\,p^2-2=0\pmod r\,$" you actually meant $\,x^2-2=0\pmod r\,$ (if I'm wrong in my assumption please disregard this post), I'll give you two examples with different outcomes:

== for $\,\displaystyle{\,p=3\,,\,m=4\,,\,r=\frac{3^4+1}{2}=41=1\pmod 8\,\,}$ , so your equation has solution

== for $\,\,\displaystyle{p=5\,,\,m=2\,\,,\,r=\frac{5^2+1}{2}=13\neq \pm1\pmod 8}\,\,$ , and your equation has no solution here.

Thus I believe you must either change your question or impose further conditions.

share|cite|improve this answer

If you are asking whether $2$ is a quadratic residue of $r$, it is easy to find by treating each of the following 8 cases: when $p \equiv 1, 3, 5, 7, 9, 11, 13, 15 (\bmod\, 16)$ respectively. Suppose $r=(p^m+1)/2$ is a prime, then the condition for $2$ being a quadratic residue of $r$ is

when $p=16n+1$, $m$ can be any natural number

when $p=16n+3$ or $16n+11$, $m\equiv 0\, (\bmod\, 4)$

when $p=16n+5$, $m\equiv 0\ \mbox{or}\ 3\, (\bmod\, 4)$

when $p=16n+7$ or $16n+9$ or $16n+15$, $m$ can be any even number

when $p=16n+13$, $m\equiv 0\ \mbox{or}\ 1\, (\bmod\, 4)$

The principle is to raise the least residues to (at most) power $4$, plus $1$ then divide by $2$, and find those which $\equiv \pm 1\, (\bmod\, 8)$

share|cite|improve this answer
If $p=16n+1$. We can $p=17$ for example, then $(p^m +1)/2$ when $m$ is odd number is not prime. In my question $(p^m +1)/2$ is prime. – Sara Jun 10 '12 at 18:47
You are right. But I have already supposed that $(p^m+1)/2$ is a prime number. – AcrePrime Jun 11 '12 at 6:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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