扩展欧几里得算法及欧拉公式

欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。

整数 a, b 的最大公约数一般表示为 gcd(a, b)

gcd(a, b) = gcd(b, a % b)

代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
// 当 a > b, 缩小问题规模的作用
// 当 a < b, 交换a, b位置的作用 
int gcd(int a, int b) {
    cout << "gcd(" << a << ", " << b << ") = ";
    if (b) return gcd(b, a % b);
    return a;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        cout << gcd(a, b) << endl;
    }
    return 0;
}

证明 1: b 和 a % b 的最大公约数，是 a 和 b 的公约数

设 b 和 a % b 的最大公约数为 C
则 b = y * C ① ， a % b = x * C ②
由 ② 得 a – k * b = x * C ③
由 ①、③ 得 a = (x + k * y) * C ④
由 ①、④ 可得：C 也是 a 和 b 的公约数

证明 2: b 和 a % b 的最大公约数也是 a 和 b 的最大公约数

反证法：假设a和b的最大公约数不是C，是d
由 ①、④可知：gcd（x + k * y， y）= d，且 d 不等于 1
所以 x + k * y = m * d; y = n * d;
所以x = m * d – k * y = (m – k * n) * d; y = n * d;
即 x = (m – k * n) * d；y = n * d; 故 x 与 y 之间存在公约数d；
由于“b 和 a % b 的最大公约数为 C”及①、② 可知，x 与 y 之间没有公约数；
5 与 6 相悖，故 1 不成立。

扩展欧几里得算法

裴蜀定理

裴蜀定理说明了对任何整数 a、b和它们的最大公约数 d ，关于未知数 x 以及 y 的线性的丢番图方程（称为裴蜀等式）。

若a、b是整数, 且 gcd(a, b) = d，那么对于任意的整数 x、y, ax + by 都一定是d的倍数

特别地，一定存在整数 x、y，使ax + by = d成立。

欧几里得算法证明裴蜀定理，求得裴蜀数（x、y的一组解）

在辗转相除的回溯过程中计算x、y。

第一种情况：a、b中有一个数为0时

gcd(c, 0) = x * c + y * 0 = c，可得：x = 1 、 y = 0

第二种情况：a与b都不为零时

a、b的递归过程为：( a, b ) -> ( b, a % b )

x、y的回溯过程为：( y, x – k * y ) <- ( x, y )

设x、y满足gcd(b, a % b) = c
所以 b * x + (a % b) * y = c ①
等价于： b * x + (a – k * b) * y = c
合并同类项：a * y + b * (x – k * y) = c ②
所以递归回溯的下一层 gcd(a, b) = c 满足 ②
下一层的x = y, y = x – k * y （k = a / b 向下取整）

代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

int ex_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int r = ex_gcd(b, a % b, x, y);
    int temp = y;
    y = x - a / b * y;
    x = temp;
    return r;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int x, y;
        int c = ex_gcd(a, b, x, y);
        cout << a << " * " << x << " + " << b << " * " << y << " = " << c << endl;
    }
    return 0;
}

扩展欧几里得算法的用途

a * x % b = c, c 是a、b的最大公约数，求x的值?

a * x – k * b = c
a * x + b * y = c

数论中的欧拉公式

欧拉定理 a^Ø(n) mod n = 1：对于互质的正整数a和n，有a^Ø(n) mod n = 1。

欧拉函数 Ø(n)：对于一个正整数n，小于n且与n互质的正整数（包括1）的个数，记做Ø(n)。

可推导结论：从0开始，每隔Ø(n)个数，a^Ø(n) mod n 等于1（循环）。

证明：

a^Ø(n) 的值集合为：S₁ = {x₁,x₂,x₃…x_Ø(n)}
a^Ø(n) 的值集合为：S₂ = {a*x₁,a*x₂,a*x₃…a*x_Ø(n)}
x₁ * x₂ * x₃… * x_Ø(n) ≡ a^Ø(n)* (x₁ * x₂ * x₃… * x_Ø(n) ) (mod n)
a^Ø(n) ≡ 1 （mod n）

欧拉函数 Ø(n)，代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
// 欧拉函数算法
// 在 1～n 这n个数中，2的倍数占比为1/2；
// 去掉2的倍数余下数中，3的倍数比例还是1/3；
// 再去掉3的倍数余下数中，5的倍数所占比例仍为1/5；
// 去掉的是不大于根号n的所有素数的倍数。
int phi(int n) {
    int x = 2, ans = n; // x:质因子, ans:欧拉函数的结果
    while (x * x <= n) { 
        // 将n写成其质因子幂的连乘积的形式
        // ϕ(N)=N∗(1−1/p1)∗(1−1/p2)∗...∗(1−1/pm)
        if (n % x == 0) ans = ans / x * (x - 1); // N∗(1−1/p1) 写法转化
        while (n % x == 0) n /= x;
        x += 1;
    }
    if (n != 1) ans -= ans / n; 
    return ans;
}

int main() {
    int n;
    while (cin >> n) {
        cout << "phi(" << n << ") = " << phi(n) << endl;
    }
    return 0;
}