连分数（二）——在数论中的应用

  本节我们介绍连分数在数论中的应用——解丢番图方程（连分数在数论中也有其它方面的应用，比如因式分解，但相关理论及算法相当复杂，不介绍。）。

  所谓的丢番图方程就是变量不少于2个，系数都是整数的代数方程，在数论中一般关心的是它们的整数解。比如ax+by=c；x²+y²=z²；xⁿ+yⁿ=zⁿ；x³+y³=z³+w³；x²-ny²=±1；...等都是丢番图方程（这里x,y,z,w表示未知量；a,b,c,...等字母表示系数，它们都是整数。）

    对于所有不同类型的丢番图方程，并不存在一个算法可以解出任意给定的丢番图方程（著名的希尔伯特第十个问题）。但对于某些类型的丢番图方程，我们有算法可以求出它们的解。本节介绍两种丢番图方程，应用连分数的知识可以求出它们的一般解（以及求解的算法）。

第一种是最简单的（两个变量的）线性丢番图方程。其一般形式有ax+by=c和ax-by=c两种（c是给定的整数，a,b都是给定的正整数）。我们先来看ax+by=c这种形式的方程。

  不失一般性我们可以假设a与b是互素的。否则若a与b的最大公约数d>1，则无论x和y取什么整数值，ax+by都能被d整除。于是c也必须能被d整除，否则c不能表示成ax+by形式，方程无解。因此a,b,c都能被d整除，于是我们可以把a,b,c都除以d，得到一个新方程a₁x+b₁y=c₁，这个方程的a₁与b₁是互素的，而它的解也是原方程的解。因此对任意a,b,c的方程ax+by=c，我们只需考虑a与b互素的情况的解就行了。

  我们先来看看解的结构。令x₀,y₀是一组解：ax₀+by₀=c，那么对于任意一组解(x,y)，有a(x-x₀)+b(y-y₀)=0，即a(x-x₀)=-b(y-y₀)。由于a与b互素，所以(x-x₀)能被b整除，(y-y₀)能被a整除，有(x-x₀)/b=-(y-y₀)/a。可设(x-x₀)/b=-(y-y₀)/a=t，于是有x=x₀+tb，y=y₀-ta。无论t取任何整数x=x₀+tb，y=y₀-ta都是原方程的解。

  另一种可以通过连分数求解的丢番图方程是佩尔方程，即形如x²-Dy²=1和x²-Dy²=-1（D是某个正整数）的方程。

  若D是某个正整数C的平方，即D=C²，则x²-Dy²=1可化为(x+Cy)(x-Cy)=1，于是只能有x+Cy=x-Cy=1或x+Cy=x-Cy=-1，于是x=1,y=0以及x=-1,y=0是其所有的解；类似的对于x²-Dy²=-1，若存在正整数C使得D=C²，则有x+Cy=1，x-Cy=-1或x+Cy=-1，x-Cy=1。此时只有在C=1的情况下才有解，有两组解：(0,1)，(0,-1)。

例5：x²-53y²=±1.

  参考文献

【1】CL. Lorentzen, H. Waadeland, Continued Fractions with Applications.

【2】Sergey Khrushchev, Orthogonal Polynomials and Continued Fractions_From Euler's Point of View (Encyclopedia of Mathematics and its Applications) .

【3】Olds, Carl D, Continued Fractions.