# When is $p^2+1$ twice of a prime?

When trying to solve a bigger problem, I came across the problem of characterising all primes $$p,q$$ such that $$p^2+1=2q$$. That is, are there necessary and sufficient conditions for primes $$p,q$$ to satisfy the equation? Even better, is there a paramatrisation of solutions (though, this is probably unlikely)? I know the solutions $$(p,q)=(3,5),(5,13),(11,61),(19,181),(29,421)$$ but I don't know that these are the only ones (indeed, it seems likely there are many more).

Some incomplete thoughts: I immediately made the factorisation $$(p+1)(p-1)=2(q-1)$$, and because $$p$$ is obviously odd, let $$p=2p_1+1$$. This leads us to the equation $$2p_1(p_1+1)=q-1$$. If we substituted $$q=2q_1+1$$ we have $$p_1(p_1+1)=q_1$$, so $$q$$ is twice of the product of two consecutive integers, plus one. It follows that $$q$$ is $$1$$ mod $$4$$, and $$p^2$$ is $$1$$ mod $$8$$. The same conclusion can be obtained simply by noting that $$-1$$ must be a quadratic residue mod $$2q$$, hence $$1$$ is a $$4$$th power residue mod $$2q$$. By Lagrange's Theorem we have $$4\mid\phi(2q)=q-1$$, so $$q \equiv1$$ mod $$4$$. Any further thoughts are appreciated!

• oeis.org/A048161 – mathlove Dec 29 '18 at 5:51
• You should definitely look at the link in the first comment. Whether there are infinitely many such $p$ is unknown... BTW if $p>5$ then $p\equiv \pm 1 \mod 10,$ for if $5<p\equiv \pm 3 \mod 10$ then $( p^2+1)/2$ is greater than $5$ and divisible by $5.$ – DanielWainfleet Dec 29 '18 at 6:28
• @mathlove Wow, thanks. If you make that an answer I would happily accept it :) – YiFan Dec 29 '18 at 8:50
• @YiFan Do you want to find all the solutions or only decide whether infinite many exist ? Besides some basic restrictions, there won't be useful methods. You will just have to check the number $\frac{p^2+1}{2}$ in general. If you are interested in an evidence that infinite many solutions probably exist, I can undelete my answer. – Peter Dec 30 '18 at 10:44
• @Peter I wanted to see if there was a nice necessary and sufficient criterion that could be used to describe all solutions to the equation, but I now know that's probably not going to happen. I'm certainly interested in anything related to the problem though, and your answer is welcome :) – YiFan Dec 30 '18 at 11:21

We have infinitely many primes of the form $$\frac{p^2+1}{2}$$ where $$p$$ is itself prime, if we have infinite many positive integers $$k$$ such that $$2k+1$$ and $$2k^2+2k+1$$ are simultaneously prime. (in this case, just set $$p=2k+1$$). The Bunyakovsky conjecture implies that this is the case, so very likely infinitely many examples exist. But I am convinced that the problem is open.
I propose the following "kind of parametrization". Remark first, as you did, that necessarily $$q\equiv 1$$ mod $$4$$ (this can be seen directly from the characterization of integers which are sums of squares, see e.g. Samuel's ANT, V-6). Then work in the Gauss ring $$\mathbf Z[i]$$, which is a PID with units $$u=\pm 1,\pm i$$. For convenience, write $$z'≈z$$ for $$z'=uz$$. It is classically known that $$2$$ is totally ramified and $$q$$ splits completely in the Gauss ring, more precisely $$2=(1+i)^2≈(1+i)(1-i)$$ and $$q≈(x+iy)(x-iy)$$, where $$x\pm iy$$ are prime elements of $$\mathbf Z[i]$$. Because of unique factorization (up to units), the given equation will be equivalent to $$p+i≈(1+i)(x+iy)$$, hence our "pseudo-parametrization" will be as follows: 1) Take a prime $$q\equiv 1$$ mod $$4$$ and decompose it in $$\mathbf Z[i]$$; 2) Solve $$p+i≈(1+i)(x+iy)$$ in $$\mathbf Z^2$$. Because of symmetry, let us solve only the equation $$p+i=-(1+i)(x+iy)$$. By identification, $$p=y-x$$ and $$-1=x+y$$, so $$p=2y+1$$. It remains however to check that $$2y+1$$ is a prime in $$\mathbf Z$$, which is why our method cannot be considered as a genuine parametrization. Although we have just shown that the OP question is essentially equivalent to the Bunyakovsky conjecture evoked by @Peter, I don't know if this gives any new hint.