Specific equations of the form below (for different given values of p, a prime number) will either have positive integer solutions for $x$ & $y$, or will not have any integer solutions.

$${2^{p-1} -1 \over p} = 2pxy + x + y$$

Is there a way to determine when an equation of this form has integer solutions and when it does not? (Other than just trying values in a brute force manner and eventually giving up?) A repeatable algorithmic method of determining whether there are integer solutions would be ideal, does this exist? If not, are there any tricks or techniques that work sometimes, or any suggested approaches?

For example, these have positive integer solutions:
when p=11, (1/11)*(2^(10)-1)=2*11*x*y+x+y has integer solution x=1 & y=4
when p=23, (1/23)*(2^(22)-1)=2*23*x*y+x+y has integer solution x=1 & y=3880
when p=29, (1/29)*(2^(28)-1)=2*29*x*y+x+y has integer solution x=4 & y=39727
when p=37, (1/37)*(2^(36)-1)=2*37*x*y+x+y has integer solution x=3 & y=8328624

And these do not have (positive) integer solutions:
when p=7, (1/7)*(2^(6)-1)=2*7*x*y+x+y has no integer solution
when p=13, (1/13)*(2^(12)-1)=2*13*x*y+x+y has no integer solution
when p=19, (1/19)*(2^(18)-1)=2*19*x*y+x+y has no integer solution
when p=31, (1/31)*(2^(30)-1)=2*31*x*y+x+y has no integer solution

  • $\begingroup$ How did you find out that for $p=7,13,19,31$, there is no integer solution? Is it just an hypothesis based on computations, or do you now these facts for sure? $\endgroup$ – Suzet Jul 31 '18 at 5:22
  • $\begingroup$ @Suzet I started with a non-prime Mersenne number has factors of the form: (2xp+1)(2yp+1). Then derived the equation I give in the question above. And in the case of p=7,13,19,31 those Mersenne numbers are Mersenne primes, so they have no factors, so there should be no integer solutions to the equation. For Mersenne numbers that are not prime, e.g. p=11,23,29,37, I was able to solve the equation for x & y and from that compute from that the factors of those Mersenne numbers. Thus I would like to see if there is a way to determine when the equation has integer solutions as a primality test. $\endgroup$ – user669487 Jul 31 '18 at 5:41
  • $\begingroup$ The given equation is equivalent to $$2^p-1=(2px+1)(2py+1)$$ but considering your comment you apparently already exploited this. $\endgroup$ – Peter Jul 31 '18 at 11:24
  • 1
    $\begingroup$ @user669487 Actually this easily leads to a primality test which is however of very little practical use. Note that every factor of $2^p-1$ with prime number $p$ is of the form $2pk+1$ $\endgroup$ – Peter Jul 31 '18 at 11:26
  • $\begingroup$ @Peter, yes the equation you gave is essentially where I started. I'm curious in trying to figure out how to tell when it has no integer solutions for x & y given a value for p. $\endgroup$ – user669487 Jul 31 '18 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.