Question

Given two positive integers a,b what is the minimal integer n, so that there exist two positive integers u,v for which n=au=av?

It is easy to verify that n=ab/gcd(a,b).

But what happens if instead of requiring au=bv, or |au-bv|≤0, we require that |au-bv|≤k for some number k?

That is, given two positive integers a,b, what are the minimal integers u,v for which |au-bv|≤k, for some k? If there's no direct formula, is there an easy way to find u,v?

Answer 1

A good heuristic is to compute the continued fraction of $a/b$ and drop the last few terms. The continued fraction will equal $u/v$ with $a/b-u/v$ very small. Since $a/b-u/v=(av-bu)/bv$, we will have $au-bv$ small.

Answer 2

I get the feeling that some of those a's are meant to be b's, is this correct? Otherwise it looks like u, v = 1.