# Is 2 a quadratic residue modulo $r=\frac{p^m+1}{2}$?

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?

-
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

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.

-

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.

-

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

-
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