# Equation involving prime numbers

Given the equation: $$p^2+\phi=q$$ where $p$ and $q$ are prime numbers and $\phi$ a constant, it seems the equation doesn't have solutions for $\phi=1,2,3$, but it has solutions for $\phi=4$. Is it possible to show why? Or maybe, there are solutions that I am not able to find also for $\phi=1,2,3$? Thanks for any suggestions.

-
$3^2+2=11{}{}$. –  Gerry Myerson Jul 18 '12 at 12:44
$2^2 + 1 = 5$ ($\phi = 1$, the only one, by parity), $2^2 + 3 = 7$ ($\phi = 1$, same). –  martini Jul 18 '12 at 12:45
If $\phi=1$, q=$p^2+1$, -1 is Quadratic residue of q =>q≡ 1(mod 4), similar constraints for $\phi=2,3$ can derived. Also $ord_qp=4$, for example $ord_52=4$ –  lab bhattacharjee Jul 18 '12 at 13:28

Consider divisibility of $p^2+2$ by 2 (for $\phi=1,3$) and by 3 (for $\phi=2$).

-

All the primes except $2$ are odd, so for $\phi$ odd, one of $p, q$ must be $2$. You could have $p=1, \phi=1, q=2$, but $1$ is not prime. $p=2, \phi=1, q=5$ and $p=2, \phi=3, q=7$ are solutions.

-

It obviously has no solutions for any odd $\,p\,,\,\phi\,$, as the LHS would be even. It too has solution for $\,p=3\,,\,\phi=2\,,\,q=11\,$, contradicting what you wrote...

-

If p>3 and $\phi=1\ or\ 3$,

p can be written as 6k±1

=>$p^2+(1\ or\ 3 )$

=$(6k±1)^2+(1\ or \ 3)$,

then q is even and >2,so q can not be prime for p>3 and $\phi=1$.

If p>3 and $\phi=2$ then, 3|q and q>3 ,so q can not be prime for p>3 and $\phi=2$.

So, the necessary cases for $\phi<4$ is p=2 or 3.

Also, p and $\phi$ are of opposite parity.

So, the potential solutions(p, $\phi$) could be (2,1),(2,3), (3,2).

Eventually, q is prime in all the three cases.

Alternatively, if prime p>3, p can be written as 6k±1 and $\phi$ must be even else q will be even and >2, hence can not be prime.

So, $\phi$ can be 6r, 6r+2, 6r+4.

But 3|$(p^2+1)$ if $\phi$=6r+2. So, $\phi$ can only be 6r, 6r+4 if p>3.

-