【数学】不定方程

b不定方程的相关内容，包括n元一次不定方程、毕达哥拉斯定理、费马大定理、佩尔方程。

一次不定方程

转化为一元线性同余方程

$n$ 元一次不定方程

转化为多元线性同余方程

毕达哥拉斯定理

$x^2+y^2=z^2$ ，当$\gcd(x,y,z)=1$ 时被称为本原的毕达哥拉斯三元组。

$本原的毕达哥拉斯三元组(x,y,z)且y为偶数\Leftrightarrow\exist m,n(m>n,m,n互素，不同奇偶),x=m^2-n^2,y=2mn,z=m^2+n^2$

费马大定理

$x^n+y^n=z^n,n\geq 3,n\in N$ 无非$0$ 整数解

佩尔方程

第一类佩尔方程

形如：$x^2-dy^2=1,d>1$

$d$ 是完全平方数$\Rightarrow$ 无解

解有迭代公式：

$x_{n}=x_{n-1} x_{1}+d y_{n-1} y_{1}\\ y_{n}=x_{n-1} y_{1}+y_{n-1} x_{1}$

推导：设特解$(x_1,y_1),(x_2,y_2)$ ，则有$x_{1}^{2}-d y_{1}^{2}=1,x_{2}^{2}-d y_{2}^{2}=1$ 则$\left(x_{1}^{2}-d y_{1}^{2}\right)\left(x_{2}^{2}-d y_{2}^{2}\right)=1$
展开，有

$\begin{aligned} &x_{1}^{2} x_{2}^{2}-d x_{1}^{2} y_{2}^{2}-d y_{1}^{2} x_{2}^{2}+d^{2} y_{1}^{2} y_{2}^{2}\\=&(x_{1}^{2} x_{2}^{2}+d^{2} y_{1}^{2} y_{2}^{2})-d(x_{1}^{2} y_{2}^{2}+y_{1}^{2} x_{2}^{2})\\ =&\left(x_{1} x_{2}+d y_{1} y_{2}\right)^{2}-d\left(x_{1} y_{2}+x_{2} y_{1}\right)^{2}\\ =&1 \end{aligned}$

逐次迭代可得上述迭代公式。

暴力迭代法

从$y=1$ 开始枚举验证，每次$+1$ 。

矩阵迭代法

第$k$ 个迭代解用矩阵表示如下：

$\left[\begin{array}{l}x_{k} \\ y_{k}\end{array}\right]=\left[\begin{array}{ll}x_{1} & d y_{1} \\ y_{1} & x_{1}\end{array}\right]^{k-1}\left[\begin{array}{l}x_{1} \\ y_{1}\end{array}\right]$

求出第一个特解后用矩阵快速幂求得第$k$ 个解。

第二类佩尔方程

形如：$x^2-dy^2=k,d>1$

解有迭代公式：

$x=p x_{1}+d q y_{1}\\y=p y_{1}+q x_{1}$

其中$(p,q)$ 是第二类佩尔方程的一个特解，$(x_1,y_1)$ 是第一类佩尔方程的最小特解。

推导：根据上述，有$p^2-dq^2=k,x_{1}^{2}-d y_{1}^{2}=1$ ，则$\left(x_{1}^{2}-d y_{1}^{2}\right)\left(p^{2}-d y^{2}\right)=k$

展开，有

$\begin{aligned} &x_{1}^{2} p^{2}-d x_{1}^{2} q^{2}-d y_{1}^{2} p^{2}+d^{2} y_{1}^{2} q^{2}\\=&(x_{1}^{2} p^{2}+d^{2} y_{1}^{2} q^{2})-d(x_{1}^{2} q^{2}+y_{1}^{2} p^{2})\\ =&\left(x_{1} p+d y_{1} q\right)^{2}-d\left(x_{1} q+p y_{1}\right)^{2}\\ =&k \end{aligned}$

逐次迭代可得上述迭代公式。

对于每一组特解$(p,q)$ ，第$k$ 个迭代解用矩阵表示如下：

$\left[\begin{array}{l}x_{k} \\ y_{k}\end{array}\right]=\left[\begin{array}{ll}p & d q \\ q& p\end{array}\right]^{k-1}\left[\begin{array}{l}x_{1} \\ y_{1}\end{array}\right]$

求出第一个特解后用矩阵快速幂求得第$k$ 个解。