Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
$3^2+2=11{}{}$. –  Gerry Myerson Jul 18 '12 at 12:44
1  
$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
add comment

4 Answers 4

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.