数论概论读书笔记 33.丢番图逼近

大家好，欢迎来到IT知识分享网。

丢番图逼近

如何求出佩尔方程$x^2-Dy^2=1$的一个正整数解$x,y$？因式分解后得

$$(x-y\sqrt{D})(x+y\sqrt{D})=1$$

现在有一个问题， $x-y\sqrt{D}$可以小到什么程度？

如果能找到整数$x,y$使其非常小，则可以期望$x,y$是佩尔方程的一个解。

鸽巢原理

具体看书，不难理解

总之，证明了对任意整数$Y$，可以找到整数$x,y$使得

$$0 <y\le Y,\quad="" |x-y\sqrt{D}|<1="" Y="" <="" script=""> <br /> 随着 <span class="MathJax_Preview" style="color: inherit; display: none;"></span> <span class="MathJax" id="MathJax-Element-10-Frame" tabindex="0" style="position: relative;"> <span class="math" id="MathJax-Span-91" style="width: 0.888em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.732em; height: 0px; font-size: 120%;"><span style="position: absolute; clip: rect(1.305em, 1000.73em, 2.294em, -999.997em); top: -2.133em; left: 0em;"><span class="mrow" id="MathJax-Span-92"><span class="mi" id="MathJax-Span-93" style="font-family: MathJax_Math-italic;">Y<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.159em;"></span></span></span><span style="display: inline-block; width: 0px; height: 2.138em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 0.941em;"></span></span> <span class="MJX_Assistive_MathML"> Y </span></span> <script type="math/tex" id="MathJax-Element-10">Y$$ 的取值越来越大，我们可以自动得到新的 $x$和 $y$。

定理 狄利克雷的丢番图逼近定理—版本2 假设$\alpha&gt;0$是一个无理数，即 $\alpha$是一个不能表成分数a/b的实数，则存在无穷多个正整数对 $(x,y)$使得

$$|x-y\alpha|&lt;\frac{1}{y}$$

我们一直在使用比较蛮力的方法去寻找无理数的有理逼近。对每个$y$，选取最接近$y\alpha$的整数$x$并检查$x/y$与$\alpha$的接近程度。

有一种建立在连分数基础上寻找最佳逼近$x/y$的更加系统化的方法。后面会讨论。

连分数还提供了一个解佩尔方程的有效方法，即使解非常大时也能求解。