1
$\begingroup$

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.

  • 0
    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$2012-07-18

4 Answers 4

2

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

1

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.

0

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...

0

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.