0
$\begingroup$

I have a set of Diophantine equations which I know only one equation has a single solution.

I am trying to find a way to give probabilities to which equation contains the solution.

For example, which of the following most likely contains a solution?

16xy +  1x + 13y = 249835285
16xy +  3x + 15y = 249835283
16xy +  5x +  9y = 249835283
16xy +  7x + 11y = 249835281

Where 'x' and 'y' are both non-zero, positive integers.

I have tried using modular arithmetic to see how many possible solutions exist for each equation.

Eg

16xy +  1x + 13y = 249835285
1xy +  1x + 1y = 1 (mod 3)
1xy +  1x + 3y = 0 (mod 5)
2xy +  1x + 6y = 0 (mod 7)

But there appears to be equal possible solutions to each.

For the curious, x = 3148 and y = 4959 is the solution to 16xy + 5x + 9y = 249835283.

$\endgroup$
1
$\begingroup$

There's no probability involved: a particular equation either has positive integer solutions or it doesn't.

In general, $a x y + b x + c y = d$ (with $a,b,c,d$ positive integers) can be written as $$ (ax + c)(ay + b) = ad + bc $$ The solutions correspond to ways to factor $ad + bc = uv$ where $u \equiv c \mod a$ and $v \equiv b \mod a$, $u > c$ and $v > b$: then $x = (u-c)/a$ and $y = (v - b)/a$ are solutions.

In your first case, $a=16$, $b = 1$, $c = 13$, $d =249835285$, $ad+bc = 3997364573 = 50377 \times 79349$, where $50377$ and $79349$ are primes $\equiv 9$ and $5 \mod 16$ respectively. There is no acceptable choice for $u$ and $v$.

In your third case, $a=16$, $b=5$, $c=9$, $d=249835283$, $ad+bc = 3997364573 = 50377 \times 79349$ again, so this time we can take $u=50377$ and $v = 79349$.

$\endgroup$
2
  • $\begingroup$ What about if we don't know the factorization of ad+bc? Is there a method which makes one of the equations 'more likely' to lead to the solution? $\endgroup$ – threenplusone Jul 21 '16 at 7:25
  • $\begingroup$ As $n \to \infty$, the numbers of primes $\le n$ that are $\equiv b \mod a$ are approximately equal for all $b$ coprime to $a$, so in that sense none of the equations is very much "more likely" than the others. Of course those numbers won't be exactly equal. Thus of the $6335$ odd primes $\le \sqrt{3997364573}$, $1574$ are $\equiv 1$ or $13 \mod 16$ while $1579$ are $\equiv 5$ or $9 \mod 16$. So in that sense you might say that the third case is very slightly "more likely" than the first. $\endgroup$ – Robert Israel Jul 21 '16 at 17:11

Your Answer

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

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