Home > Algebra, Number theory, Olympiad > Best approximation of a certain square root

## Best approximation of a certain square root

Let ${\lambda}$ be a real number such that the inequality

$\displaystyle 0 < \sqrt{2002}-\frac{a}{b} < \frac{\lambda}{ab}$

holds for an infinity of pairs ${(a,b)}$ of natural numbers. Prove that ${\lambda\geq 5}$.

Solution: We know that ${a^2 <2002 b^2}$. Then there exists a positive integer ${k}$ such that ${a^2=2002b^2-k}$. Let’s find the smallest value for ${k}$. We factor ${2002}$ and we get ${2002=2\cdot 7\cdot 11\cdot 13}$. We see that ${-k}$ is a quadratic residue modulo ${7,11,13}$. Let’s enumerate these quadratic residues:

$\displaystyle a^2 \pmod 7 \in \{0,1,4,2\}$

$\displaystyle a^2 \pmod{11} \in \{0,1,4,9,5,3\}$

$\displaystyle a^2 \pmod{13} \in \{0,1,4,9,3,12\}$

Now we can pick the values of ${k}$ one at a time to see which one is the smallest and verifies that ${-k}$ is quadratic residue modulo ${7,11,13}$.

• ${k=1}$: ${-1}$ is not quadratic residue modulo ${7}$;
• ${k=2}$: ${-2}$ is not quadratic residue modulo ${7}$;
• ${k=3}$: ${-3}$ is not quadratic residue modulo ${11}$;
• ${k=4}$: ${-4}$ is not quadratic residue modulo ${7}$;
• ${k=5}$: ${-5}$ is not quadratic residue modulo ${7}$;
• ${k=6}$: ${-6}$ is not quadratic residue modulo ${13}$;
• ${k=7}$: ${-7}$ is not quadratic residue modulo ${13}$;
• ${k=8}$: ${-8}$ is not quadratic residue modulo ${7}$;
• ${k=9}$: ${-9}$ is not quadratic residue modulo ${11}$;
• ${k=10}$: ${-10}$ has residues ${4,1,3}$ modulo ${7,11,13}$ (respectively) and they are all quadratic residues.

Therefore ${k \geq 10}$ and we find that ${a^2+10\leq 2002b^2}$. Using the hypothesis and the new found inequality we find:

$\displaystyle \frac{10}{b\sqrt{2002}+a} \leq b\sqrt{2002}-a<\frac{\lambda}{a},$

and taking the inequality between the first and last term we obtain

$\displaystyle \frac{10}{\frac{b}{a}\sqrt{2002}+1}<\lambda.$

We know that

$\displaystyle 0<\frac{b}{a}\sqrt{2002}-1<\frac{\lambda}{a^2}$

Since ${a,b}$ take infinitely many values, we find that ${a/b}$ approximates the irrational number ${\sqrt{2002}}$ so ${a}$ (and ${b}$) get arbitrary large in order to do that. We add ${2}$ to the above inequality and we get

$\displaystyle 2<\frac{b}{a}\sqrt{2002}+1<2+\frac{\lambda}{a^2}$

which gives

$\displaystyle \lambda>\frac{10}{\frac{b}{a}\sqrt{2002}+1}>\frac{10}{2+\lambda/a^2}.$

Taking ${a \rightarrow \infty}$ we obtain ${\lambda \geq 5}$.

Note that the estimation for ${\lambda}$ depends only on the value of ${k}$ which here is ${10}$ and in general ${\lambda=k/2}$. This problem also works for other numbers which have the property that the smallest ${k}$ such that ${k}$ is quadratic residue modulo one of its prime factors is at least ${10}$, and this is the case for ${2013=3\cdot 11\cdot 61}$. The first negative quadratic residues modulo ${61}$ are ${-1,-3,-4,-5,-9}$ while for ${11}$ we have ${-2,-6,-7,-8}$. The estimation can even be improved for ${2013}$, and the algorithm below gives that ${k=39}$ so if we have

$\displaystyle 0 < \sqrt{2013}-\frac{a}{b} < \frac{\lambda}{ab}$

for an infinity of pairs ${(a,b)}$ then ${\lambda \geq 19,5}$. Moreover (what a lucky coincidence), ${2013}$ is the first number for which ${k}$ is ${39}$. The number which has the greatest ${k}$ before ${2013}$ was ${1653}$ with ${k=29}$.

function res = min_res(n)

factors = unique(factor(n));

fac_max = n;

lis = 1:fac_max-1;

for m = factors
res_m = sort(mod((0:floor(m/2)).^2,m));
rest = mod(m-res_m(:),m);
partial = rest;
for k = 1:ceil(fac_max/m)-1
partial = [partial; k*m+rest];
end
partial(partial>fac_max)     = [];
lis      = intersect(lis,partial);
end

res = lis;