扩展欧几里得算法求解线性同余方程

# 1. 算法介绍

## 1.1 欧几里得算法简介

欧几里得算法，又称辗转相除法，用于计算两个非负整数的最大公约数。该算法基于以下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。欧几里得算法通过递归或迭代的方式求解，是计算机最常用的求解最大公约数的方法之一。

## 1.2 线性同余方程的定义与求解

在线性代数和数论中，线性同余方程指的是形如 ax ≡ b (mod m) 的方程，其中 a、b 和 m 为已知整数，x 为未知数，符号 ≡ 表示同余。求解线性同余方程就是要找到模 m 下满足方程的整数 x 的值。

## 1.3 扩展欧几里得算法的原理

扩展欧几里得算法是欧几里得算法的扩展，它不仅可以求解两个数的最大公约数，还可以找到两个数的线性组合使得其最大公约数等于两数的最大公约数。扩展欧几里得算法基于以下原理：对于整数 a、b，存在整数 x、y 使得 ax + by = gcd(a, b)，其中 gcd(a, b) 表示 a 和 b 的最大公约数。
## 扩展欧几里得算法的实现

欧几里得算法可以求解最大公约数，但扩展欧几里得算法通过辗转相除法，不仅可以求解最大公约数，还可以找到一对整数$x$和$y$，使得$ax + by = \text{gcd}(a, b)$。这个性质在求解线性同余方程中有很大的用处。

### 2.1 递归实现

下面是使用Python实现的递归版本扩展欧几里得算法的示例代码：

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_gcd(b, a % b)
        return d, y, x - (a // b) * y

#### 代码说明：
- `extended_gcd`函数接受两个参数$a$和$b$，返回值为$d, x, y$，其中$d$为$a$和$b$的最大公约数，$x$和$y$满足$ax + by = \text{gcd}(a, b)$。
- 如果$b$等于0，递归结束，此时$a$就是最大公约数，$x$为1，$y$为0。
- 如果$b$不等于0，递归调用`extended_gcd`函数，并用$b$和$a\%b$作为参数进行递归。
- 最终返回最大公约数$d$，以及满足线性关系的$x$和$y$。

### 2.2 非递归实现

下面是使用Java实现的非递归版本扩展欧几里得算法的示例代码：

public static int[] extendedGcd(int a, int b) {
    int[] result = new int[3];
    int x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        int q = a / b;
        int tmp;

        tmp = a % b;