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;
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: