裴蜀等式与扩展欧几里得算法

裴蜀等式

对于任何整数$a$、$b$和它们的最大公约数$d$，关于未知数$x$和$y$的线性丢番图方程称为裴蜀等式

$$ax+by=m$$有整数解时当且仅当$m$是$d$的倍数

裴蜀等式有解时必然有无穷多个整数解，每组解$x$、$y$都成为裴蜀数，$x$和$y$可用扩展欧几里得算法$(ExtendedEuclideanalgorithm)$求得

特别地，$ax+by=1$有整数解，当且仅当$a$和$b$互素

拓展欧几里得算法

欧几里得算法地终止状态是$a=gcd,b=0$，那么此时方程$ax+by=gcd$的解$x=1,y$为任意数

当然，上面说的是最终状态，但是我们能否从最终状态反推初始状态？

假设当前要求的是$a$和$b$的最大公约数，并求出$x$和$y$，使得$ax+by=gcd\cdot \cdot \cdot \cdot (Formula1)$

而我们已经求出了下一状态$b$和$a\%b$的最大公约数，并且也求出了一组解 x 1 x_1 x1​和 y 1 y_1 y1​，使得 b × x 1 + ( a % b ) × y 1 = g c d b\times x_1 + (a\%b)\times y_1 = gcd b×x1​+(a%b)×y1​=gcd

那么这两个状态之间是否存在某种关系呢？

我们知道$a\%b=a-(a/b)\times b$（这里的/指的是整除），那么可以进一步得到：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …

对比$Formula1$和$Formula2$，我们发现一个递推式
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} …
其中，$x$和$y$分别是递归时第$i$层$ax+by=gcd$的一组解， x 1 x_1 x1​和 y 1 y_1 y1​分别是递归时第$i+1$层 a x 1 + b y 1 = g c d ax_1+by_1=gcd ax1​+by1​=gcd的一组解

我们上面推到的其实都是$ax+by=d$的解，$d=gcd(a,b)$，对于一般的情况$m$为$d$的倍数，则有$ax+by=m$的解为 x × m d x \times \frac{m}{d} x×dm​和 y × m d y \times \frac{m}{d} y×dm​

public class exgcd {static long x, y;static long exgcd(long a, long b) {if (b == 0) {x = 1;y = 0;return a;}long res = exgcd(b, a % b);long x1 = x;x = y;y = x1 - (a / b) * y;return res;}/** 线性方程 ax + by = m 当m为gcd(a,b)的倍数时有整数解*/static long linearEquation(long a, long b, long m) throws Exception {long d = exgcd(a, b);if (m % d != 0)throw new Exception("无解");long n = m / d;x *= n;y *= n;return d;}public static void main(String[] args) {try {linearEquation(2, 7, 1);System.out.println(x + " " + y);} catch (Exception e) {System.out.println("无解");}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！