# Approximation of a real number as a linear combination of two reals with coprime integral coefficients

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, give me an algorithm that will provide coprime integers $a$ and $b$ such that $|ax + by - z| < \epsilon$.

Note that if the restriction that $a$ and $b$ be coprime is lifted, the problem becomes very simple. One possible algorithm is:

• Find $a_1$ and $b_1$ such that $0 < a_1 x + b_1 y < \epsilon$ using the extended Euclidean algorithm.
• Let $\displaystyle a = a_1 \left[ \frac{z}{a_1 x + b_1 y} \right]$ and $\displaystyle b = b_1 \left[ \frac{z}{a_1 x + b_1 y} \right],\,$ where $[\,\cdot\,]$ is the nearest integer function.

However, the integers $a$ and $b$ provided by this algorithm are usually not coprime. I'm looking for an algorithm that produces the same kind of approximation but guarantees that $a$ and $b$ are coprime.

-
I would suggest a search for "inhomogeneous diophantine approximation." –  Gerry Myerson Jul 10 '11 at 11:12