# Given an integer n is there an efficient way to find integers p, q such that abs(p^2-n q^2) <= 1 ?

Oct 14, 2015

Assuming $n$ is not a perfect square:

Find the simple continued fraction expansion of $\sqrt{n}$, terminate it just before it repeats and expand to find $\frac{p}{q}$.

#### Explanation:

To find the simple continued fraction expansion of $\sqrt{n}$, use the following algorithm:

${m}_{0} = 0$
${d}_{0} = 1$
${a}_{0} = \left\lfloor \sqrt{n} \right\rfloor$

${m}_{i + 1} = {d}_{i} {a}_{i} - {m}_{i}$

${d}_{i + 1} = \frac{n - {m}_{i + 1}^{2}}{d} _ i$

${a}_{i + 1} = \left\lfloor \frac{{a}_{0} + {m}_{i + 1}}{d} _ \left(i + 1\right) \right\rfloor$

The continued fraction expansion is then [a_0; a_1, a_2, a_3,...]

$\sqrt{n} = {a}_{0} + \frac{1}{{a}_{1} + \frac{1}{{a}_{2} + \frac{1}{{a}_{3} + \frac{1}{\ldots}}}}$

This will repeat immediately after the first term satisfying ${a}_{i} = 2 {a}_{0}$

Stop just before the ${a}_{i} = 2 {a}_{0}$ term and compute the resulting fraction $\frac{p}{q}$. This will satisfy $\left\mid {p}^{2} - n {q}^{2} \right\mid = 1$

For example, consider $n = 6798$

${m}_{0} = 0$, ${d}_{0} = 1$, ${a}_{0} = \left\lfloor \sqrt{6798} \right\rfloor = 82$

Then:

${m}_{1} = {d}_{0} {a}_{0} - {m}_{0} = 1 \cdot 82 - 0 = 82$

${d}_{1} = \frac{n - {m}_{1}^{2}}{d} _ 0 = \frac{6798 - {82}^{2}}{1} = 74$

${a}_{1} = \left\lfloor \frac{{a}_{0} + {m}_{1}}{d} _ 1 \right\rfloor = \left\lfloor \frac{82 + 82}{74} \right\rfloor = 2$

${m}_{2} = {d}_{1} {a}_{1} - {m}_{1} = 74 \cdot 2 - 82 = 66$

${d}_{2} = \frac{n - {m}_{2}^{2}}{d} _ 1 = \frac{6798 - {66}^{2}}{74} = 33$

${a}_{2} = \left\lfloor \frac{{a}_{0} + {m}_{2}}{d} _ 2 \right\rfloor = \left\lfloor \frac{82 + 66}{33} \right\rfloor = 4$

${m}_{3} = {d}_{2} {a}_{2} - {m}_{2} = 33 \cdot 4 - 66 = 66$

${d}_{3} = \frac{n - {m}_{3}^{2}}{d} _ 2 = \frac{6798 - {66}^{2}}{33} = 74$

${a}_{3} = \left\lfloor \frac{{a}_{0} + {m}_{3}}{d} _ 3 \right\rfloor = \left\lfloor \frac{82 + 66}{74} \right\rfloor = 2$

${m}_{4} = {d}_{3} \cdot {a}_{3} - {m}_{3} = 74 \cdot 2 - 66 = 82$

${d}_{4} = \frac{n - {m}_{4}^{2}}{d} _ 3 = \frac{6798 - 6724}{74} = 1$

${a}_{4} = \left\lfloor \frac{{a}_{0} + {m}_{4}}{d} _ 4 \right\rfloor = \left\lfloor \frac{82 + 82}{1} \right\rfloor = 164 = 2 \cdot {a}_{0}$

So sqrt(6798) = [82;2,4,2,164,2,4,2,164,...]

[82;2,4,2] = 82+1/(2+1/(4+1/2))

$= 82 + \frac{1}{2 + \frac{1}{\frac{9}{2}}}$

$= 82 + \frac{1}{2 + \frac{2}{9}}$

$= 82 + \frac{1}{\frac{20}{9}}$

$= 82 + \frac{9}{20}$

$= \frac{1649}{20}$

So $p = 1649$ and $q = 20$

${p}^{2} = 2719201$

$n {q}^{2} = 6798 \cdot 400 = 2719200$

So $\frac{1649}{20}$ will be a good first approximation for a Newton Raphson type method to find $\sqrt{6798}$ accurately with the minimum waste digits.