贝祖公式简介

欧几里得算法（即辗转相除法）

• 在这里不再过多描述该算法，高中的时候学过的，在这里直接附代码。

public static int gcd(int m,int n) {
		return n == 0?m:gcd(n, m%n);
	}

贝祖等式

• 简单描述：ax + by = m 有整数解时，当且仅当m是d的倍数，d是a和b的最大公约数。

• 在这里做一下主要的分析
  （1）ax + by = gcd;
  （2）bx₁ + (a%b)y₁ = gcd;
  因为a%b = a - a/b * b，例如5 % 3 = 5 - 5/3 * 3 = 2
  所以（3）gcd = bx₁ + （a-（a/b）b）y₁
  =bx₁+ay₁-（a/b）by₁
  =ay₁+b（x₁ -（a/b）y₁）
  由式子（1）（3），可得
  x = y₁; y₁ = x₁ - （a/b）y₁

• 代码模板如下

public class Main {
	static long x,y;
	public static void main(String[] args) {
		linearEquation(2,7,1);
	}
	//求解最大公因数
	public static long gcd(long m,long n) {
		return n == 0?m:gcd(n, m%n);
	}
	//求解最小公倍数
	public static long lcm(long a,long b) {
		return (a * b)/gcd(a, b);
	}
	
	public static long ext_gcd(long a,long b) {
		if(b == 0) {
			x = 1;
			y = 0;
			return a;
		}
		long res = ext_gcd(b, a%b);
		long x1 = x;
		x = y;
		y = x1 - a/b * y;
		return res;
	}
	//线性方程 ax + by = m,当m是gcd(a.b)的倍数时有解
	public static long linearEquation(long a,long b,long m) {
		long d = ext_gcd(a, b);
		if(m % d != 0) {
			System.out.println("无解");
		}else {
			long n = m / d;
			x *= n;
			y *= n;
			System.out.println(x + " "+y);
		}
		return d;
	}
}

• 在这里我们根据代码举个例子分析
  例：2x + 7y = 1;
  过程如下：
  gcd(2,7) => gcd(7,2) = > gcd(2,1) = >gcd(1,0),
  注意到了b==0时，x = 1,y = 0,根据前面的公式 x = y1; y1 = x1 - （a/b）y1，我们可以得到x = 0,y = 1;此时a = 7,b = 2,根据公式可得：x = 1,y = -3;此时a = 2,b = 7,根据公式可得：x = -3,y = 1。那么结果就出来了。

贝祖等式扩展（求解同余方程）

• 简单描述： a,b对m取模的结果相同，记为 a ≡ b ( mod m ) 即 a mod m = = b mod m
  如果 a ≡ b ( mod m ) a ，且 c ≡ d ( mod m ) ，则

• a+b≡c+d(mod m)
• a×b≡c×d(mod m)
  同余方程
  设有同余方程 a x ≡ b ( mod n ) a对于未知数 x 有解, 当且仅当 b是 gcd ( a , n )的倍数。且方程有解时，方程有gcd(a,n)个解。
  求解方程a x ≡ b ( mod n ) 相当于求解ax + ny = b(x,y为整数)。
  Why?
  因为ax mod n = = b mod n
  即左边：ax - （ax/n）* n = 余数
  右边：bx - （bx/n）* n = 余数
  故 ax = ny1 + 余数，bx = ny2 + 余数
  合并，得ax + ny = b,又回归到求解线性方程。

• 模的逆元
  模的逆元与同余方程类似，唯一不同的是(模的逆元表达式ax≡ 1 ( mod m ))b == 1,即只需要求解ax + ny = 1就行了。