1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Closed per FC's comment. $\endgroup$
    – Scott Morrison
    Nov 18, 2009 at 16:30
  • $\begingroup$ I'm not sure I get the drift of the FAQ. If it's not either a research question, or related to graduated material - it's not for Mathoverflow? Lightweight material - out? No room for, say, recreational math? Stackoverflow for instance has room for programming riddles which are not of real professional interest. (I'm not criticizing, just want to make sure I got the spirit of the site) $\endgroup$
    – Elazar Leibovich
    Nov 18, 2009 at 16:55
  • $\begingroup$ Recreational math is certainly okay. I think David Speyer's answer below indicates this isn't a particularly interesting question. Remember the primary criterion is "of interest to mathematicians", where we're defining "mathematicians" fairly tightly. If it had more upvotes, or some comments complaining about me closing it, I'd reconsider. More generally, we're still exploring the range of questions we're after -- feel free to come over to tea.mathoverflow.net to discuss. $\endgroup$
    – Scott Morrison
    Nov 18, 2009 at 17:05

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Correct, fixed. $\endgroup$
    – Elazar Leibovich
    Nov 18, 2009 at 17:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.