Convergents as solution to $x^2 - dy^2=m, m \leq \sqrt d$

184 Views Asked by At

Let $d$ and $m$ be positive integers such that $d$ is not a square and such that $m\leq\sqrt{d}$. I want to prove that if $x$ and $y$ are positive integers satisfying $x^2-dy^2=m$, then $x/y$ is a convergent of $\sqrt d$.

Any hints how I can prove such statement? I don't know where to start.

1

There are 1 best solutions below

0
On

This is similar to Theorem 7.24 in I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991.

You asked for hints, so read just enough of the proof so that you can finish it yourself. If you do not already have Theorem (3), which is needed to complete the proof, you can do the same at the referenced document.

Rearranging the equation, we have $$\frac{x}{y} - \sqrt d = \frac{m}{y(x + y\sqrt d)},$$ and hence $$0 < \frac{x}{y} - \sqrt d \le \frac{\sqrt d}{y(x + y\sqrt d)} = \frac{1}{y^2(x/(y\sqrt d) + 1)}.$$

Also, $0 < x/y - \sqrt d$ implies $x/(y\sqrt d) > 1$, and therefore $$\frac{x}{y} - \sqrt d < \frac{1}{y^2(1 + 1)} = \frac{1}{2y^2}.$$ By Theorem (3), $x/y$ is a convergent of $\sqrt d$.