Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as too localized by Scott Morrison Nov 18 '09 at 16:29

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Closed per FC's comment. –  Scott Morrison Nov 18 '09 at 16:30
    
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) –  Elazar Leibovich Nov 18 '09 at 16:55
    
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. –  Scott Morrison Nov 18 '09 at 17:05

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Correct, fixed. –  Elazar Leibovich Nov 18 '09 at 17:01

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