Avoiding overflow in finding a solution to $ax + by = c$ Can anyone come up with a nice way of computing a solution to the linear diophantine equation $ax + by = c$ where $a,b,c \in \mathbb{Z}$ and $\gcd(a,b) \mid c$, such that all the calculations are carried out without any of the intermediate results exceeding $\max\{|a|, |b|, |c|\}$ in absolute value?

I.e. if $a,b,c$ are 64-bit integers, all the calculations should be done using 64-bit integers only.

The standard method is of course to use Euclidean algorithm to first find a solution to $ax + by = \gcd(a,b)$ and then multiplying $x$ and $y$ by $\frac{c}{\gcd(a,b)}$. The Euclidean algorithm is fine, but this last multiplication might go out of range.
One way to solve this might be through an application of the Chinese remainder theorem and some kind of Hensel lifting.
Let's fix a constant $\alpha$ with the property that $2^\alpha 3^\alpha 5^\alpha &gt; 2^{129}$ and $5^\alpha &lt; 2^{64}$.  For instance, $\alpha=27$ would work fine.
Suppose $ax+by=c$ holds modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$, i.e., $ax+by \equiv c \pmod{q}$ for $q=2^\alpha$, $q=3^\alpha$, and $q=5^\alpha$.  Then by the Chinese remainder theorem, it follows that $ax+by=c$ holds in the integers.  So, our goal will be to find $x,y$ that satisfy this equation modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$.
Here are some observations that will help us find a solution that works modulo each of $2^\alpha$, $3^\alpha$, and $5^\alpha$:

Given a solution that is valid modulo $2^i$, $3^i$, and $5^i$, it is easy to find a solution that is valid modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$.  Here is how.  Given $(x,y)$ such that $ax+by \equiv c \pmod{q}$ (for $q\in \{2^i,3^i,5^i\}$), we consider the 3481 pairs $(x',y')$ such that $x' \in \{x,x+ d \cdot 2^i 3^i 5^i : |d| &lt; 30, d \in \mathbb{Z}\}$ and $y' \in \{y,y+ d \cdot 2^i 3^i 5^i : |d| &lt; 30, d \in \mathbb{Z}\}$.
One of these pairs will satisfy $ax+by \equiv c \pmod{q}$ (for $q\in \{2^{i+1}, 3^{i+1}, 5^{i+1}\}$) and will avoid overflow in $x',y'$ (i.e., we will have $0 \le x',y' &lt; 2^{64}$).  So, you can check all 3481 candidates and find the one that you wanted.  Identifying the one you wanted is easy.  Given a candidate, it is easy to check for overflow and immediately rule out any $x',y'$ that trigger overflow or underflow in the expressions $x+ d \cdot 2^i 3^i 5^i,y+ d \cdot 2^i 3^ i5^i$.  Also, you can check whether $ax+by=c$ holds modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$ separately in 64-bit arithmetic without overflow, as long as each of $2^{i+1},3^{i+1},5^{i+1}$ is at most $2^{64}$.

It is also easy to find a solution that is valid modulo $2^0 3^0 5^0$: simply take $x=0,y=0$.


Given all of this background, we can now use induction to find a solution.  We start by forming a solution that works for $i=0$.  At each step, we increment $i$, until we reach $i=\alpha$.  Each step can be done in 64-bit arithmetic semi-efficiently (with a few thousand basic arithmetical operations), so the whole computation should be semi-efficient.

I feel like there ought to be some way to work modulo $2^i$, $3^j$, and $5^k$, and at each step separately increment either $i$, $j$, or $k$, but I haven't worked out the exact details of how to do that yet.  If you can make that work, the resulting scheme would be significantly more efficient.