Bound on gcd of two integers

Question

Well this is a problem I was fiddling with. I came up with it but it probably is not original.

Suppose $a\in \mathbb{N}$ is not a perfect square. Then show that : $$\text{gcd}(n,\lfloor{n\sqrt{a}}\rfloor)\le c\sqrt n\tag{1}$$ Where $c=\sqrt[4]{4a}$ and P.S. it is the best constant, when $ax^2-y^2=1$ admits a solution.

Now I have a couple questions.

• When $ax^2-y^2=1$ has no solution, what could be the best constant $c$ in $(1)$ then?
• What about when $\dfrac{\text{gcd}(n,\lfloor{n\alpha}\rfloor)}{\sqrt n}$we have a irrational number $\alpha$ which is not a quadratic surd. For example, $\pi,\sqrt[3]{2}$ etc?

Any references or solutions would be helpful. Thanks.

Answer 1

For the second question, if $b = \sqrt{a}$ is an irrational number with very good rational approximations, there won't be an upper bound. For example, if $$ \dfrac{p}{q} + \dfrac{1}{q^r} > b > \dfrac{p}{q}$$ for coprime positive integers $p,q$ and integer $r>1$, then taking $n=q^r$ we have $\lfloor n b \rfloor = p q^{r-1}$ and $\gcd(\lfloor n b \rfloor, n) = q^{r-1} = n^{1-1/r}$. For example, you could take $$b = \sum_{j=0}^\infty 2^{-(r+1)^j}$$ and have this with $q = 2^{(r+1)^m}$ for all positive integers $m$.

Of course, Roth's theorem says for an algebraic number $b$ there will be only finitely many such $q$.

EDIT: Conversely, suppose $\gcd(\lfloor nb \rfloor, n) = g$, with $n=gu$ and $\lfloor nb \rfloor = g v$ for coprime positive integers $u$,$v$. Thus $$ \dfrac{v}{u} + \dfrac{1}{gu} > b > \dfrac{v}{u}$$ If $g > 2 u$, i.e. $g > \sqrt{2n}$, then $v/u$ must be a convergent of the continued fraction for $b$. Moreover, if we have a bound $a_k < M$ for the elements $a_k$ of this continued fraction, then $gu < (M+ 2) u^2$ so that $g < \sqrt{(M+2) n}$.

EDIT: In the case $b = \sqrt{3}$, the convergents of the continued fraction that are less than $b$ are $v_k/u_k$ where $u_k$ and $v_k$ both satisfy the recurrence $a_{k+2} = 4 a_{k+1} - a_k$, with $v_1 = 1$, $v_2 = 5$ while $u_1 = 1$, $u_2 = 3$, and $3 u_k^2 - v_k^2 = 2$. We can then take $$ \eqalign{g &= \left \lfloor \dfrac{1}{u_k \sqrt{3} - v_k}\right \rfloor = \left \lfloor \dfrac{u_k \sqrt{3} + v_k}{2}\right \rfloor \approx \dfrac{\sqrt{3}-1}{2} (2+\sqrt{3})^k\cr n &= g u_k \approx \left(\dfrac{\sqrt{3}}{3}-\dfrac{1}{2}\right) (2 + \sqrt{3})^{2k}\cr \dfrac{g}{\sqrt{n}} &\approx 3^{1/4}}$$

EDIT: A similar calculation for the case $b = \sqrt{7}$ seems to yield $g/\sqrt{n} \approx (28/9)^{1/4}$

Answer 2

Robert Israel's nice answer above already points to what happens if there are very good rational approximations to the irrational number $\alpha$. Let me just address the first question when $\alpha =\sqrt{a}$ is a quadratic irrational (with $a$ being a non-square natural number). Let $k$ be the least positive number that can be expressed as $ax^2-y^2$. Then the best constant in the bound for the gcd is $\sqrt{2\sqrt{a}/k}$.

To see this, suppose $g=(n,\lfloor n\alpha \rfloor)$, and write $n=gv$ and $\lfloor n\alpha \rfloor =gu$. Then $$ \frac{1}{n} > \alpha -\frac{u}{v} > 0, $$ and multiplying both sides by $\alpha+u/v \le 2\alpha$ we get $$ \frac{2\alpha}{n} \ge \alpha^2 -\frac{u^2}{v^2} \ge \frac{k}{v^2}, $$ since $k$ is the smallest positive number of the form $a x^2- y^2$. Since $v=n/g$, we conclude that $$ g^2 \le \frac{2\alpha}{n} \frac{n^2}{k} = \frac{2\alpha n}{k}, $$ which is the claimed bound.

To see that this bound is asymptotically attained, take a solution to $ax^2 -y^2 =k$ and by multiplying by a solution to the Pell equation $x^2-ay^2=1$ we can find a solution to $ax^2 -y^2 =k$ with $x$ and $y$ arbitrarily large. Further such $x$ and $y$ may be assumed to be coprime by the minimality of $k$. For such a choice we know that $$ \alpha - \frac{y}{x} \approx \frac{k}{2\alpha x^2}, $$ and choosing $n= x \lfloor (1-\epsilon) 2\alpha x/k\rfloor$ produces a large gcd for $n$ and $\lfloor n\alpha\rfloor$.

Finally the negative Pell equation $ax^2-y^2=1$ has been extensively studied, and still remains not fully understood. See for example this impressive recent paper of Fouvry and Kluners in Annals. It may also be interesting to note that there do exist $a$ for which $k$ is essentially as large as possible: namely take $a$ of the form $b(b+2)$ and then the corresponding $k$ is $2b$. (One can see this from the fact that the continued fraction expansion for $\sqrt{b(b+2)}$ is $[b;1,2b,1,2b,\ldots]$.)