Lagrange 如何用连分数理论推导出一次同余方程的通解？

拉格朗日（JosephLouis Lagrange）利用连分数理论推导一次同余方程的通解，这是一个非常巧妙且深刻的数学成果。它将看似独立的数论问题与连分数这种代数工具联系起来，展示了数学的内在统一性。

下面我将详细阐述拉格朗日是如何做到的，并尽量详细地解释其中的数学原理。

1. 问题背景：一次同余方程

我们要解决的是一个一次同余方程：

$ax equiv b pmod{m}$

其中，$a, b, m$ 是已知的整数，$m > 0$。我们希望找到所有满足这个方程的整数 $x$。

2. 方程解的存在性条件

首先，这个方程有解的充要条件是 $gcd(a, m)$ 整除 $b$。

为什么？
如果 $ax equiv b pmod{m}$，那么 $ax b = km$ 对于某个整数 $k$ 成立。
令 $d = gcd(a, m)$。那么 $d$ 整除 $a$ 且 $d$ 整除 $m$。
因此，$d$ 整除 $ax$ 和 $km$。
所以，$d$ 必须整除 $ax km$，也就是 $d$ 必须整除 $b$。
反之，如果 $d | b$，我们可以将同余方程除以 $d$：
$(a/d)x equiv (b/d) pmod{(m/d)}$
此时 $gcd(a/d, m/d) = 1$，这意味着 $(a/d)$ 在模 $(m/d)$ 下有乘法逆元，因此存在唯一解 modulo $(m/d)$。

3. 将同余方程转化为丢番图方程

为了利用连分数，我们首先将同余方程 $ax equiv b pmod{m}$ 转化为一个线性丢番图方程。
这意味着存在一个整数 $y$，使得：

$ax my = b$

这是一个关于 $x$ 和 $y$ 的二元一次线性丢番图方程。

4. 使用扩展欧几里得算法求解丢番图方程

传统的求解 $ax + by = c$ 类型丢番图方程的方法是使用扩展欧几里得算法。拉格朗日的方法虽然也依赖于欧几里得算法的思想，但通过连分数的形式来展现。

考虑基础方程 $ax' + my' = gcd(a, m)$。如果 $d = gcd(a, m)$ 且 $d | b$，那么方程 $ax my = b$ 的一个特解可以由基础方程的解乘以 $b/d$ 得到。

5. 连分数与欧几里得算法的联系

欧几里得算法用于求解两个整数的最大公约数，其步骤可以用连分数来表示。对于两个正整数 $a$ 和 $m$，我们可以通过一系列除法来计算 $gcd(a, m)$：

$a = q_1 m + r_1$
$m = q_2 r_1 + r_2$
$r_1 = q_3 r_2 + r_3$
...
$r_{n1} = q_{n+1} r_n + 0$

这里的 $q_i$ 是商，$r_i$ 是余数，最终的非零余数 $r_n$ 就是 $gcd(a, m)$。

这些等式可以写成：

$r_1 = a q_1 m$
$r_2 = m q_2 r_1 = m q_2 (a q_1 m) = (q_2) a + (1 + q_1 q_2) m$
$r_3 = r_1 q_3 r_2 = (a q_1 m) q_3 ((q_2) a + (1 + q_1 q_2) m)$
$r_3 = (1 + q_3 q_2) a + (q_1 q_3 q_1 q_2 q_3) m$

我们可以看到，每一级的余数 $r_i$ 都可以表示成 $a$ 和 $m$ 的线性组合：$r_i = s_i a + t_i m$。

连分数的表示：
将上述欧几里得算法的过程写成连分数形式：

$frac{a}{m} = q_1 + frac{r_1}{m} = q_1 + frac{1}{frac{m}{r_1}} = q_1 + frac{1}{q_2 + frac{r_2}{r_1}} = q_1 + frac{1}{q_2 + frac{1}{frac{r_1}{r_2}}} = dots$

这构成了 $frac{a}{m}$ 的一个有限连分数表示：
$frac{a}{m} = [q_1; q_2, q_3, dots, q_{n+1}]$

收敛分数与欧几里得算法的联系：
连分数的收敛分数（convergents）是其渐近线。令 $frac{p_k}{q_k}$ 是 $frac{a}{m}$ 的第 $k$ 个收敛分数。这些收敛分数可以通过递推关系得到：

$p_0 = q_1, q_0 = 1$
$p_1 = q_2 p_0 + 1, q_1 = q_2 q_0$ (注意：此处我的符号与标准表示略有不同，为了配合后续推导，$p_0/q_0$ 应该是 $q_1/1$ 或者将 $q_0=1, p_0=0$ 或 $p_0=1, q_0=0$ 作为初值，使用标准的递推公式更清晰：)

标准的递推关系是：
$p_{2}=0, p_{1}=1$
$q_{2}=1, q_{1}=0$
$p_k = q_k p_{k1} + p_{k2}$
$q_k = q_k q_{k1} + q_{k2}$

其中 $q_k$ 是连分数的系数。
对于 $frac{a}{m} = [q_1; q_2, dots, q_{n+1}]$，我们有：
$frac{p_k}{q_k} = [q_1; q_2, dots, q_k]$

关键的性质是：对于每一个 $k$（除了 $q_k$ 为零的情况，这里不会发生），$gcd(p_k, q_k) = 1$ 并且存在整数 $y_k$ 使得：

$ap_k mq_k = (1)^k gcd(a, m)$ （这里的形式可能需要根据 $a$ 和 $m$ 的相对大小调整，更准确地说，是 $p_k/q_k$ 是 $a/m$ 的渐近线，满足 $ap_k mq_k = ext{const}$，具体常数与 $a$ 和 $m$ 的关系有关）。

让我们回到欧几里得算法的线性组合表示：
$r_n = s_n a + t_n m = gcd(a, m)$
这里的 $s_n$ 和 $t_n$ 是整数。
这些系数 $s_n$ 和 $t_n$ 可以通过计算收敛分数的分子和分母来获得。
具体来说，令 $frac{p_k}{q_k}$ 是 $frac{a}{m}$ 的收敛分数，则有：
$ap_k mq_k = (1)^k q_k'$ （其中 $q_k'$ 是除法过程中的另一个部分）

一个更直接的联系：
我们可以通过欧几里得算法直接找到 $ax' + my' = gcd(a, m)$ 的解。
假设我们已经用欧几里得算法得到一系列等式：
$a = q_1 m + r_1$
$m = q_2 r_1 + r_2$
...
$r_{n1} = q_{n+1} r_n$

令 $d = gcd(a, m) = r_n$.
我们可以从最后一个非零余式开始，向上回代，将 $d$ 表示为 $a$ 和 $m$ 的线性组合：
$d = r_n$
$d = r_{n1} q_{n+1} r_n$ (这一步是错误的，应该是从 $r_{n2}$ 开始回代)
$r_n = r_{n2} q_n r_{n1}$
$r_{n1} = r_{n3} q_{n1} r_{n2}$
...
$r_1 = a q_1 m$

最终会得到 $d = ax_0 + my_0$ 形式的解。

拉格朗日的核心思想是将这一过程与连分数联系起来：
当我们将 $a/m$ 写成连分数 $[q_1; q_2, dots, q_{n+1}]$ 时，其最后的收敛分数 $frac{p_{n+1}}{q_{n+1}}$ （或者更准确地说，是 $frac{p_n}{q_n}$，这取决于索引的定义）将满足一个特殊的性质。

假设 $frac{a}{m} = [q_1; q_2, dots, q_N]$。
考虑 $frac{p_{N1}}{q_{N1}} = [q_1; q_2, dots, q_{N1}]$.
根据性质，有 $a q_{N1} m p_{N1} = (1)^{N1} gcd(a, m)$ 的形式。
（注意：这里需要谨慎处理，因为 $a/m$ 的连分数是有限的，最后一个商 $q_N$ 可能与 $a$ 和 $m$ 的关系有关）。

更清晰的路径：
拉格朗日关注的不是 $a/m$ 本身的连分数，而是寻找一个数 $x$ 使得 $ax equiv b pmod m$。
这等价于 $ax my = b$。
除以 $d = gcd(a, m)$ 得到 $(a/d)x (m/d)y = b/d$.
令 $a' = a/d$, $m' = m/d$, $b' = b/d$. 现在问题变成 $a'x equiv b' pmod{m'}$，其中 $gcd(a', m') = 1$.

现在我们需要解决 $a'x m'y = b'$。
由于 $gcd(a', m') = 1$, 我们可以将问题转化为找到 $a'$ 在模 $m'$ 下的乘法逆元。
也就是说，我们需要找到一个整数 $x_0$ 使得 $a'x_0 equiv 1 pmod{m'}$.

连分数如何找到乘法逆元？
当 $gcd(a', m') = 1$ 时，$a'/m'$ 的连分数表示的性质是，其最后的收敛分数 $frac{p_k}{q_k}$ 将满足 $a'q_k m'p_k = pm 1$.
令 $frac{a'}{m'} = [q_1; q_2, dots, q_N]$.
那么，其第 $N1$ 个收敛分数 $frac{p_{N1}}{q_{N1}}$ 将满足：
$a'q_{N1} m'p_{N1} = (1)^{N1} imes 1$ (因为 $gcd(a', m') = 1$).

也就是说，$a'q_{N1} equiv (1)^{N1} pmod{m'}$.
那么，如果 $(1)^{N1} = 1$，我们就有 $a'q_{N1} equiv 1 pmod{m'}$. 此时，$x_0 = q_{N1}$ 就是一个解。
如果 $(1)^{N1} = 1$，我们就有 $a'q_{N1} equiv 1 pmod{m'}$. 乘以 $1$ 就得到 $a'(q_{N1}) equiv 1 pmod{m'}$. 此时，$x_0 = q_{N1}$ 就是一个解。

总结找到逆元的过程：
1. 将 $a'/m'$ 写成连分数 $[q_1; q_2, dots, q_N]$.
2. 计算其倒数第二个收敛分数的分子 $p_{N1}$ 和分母 $q_{N1}$.
3. 根据性质 $a'q_{N1} m'p_{N1} = (1)^{N1}$.
4. 乘法逆元 $x_0$ 是 $q_{N1}$ 或者 $q_{N1}$ (取模 $m'$ 后的结果)。

回到原方程 $ax equiv b pmod m$

1. 计算 $d = gcd(a, m)$。如果 $b$ 不能被 $d$ 整除，无解。
2. 令 $a' = a/d, m' = m/d, b' = b/d$. 我们需要解 $a'x equiv b' pmod{m'}$.
3. 利用连分数找到 $a'$ 在模 $m'$ 下的乘法逆元 $inv(a', m')$.
将 $a'/m'$ 写成连分数 $[q_1; q_2, dots, q_N]$.
计算收敛分数 $frac{p_{N1}}{q_{N1}}$.
$inv(a', m') equiv (1)^{N1} q_{N1} pmod{m'}$.
4. 将 $b'$ 乘以逆元：
$x_0 equiv b' imes inv(a', m') pmod{m'}$
$x_0 equiv (b/d) imes ((1)^{N1} q_{N1}) pmod{(m/d)}$

通解

一旦我们找到一个特解 $x_0$ 满足 $ax_0 equiv b pmod m$，那么方程的通解由以下形式给出：

$x equiv x_0 + k frac{m}{d} pmod{m}$

其中 $k$ 是任意整数。
这意味着共有 $d$ 个不同的解模 $m$。

拉格朗日方法的优势和意义

系统性: 连分数提供了一种系统性的方法来解决欧几里得算法中出现的线性丢番图方程，从而间接解决了同余方程。
理论联系: 它揭示了数论中的同余方程问题与代数工具连分数之间的深刻联系。
算法实现: 连分数的计算过程（通过欧几里得算法）本身就是一种有效的算法，因此这种方法可以用来实际计算同余方程的解。

一个具体的例子

解同余方程 $7x equiv 3 pmod{11}$

1. $a=7, b=3, m=11$.
2. $gcd(7, 11) = 1$. 因为 $1$ 整除 $3$，所以有解。
3. 我们需要找到 $7$ 在模 $11$ 下的乘法逆元。问题转化为 $7x equiv 1 pmod{11}$.
4. 将 $7/11$ 写成连分数：
$11 = 1 cdot 7 + 4$
$7 = 1 cdot 4 + 3$
$4 = 1 cdot 3 + 1$
$3 = 3 cdot 1 + 0$
所以 $7/11 = [0; 1, 1, 1, 3]$.
注意，这里的第一个系数是 $q_1=0$，因为 $7 < 11$. 通常我们写 $a/m$ 的连分数，如果 $a Let's reevaluate:
$11 = 1 cdot 7 + 4$
$7 = 1 cdot 4 + 3$
$4 = 1 cdot 3 + 1$
$1 = 1 cdot 0 + 1$ (This last step is unusual, but means we stop at remainder 1)

So, $11/7 = [1; 1, 1, 3]$. The sequence of quotients is $1, 1, 1, 3$.
Let's use $a=7, m=11$. We want to solve $7x equiv 1 pmod{11}$.
This means we are looking for $x$ such that $7x = 1 + 11y$.
$7x 11y = 1$.
Let's use the extended Euclidean algorithm directly on $7x 11y = 1$:
$11 = 1 cdot 7 + 4$
$7 = 1 cdot 4 + 3$
$4 = 1 cdot 3 + 1$

From $4 = 1 cdot 3 + 1$, we get $1 = 4 1 cdot 3$.
Substitute $3 = 7 1 cdot 4$:
$1 = 4 1 cdot (7 1 cdot 4) = 4 7 + 4 = 2 cdot 4 7$.
Substitute $4 = 11 1 cdot 7$:
$1 = 2 cdot (11 1 cdot 7) 7 = 2 cdot 11 2 cdot 7 7 = 2 cdot 11 3 cdot 7$.
So we have $7(3) 11(2) = 1$.
This means $7(3) equiv 1 pmod{11}$.
The inverse of $7$ modulo $11$ is $3 equiv 8 pmod{11}$.

Now, let's connect this with連分數 and convergents properly.
We are solving $ax equiv b pmod m$.
Let's find the inverse of $a$ modulo $m$ when $gcd(a, m) = 1$.
We write $m/a$ as a continued fraction.
$11/7 = [1; 1, 1, 3]$.
Quotients are $q_1=1, q_2=1, q_3=1, q_4=3$.
Convergents $frac{p_k}{q_k}$:
$k=0: p_0=1, q_0=0$ (for calculation of p1, q1)
$k=1: q_1=1$. $p_1 = q_1 p_0 + 1 = 1$. $q_1 = q_1 q_0 + 0 = 0$? No, $p_0=q_1$, $q_0=1$. This convention is messy.

Let's use the property: $a q_{N1} m p_{N1} = (1)^{N1} gcd(a,m)$ for $m/a$.
Here $a=7, m=11$. $m/a = 11/7 = [1; 1, 1, 3]$. $N=4$.
$a=7, m=11$.
$q_1 = 1$
$q_2 = 1$
$q_3 = 1$
$q_4 = 3$

Convergents of $11/7$:
$k=0: p_0=1, q_0=0$
$k=1: q_1=1. p_1=1, q_1=1$. $frac{p_1}{q_1} = 1/1$.
$k=2: q_2=1. p_2=1cdot1+1=2, q_2=1cdot1+0=1$. $frac{p_2}{q_2} = 2/1$.
$k=3: q_3=1. p_3=1cdot2+1=3, q_3=1cdot1+1=2$. $frac{p_3}{q_3} = 3/2$.
$k=4: q_4=3. p_4=3cdot3+2=11, q_4=3cdot2+1=7$. $frac{p_4}{q_4} = 11/7$.

The property relates $a cdot q_{k1} m cdot p_{k1}$ for $a/m$. Here we use $m/a$.
The property is $p_k' m q_k' a = (1)^{k+1}$ for $m/a = [q_1; q_2, dots]$.
Using $m/a = 11/7 = [1; 1, 1, 3]$:
We look at the last convergent before the full fraction $11/7$.
This is $3/2$. So $p_3'=3, q_3'=2$.
$p_3' m q_3' a = 3 cdot 11 2 cdot 7 = 33 14 = 19 eq pm 1$. This is not correct.

The property is: If $frac{p_k}{q_k}$ are convergents of $frac{alpha}{eta}$, then $alpha q_k eta p_k = (1)^k gamma_k$, where $gamma_k$ is some integer related to the remainder.
For a finite continued fraction $frac{a}{m} = [q_1; q_2, dots, q_N]$, we have:
$a q_{N1} m p_{N1} = (1)^N imes ext{numerator of last remainder}$ if we use $a/m$.

Let's reconsider $a'x equiv b' pmod{m'}$. $gcd(a', m')=1$.
We need inverse of $a'$ mod $m'$.
Let's find convergents of $a'/m' = 7/11$.
$7/11 = [0; 1, 1, 1, 3]$.
$q_1=0, q_2=1, q_3=1, q_4=1, q_5=3$.
Convergents for $7/11$:
$p_{1}=1, q_{1}=0$
$p_0=0, q_0=1$
$k=1: q_1=0. p_1=0cdot1+1=1, q_1=0cdot0+1=1$. $frac{p_1}{q_1} = 1/1$.
$k=2: q_2=1. p_2=1cdot1+0=1, q_2=1cdot1+1=2$. $frac{p_2}{q_2} = 1/2$.
$k=3: q_3=1. p_3=1cdot1+1=2, q_3=1cdot2+1=3$. $frac{p_3}{q_3} = 2/3$.
$k=4: q_4=1. p_4=1cdot2+3=5, q_4=1cdot3+2=5$. $frac{p_4}{q_4} = 5/5$? ERROR in calculation.
Let's recalculate $7/11$:
$7/11 = [0; 1, 1, 1, 3]$
$q_1 = 0$
$q_2 = 1$
$q_3 = 1$
$q_4 = 1$
$q_5 = 3$

$p_{2}=0, p_{1}=1$
$q_{2}=1, q_{1}=0$

$k=1: q_1=0. p_1 = 0cdot1+0=0, q_1=0cdot0+1=1$. $frac{p_1}{q_1} = 0/1$. (This is $p_0/q_0$ in standard notation for $a/b$)
Let's use $a=7, b=11$ for $a/b$.
$q_1=0, q_2=1, q_3=1, q_4=1, q_5=3$.
$p_0=0, q_0=1$
$p_1=1, q_1=0$ (This is not helpful with 0indexed $q_i$ in the list)

Let's use the general property: $alpha frac{p_{k1}}{q_{k1}} eta frac{p_{k1}}{q_{k1}} = (1)^k$ for $alpha/eta$.
Here $alpha=7, eta=11$.
$7/11 = [0; 1, 1, 1, 3]$
Quotients: $q_1=0, q_2=1, q_3=1, q_4=1, q_5=3$.
The convergents of $7/11$ are $frac{p_k}{q_k}$.
$k=1$ (for $q_1=0$): $p_1=0, q_1=1$. $0/1$.
$k=2$ (for $q_2=1$): $p_2=1cdot0+1=1, q_2=1cdot1+0=1$. $1/1$.
$k=3$ (for $q_3=1$): $p_3=1cdot1+0=1, q_3=1cdot1+1=2$. $1/2$.
$k=4$ (for $q_4=1$): $p_4=1cdot1+1=2, q_4=1cdot2+1=3$. $2/3$.
$k=5$ (for $q_5=3$): $p_5=3cdot2+1=7, q_5=3cdot3+2=11$. $7/11$.

The property is $7 q_{k} 11 p_{k} = (1)^{k+1}$ for the convergents of $7/11$. Let's check.
For $k=4$, $frac{p_4}{q_4} = 2/3$.
$7 q_4 11 p_4 = 7 cdot 3 11 cdot 2 = 21 22 = 1$.
This means $7 cdot 3 equiv 1 pmod{11}$.
We need $7x equiv 1 pmod{11}$.
Multiply by $1$: $7 cdot (3) equiv 1 pmod{11}$.
So, $x_0 = 3 equiv 8 pmod{11}$.

Now, back to the original equation: $7x equiv 3 pmod{11}$.
We found the inverse of $7 pmod{11}$ is $8$.
So, $x equiv 3 imes 8 pmod{11}$.
$x equiv 24 pmod{11}$.
$x equiv 2 pmod{11}$.

Let's check: $7 cdot 2 = 14 equiv 3 pmod{11}$. Correct.

The general solution is $x equiv 2 + k frac{11}{gcd(7,11)} pmod{11}$.
$x equiv 2 + k cdot 11 pmod{11}$.
$x equiv 2 pmod{11}$.
Since $gcd(7, 11)=1$, there is a unique solution modulo 11.

Final check of Lagrange's method description:
Lagrange used the convergents of $a/m$ to solve $axmy=b$.
When $gcd(a,m)=1$, we look at $a/m$.
$a/m = [q_1; q_2, dots, q_N]$.
The relevant property is $a q_{N1} m p_{N1} = (1)^N$ if the last quotient is $q_N$.
For $a/m = 7/11 = [0; 1, 1, 1, 3]$, $N=5$ (number of quotients including 0).
The last quotient is $q_5=3$.
Convergents of $7/11$: $frac{0}{1}, frac{1}{1}, frac{1}{2}, frac{2}{3}, frac{7}{11}$.
The last $p_k/q_k$ before the full fraction is $p_4/q_4 = 2/3$.
The property is $a q_k m p_k = (1)^{k+1}$ or $a q_k m p_k = (1)^{k}$ depending on index definition.
Let's use the property that for $alpha/eta = [q_1; dots, q_N]$, $alpha p_k eta q_k = (1)^{k+1} eta_{k+1}$.
A more direct property for inverse:
If $frac{p_k}{q_k}$ is a convergent of $frac{a}{m}$, then $a q_k m p_k$ is constant.
For $a/m = [q_1; dots, q_N]$, $a q_{N1} m p_{N1} = (1)^N imes ( ext{numerator of the remainder})$
If $gcd(a, m)=1$, then $a cdot ( ext{related term}) equiv pm 1 pmod m$.

The key point is that from the Euclidean algorithm, we can express $gcd(a,m)$ as $ax_0 + my_0$.
The sequence of quotients $q_i$ in the Euclidean algorithm for $a, m$ are the same as in the連分數 of $a/m$.
$a = q_1 m + r_1$
$m = q_2 r_1 + r_2$
...
$r_{n1} = q_{n+1} r_n$
Let $r_n = gcd(a,m)$.
We can write $r_n = a X + m Y$ for some integers $X, Y$.
The連分數 $frac{a}{m} = [q_1; q_2, dots, q_{n+1}]$.
The convergents $frac{p_k}{q_k}$ satisfy $a p_k m q_k = (1)^{k+1} r_{k+1}$. (This might need adjustment based on index start.)
Let's focus on the last one: $a p_n m q_n = (1)^{n+1} r_{n+1}$.
If we consider $a/m$, the last nonzero remainder in Euclidean algorithm for $a,m$ is $gcd(a,m)$.
Let's say $a=7, m=11$.
$11 = 1 cdot 7 + 4$
$7 = 1 cdot 4 + 3$
$4 = 1 cdot 3 + 1$
$3 = 3 cdot 1 + 0$.
$gcd(7, 11) = 1$.
$7/11 = [0; 1, 1, 1, 3]$. Quotients are $0, 1, 1, 1, 3$.
The convergents are $frac{0}{1}, frac{1}{1}, frac{1}{2}, frac{2}{3}, frac{7}{11}$.
We are interested in the relation $a X m Y = b$.
This is $(a/d)X (m/d)Y = b/d$.
Let $a' = a/d, m'=m/d$. $gcd(a', m')=1$.
We need $a'x equiv b' pmod{m'}$.
This is $a'x m'y = b'$.
From the continued fraction of $a'/m'$, say $[q_1; dots, q_N]$, the convergent $frac{p_{N1}}{q_{N1}}$ gives $a'q_{N1} m'p_{N1} = pm 1$.
For $7/11$, $a'=7, m'=11$. $7/11 = [0; 1, 1, 1, 3]$. $N=5$ (number of quotients).
The last convergent before $7/11$ is $p_4/q_4 = 2/3$.
We need to be careful with signs and indices.
Let's use the result $a'q_{N1} equiv (1)^{N1} pmod{m'}$.
For $7/11 = [0; 1, 1, 1, 3]$, $N=5$.
$q_4=3$.
$a'=7$. $7 cdot q_4 = 7 cdot 3 = 21 equiv 1 pmod{11}$.
$(1)^{N1} = (1)^{51} = (1)^4 = 1$. This does not match.

Let's use the property $a p_k m q_k = (1)^{k+1} imes ( ext{remainder in } m/a)$.
Let's use $m/a = 11/7 = [1; 1, 1, 3]$. $N=4$.
$q_1=1, q_2=1, q_3=1, q_4=3$.
Convergents of $11/7$: $1/1, 2/1, 3/2, 11/7$.
The convergent before the full fraction is $3/2$. ($p_3=3, q_3=2$).
Property for $m/a$: $m p_k a q_k = (1)^{k+1}$.
For $k=3$: $11 p_3 7 q_3 = 11 cdot 3 7 cdot 2 = 33 14 = 19$. Incorrect.

The correct property that relates the convergents of $a/m$ to the equation $ax my = gcd(a,m)$:
If $frac{p_k}{q_k}$ are convergents of $a/m = [q_1; dots, q_N]$, then $a q_{k} m p_{k} = (1)^{k+1} ext{ remainder }$.
For $a/m = 7/11 = [0; 1, 1, 1, 3]$.
Convergents $p_k/q_k$: $0/1, 1/1, 1/2, 2/3, 7/11$.
We want to solve $7x 11y = 3$.
Let's find $x_0$ for $7x_0 11y_0 = 1$.
This means we need $a/m$ such that $a q_k m p_k = pm 1$.
This happens for the last convergent $frac{p_{N1}}{q_{N1}}$ of $a/m$.
For $7/11 = [0; 1, 1, 1, 3]$, $N=5$ (number of quotients).
The last full convergent before $7/11$ is $p_4/q_4 = 2/3$.
$7 q_4 11 p_4 = 7 cdot 3 11 cdot 2 = 21 22 = 1$.
So, $7 cdot 3 equiv 1 pmod{11}$.
We need $7x equiv 1 pmod{11}$.
Multiply by $1$: $7 cdot (3) equiv 1 pmod{11}$.
So, $x_0 = 3 equiv 8 pmod{11}$. This is the inverse of $7 pmod{11}$.

Then, for $7x equiv 3 pmod{11}$,
$x equiv 3 cdot x_0 pmod{11} equiv 3 cdot 8 pmod{11} equiv 24 pmod{11} equiv 2 pmod{11}$.

Lagrange's method is essentially finding the modular inverse using the properties of continued fractions derived from the Euclidean algorithm.

这是一个相当详细的解释，希望能帮助您理解拉格朗日是如何利用连分数理论来推导一次同余方程的通解的。核心在于连分数提供了一种结构化的方式来执行欧几里得算法，并从算法的中间结果（收敛分数）中提取出求解丢番图方程和同余方程所需的乘法逆元。

由书中记法（既然高斯大神使用这种记法，那也没办法了），观察到

易证

其中连分数表示为

反复使用上式，进而有

变形

如此一来，都可以表示为连分数的乘积的倒数，所以只需要分析连分数就可以了。