# Diophantine inequality that's not solved

Mathematica has trouble solving this Diophantine inequality:

(* givens *)
e = 653315732497285855855422606783
f = 1697172185816328002847853765504
g = 1650189636468405601822430434691
h = 2622176396697944576102111774652
m = 10^10

FindInstance[Abs[a f (g + d h) - b h (e + c f)] < m
&& 0 < c && c < a && a < m && 0 < d && d < b && b < m,
{a, b, c, d}, Integers]


nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.

How can we help it?

Note: if that helps, the context insures Abs[a d - b c] < m. But adding that condition does not seem to improve things.

There are at least two solutions:

{{a -> 9861328816, b -> 6913952452, c -> 6835352265, d -> 4792386648},
{a -> 7395996612, b -> 5185464339, c -> 6835352265, d -> 4792386648}}


See this question on the Cryptography Stack for context.

Update: I simplified the problem thru some simple modular arithmetic (see how in the related question on math-SE) but still hit a wall:

(* givens *)
e = 653315732497285855855422606783
f = 1697172185816328002847853765504
g = 1650189636468405601822430434691
h = 2622176396697944576102111774652
m = 10^10

(* derived quantities *)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

FindInstance[Mod[gg s, hh]<m && Mod[ee s, ff]<m && -mm<s && s!=0 && s<mm, s, Integers]


mpwc: FindInstance was unable to convert $$\left\lfloor\frac{356075003617676589725598337103\,s}{424293046454082000711963441376}\right\rfloor$$ to Piecewise because the required number 4196097564 of piecewise cases sought exceeds the internal limit $MaxPiecewiseCases = 100. Update: Problem solved! But I would love to know how to have Mathematica rather than me make the math, even for the last step! • The result of Reduce[a f (g + d h) - b h (e + c f) < m && 0 < c && c < a && a < m && 0 < d && d < b && b < m && a f (g + d h) - b h (e + c f) > -m, {a, b, c, d}, Reals] may be useful. Only the two last cases lead to integer solutions. Dec 8 '20 at 18:14 • Putting $MaxPiecewiseCases = 10^10; and executing your modified code,I obtain "FindInstance::nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.". Every soft has its limitations. Dec 9 '20 at 10:09

This is just a simplified code of the OP answer. The method is the same. The code uses the fact that a == gg s - u hh and b == ee s - v ff so it is not necessary to re-compute them using {a = Mod[gg s, hh], b = Mod[ee s, ff]}.

(* givens *)
e = 653315732497285855855422606783;
f = 1697172185816328002847853765504;
g = 1650189636468405601822430434691;
h = 2622176396697944576102111774652;
m = 10^10;

(*derived quantities*)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

(*find all pairs {a, b}*)
ab = Or @@
And @@@ Solve[
0 < gg s - u hh == a < m &&
0 < ee s - v ff == b < m && -mm < s && s != 0 && s < mm, {a, b,
s, u, v}, Integers][[All, {1, 2}]] /. Rule -> Equal

(*find all {a, b, c, d}*)
Solve[(Abs[a f (g + d h) - b h (e + c f)] < m && 0 < c < a &&
0 < d < b && ab), {a, b, c, d}, Integers]


Output:

(a == 2465332204 && b == 1728488113) || (a == 4930664408 &&
b == 3456976226) || (a == 7395996612 &&
b == 5185464339) || (a == 9861328816 && b == 6913952452)

{{a -> 2465332204, b -> 1728488113, c -> 1904687857,
d -> 1335410422}, {a -> 4930664408, b -> 3456976226,
c -> 1904687857, d -> 1335410422}, {a -> 4930664408,
b -> 3456976226, c -> 4370020061,
d -> 3063898535}, {a -> 7395996612, b -> 5185464339,
c -> 1904687857, d -> 1335410422}, {a -> 7395996612,
b -> 5185464339, c -> 4370020061,
d -> 3063898535}, {a -> 7395996612, b -> 5185464339,
c -> 6835352265, d -> 4792386648}, {a -> 9861328816,
b -> 6913952452, c -> 1904687857,
d -> 1335410422}, {a -> 9861328816, b -> 6913952452,
c -> 4370020061, d -> 3063898535}, {a -> 9861328816,
b -> 6913952452, c -> 6835352265,
d -> 4792386648}, {a -> 9861328816, b -> 6913952452,
c -> 9300684469, d -> 6520874761}}

• Nice! The end is more elegant than my mess. Learned useful things, including 0 < c < a Dec 9 '20 at 14:02

Solved! It works better when we explicitly change Mod[gg s, hh] < m into
0<= gg s - u hh && gg s - u hh < m with some additional variable u.

I though Mathematica would know that! And would love a way to make it automagic.

(* givens *)
e = 653315732497285855855422606783;
f = 1697172185816328002847853765504;
g = 1650189636468405601822430434691;
h = 2622176396697944576102111774652;
m = 10^10;

(* derived quantities *)
l = GCD[f, h];
mm = Ceiling[m/l];
ff = f/l;
hh = h/l;
gg = PowerMod[g ff, -1, hh];
ee = PowerMod[-e hh, -1, ff];

(* find the list S of solutions s *)
S = Last /@ First /@ Solve[
0 < gg s - u hh && gg s - u hh < m &&
0 < ee s - v ff && ee s - v ff < m &&
-mm < s && s != 0 && s < mm, {s, u, v}, Integers];

(* show the solutions as {a,b,{list-of-solutions {c,d}} *)
MySol[s_] := Block[{a = Mod[gg s, hh], b = Mod[ee s, ff]},
{a, b,
Solve[ Abs[a f (g + d h) - b h (e + c f)] < m &&
0 < c && c < a && a < m && 0 < d && d < b && b < m,
{c, d}, Integers]
}]
SetAttributes[MySol, Listable];
MySol[S]


Which yields (hopefully) all the 10 solutions:

{{2465332204, 1728488113, {{c -> 1904687857, d -> 1335410422}}},
{4930664408, 3456976226, {{c -> 1904687857, d -> 1335410422},
{c -> 4370020061, d -> 3063898535}}},
{7395996612, 5185464339, {{c -> 1904687857, d -> 1335410422},
{c -> 4370020061, d -> 3063898535},
{c -> 6835352265, d -> 4792386648}}},
{9861328816, 6913952452, {{c -> 1904687857, d -> 1335410422},
{c -> 4370020061, d -> 3063898535},
{c -> 6835352265, d -> 4792386648},
{c -> 9300684469, d -> 6520874761}}}}

• +1. The solution presented by you is very tricky. Dec 9 '20 at 12:45