4.II.11H

Number Theory
Part II, 2008

Let N>1N>1 be an integer, which is not a square, and let pk/qk(k=1,2,)p_{k} / q_{k}(k=1,2, \ldots) be the convergents to N\sqrt{N}. Prove that

pk2qk2N<2N(k=1,2,)\left|p_{k}^{2}-q_{k}^{2} N\right|<2 \sqrt{N} \quad(k=1,2, \ldots)

Explain briefly how this result can be used to generate a factor base BB, and a set of BB-numbers which may lead to a factorization of NN.