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

∣pk2−qk2N∣<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.

Typos? Please submit corrections to this page on GitHub.