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.
Equation involving prime numbers
-
0If $\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$ – 2012-07-18
4 Answers
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.