Avoiding overflow in finding a solution to $ax + by = c$
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.