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

1 Answer
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 #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 = floor(sqrt(n))#

#m_(i+1) = d_i a_i - m_i#

#d_(i+1) = (n - m_(i+1)^2)/d_i#

#a_(i+1) = floor((a_0 + m_(i+1)) / d_(i+1))#

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

#sqrt(n) = a_0 + 1/(a_1 + 1/(a_2 + 1/(a_3 + 1/...)))#

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 #p/q#. This will satisfy #abs(p^2 - n q^2) = 1#

For example, consider #n = 6798#

#m_0 = 0#, #d_0 = 1#, #a_0 = floor(sqrt(6798)) = 82#

Then:

#m_1 = d_0 a_0 - m_0 = 1*82 - 0 = 82#

#d_1 = (n - m_1^2) / d_0 = (6798 - 82^2) / 1 = 74#

#a_1 = floor((a_0 + m_1) / d_1) = floor((82 + 82) / 74) = 2#

#m_2 = d_1 a_1 - m_1 = 74 * 2 - 82 = 66#

#d_2 = (n - m_2^2) / d_1 = (6798 - 66^2) / 74 = 33#

#a_2 = floor((a_0 + m_2)/d_2) = floor((82 + 66) / 33) = 4#

#m_3 = d_2 a_2 - m_2 = 33 * 4 - 66 = 66#

#d_3 = (n - m_3^2) / d_2 = (6798 - 66^2) / 33 = 74#

#a_3 = floor((a_0 + m_3) / d_3) = floor((82 + 66) / 74) = 2#

#m_4 = d_3 * a_3 - m_3 = 74 * 2 - 66 = 82#

#d_4 = (n - m_4^2) / d_3 = (6798 - 6724) / 74 = 1#

#a_4 = floor((a_0 + m_4) / d_4) = floor((82+82)/1) = 164 = 2 * 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+1/(2+1/(9/2))#

#=82+1/(2+2/9)#

#=82+1/(20/9)#

#=82+9/20#

#=1649/20#

So #p = 1649# and #q = 20#

#p^2 = 2719201#

#n q^2 = 6798 * 400 = 2719200#

So #1649/20# will be a good first approximation for a Newton Raphson type method to find #sqrt(6798)# accurately with the minimum waste digits.