Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$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
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.