Problem: Let $h$ and $k$ be positive integers. Prove that for every $\epsilon>0$ there are positive integers $m$ and $n$ such that $$\epsilon < |h\sqrt{m}-k\sqrt{n}| < 2\epsilon.$$

This is a Putnam problem and no I'm not a student. I just like math and I'm looking at some more challanging problems. Now, for this problem, I'm quite lost because I don't really know how to start of attacking number theoretical problems like these - any hint is much appreciated!

I was thinking of splitting it into four cases, one when $h$ is odd and $k$ is even, one when $h$ is even and $k$ is odd, a third where both are odd and a fourht where both are even. Is this futile?



We can use either the mean value theorem: $$\dfrac{f(b)-f(a)}{b-a} = f'(c),\qquad \text{for some }c\in(a,b)$$ with $f(x) = \sqrt{x}$, or some slick algebra, to find that when $0<a<b$ $$\sqrt{b}-\sqrt{a}\le\dfrac{b-a}{2\sqrt{a}} $$ and a similar bound from below.

Then there is a logical choice of $a$ and $b$ to get a pair of inequalities on $h\sqrt{m} - k\sqrt{n}$ and if you let $$m= k^2(\ell +1) \text{ and } n = h^2\ell$$ then you should be able to solve these inequalities to get bounds on $\ell$ in terms of $h,k,$ and $\varepsilon$ so that $$\varepsilon<h\sqrt{m} - k\sqrt{n} < 2\varepsilon$$

Good luck!! :)

(note there is some mucking around to be done when $\varepsilon$ isn't small but this is a method to tackle what is in my opinion the "hard" bit.)


The problem is initially quite intimidating, so the first thing to do is to try to see why it should be true before we set out trying to prove it with any amount of rigour. The way I saw the problem was this: we can rewrite the inequality like this $$ \varepsilon < \sqrt{h^2m}-\sqrt{k^2n}< 2\varepsilon$$ Now we can look at the term in the middle as the distance between two $y$ values on the graph of $y=\sqrt{x}$. This graph slowly flattens out so if we can make $h^2m$ and $k^2n$ big enough while still keeping them close we should be able to make the difference as small as we like (say less than $2\varepsilon$) and so long as we don't make them too big we should also be able keep the distance bigger than say $\varepsilon$.

But that won't do as a mathemtaical argument, we now need to formalise this notion of $\sqrt{x}\ $ "flattening out" there are couple of ways to do this and one of those ways is to consider the gradient of the graph which is where the mean value theorem comes in but if you're not familiar with that then don't worry we can arrive at the inequalities we need without it with some clever algebra (it just feels a little less motivated). So basically one way or another we can get the inequalities:

$$\dfrac{b-a}{2\sqrt{b}}\le \sqrt{b}-\sqrt{a}\le\dfrac{b-a}{2\sqrt{a}} $$

where $0<a<b$. Now we just have to pick the right values of $b$ and $a$ to give us the desired result (the choice is hopefully clearish at this point?) Anyway because of the $b-a$ that pops up in the numerator I found that defining a new variable $\ell$ and setting $$m= k^2(\ell +1) \text{ and } n = h^2\ell$$ algebraically convenient. Once here we just enforce a bound of $2\varepsilon$ from above and $\varepsilon$ from below and algebraically solve for $\ell$.


The upper bound comes from setting $$\ell > \dfrac{h^2k^2}{4^2\varepsilon^2}$$

This was a fun problem, thanks! :)

  • $\begingroup$ 1) What do you mean by "with a nice choice of..."? 2) How did you deduce the $\ell$? 3) I used ($\epsilon$) Epsilon in my question, why did you use ($\varepsilon$) Varepsilon? $\endgroup$
    – Parseval
    May 5 '17 at 4:55
  • $\begingroup$ I've tried adding in some motivation (hopefully that helps) let me know! (also my formatting choices are entirely stylistic there's no magic going on there) $\endgroup$
    – Angus Leck
    May 5 '17 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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