## Best approximation of a certain square root

Let be a real number such that the inequality

holds for an infinity of pairs of natural numbers. Prove that .

*Solution:* We know that . Then there exists a positive integer such that . Let’s find the smallest value for . We factor and we get . We see that is a quadratic residue modulo . Let’s enumerate these quadratic residues:

Now we can pick the values of one at a time to see which one is the smallest and verifies that is quadratic residue modulo .

- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : is not quadratic residue modulo ;
- : has residues modulo (respectively) and they are all quadratic residues.

Therefore and we find that . Using the hypothesis and the new found inequality we find:

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

We know that

Since take infinitely many values, we find that approximates the irrational number so (and ) get arbitrary large in order to do that. We add to the above inequality and we get

which gives

Taking we obtain .

Note that the estimation for depends only on the value of which here is and in general . This problem also works for other numbers which have the property that the smallest such that is quadratic residue modulo one of its prime factors is at least , and this is the case for . The first negative quadratic residues modulo are while for we have . The estimation can even be improved for , and the algorithm below gives that so if we have

for an infinity of pairs then . Moreover (what a lucky coincidence), is the first number for which is . The number which has the greatest before was with .

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;