NT5 Bézout’s Identity裴蜀定理[C Done]

Given integers \(a,b\), let \(d=\gcd(a,b)\) (the greatest common divisor of a and b). There exist integers \(x,y\) such that

\(\boldsymbol{ax+by=d}\)

Key Corollaries

1. If \(a,b\) are coprime (\(\gcd(a,b)=1\)), there exist integers \(x,y\) satisfying \(ax+by=1\).
2. The linear Diophantine equation \(ax+by=k\) has integer solutions if and only if \(\gcd(a,b)\) divides k.

定理原文

给定整数 \(a,b\)，设它们的最大公约数 \((a,b)=d\)，则存在整数 \(x,y\)，使得

\(\boldsymbol{ax+by=d}\)

核心推论

1. 若 \(a,b\) 互质（\(\gcd(a,b)=1\)），则存在整数 \(x,y\) 满足 \(ax+by=1\)；
2. 不定方程 \(ax+by=k\) 存在整数解的充要条件是：\(\boldsymbol{\gcd(a,b) \mid k}\)（\(a,b\) 的最大公约数整除 k）。

---

Given integers \(a,b,c,d\) such that \(ad-bc=1\), prove that \(\boldsymbol{\dfrac{a+b}{c+d}}\) is a reduced fraction (i.e., its numerator and denominator are coprime).

已知整数 \(a,b,c,d\) 满足 \(ad-bc=1\)，求证：\(\boldsymbol{\dfrac{a+b}{c+d}}\) 是既约分数。

证明 Proof

既约分数等价于分子、分母的最大公约数为 1，即证 \(\boldsymbol{\gcd(a+b,\ c+d)=1}\)。

设 \(d_0=\gcd(a+b,\ c+d)\)，则：

\(d_0\mid (a+b),\quad d_0\mid (c+d)\)

\(d_0\) 整除两数的任意整数线性组合，构造： \(\begin{align*} d_0&\mid a(c+d)-c(a+b) \\ &=ac+ad-ac-bc \\ &=ad-bc=1 \end{align*}\)

因此 \(d_0\mid 1\)，即 \(d_0=1\)。

故 \(\boldsymbol{\dfrac{a+b}{c+d}}\) 是既约分数。

---

Prove that for any positive integer n, the fraction \(\boldsymbol{\dfrac{21n+4}{14n+3}}\) is a reduced fraction.

对任意正整数 n，分数 \(\boldsymbol{\dfrac{21n+4}{14n+3}}\) 是既约分数。

证明 Proof

即证 \(\boldsymbol{\gcd(21n+4,\ 14n+3)=1}\)。

设 \(d=\gcd(21n+4,\ 14n+3)\)，由最大公约数性质 \(\gcd(x,y)=\gcd(x-y,\ y)\)： \(\begin{align*} d&\mid (21n+4)-(14n+3)=7n+1 \\ d&\mid (14n+3)-2(7n+1)=1 \end{align*}\)

因此 \(d\mid 1\)，即 \(d=1\)。

故对任意正整数 n，\(\boldsymbol{\dfrac{21n+4}{14n+3}}\) 是既约分数。

---

Find the positive integer solutions \((x,y)\) of the linear Diophantine equation \(\boldsymbol{6x+15y=40}\).

求关于 \(x,y\) 的方程 \(\boldsymbol{6x+15y=40}\) 的正整数解。

解答 Proof（裴蜀定理应用）

1. 求系数的最大公约数\(\gcd(6,15)=3\)
2. 裴蜀定理判定不定方程 \(ax+by=c\) 存在整数解的充要条件是：\(\boldsymbol{\gcd(a,b)\mid c}\)（最大公约数整除常数项）。本题中 \(3\nmid40\)（3 不能整除 40），因此方程 \(6x+15y=40\)不存在整数解，自然也没有正整数解。

结论：该方程无正整数解。

---

Find all integer solutions of the linear Diophantine equation \(\boldsymbol{3x-5y=7}\).

求关于 \(x,y\) 的方程 \(\boldsymbol{3x-5y=7}\) 的整数解。

要记住不定方程的通解公式

解答

步骤 1：用裴蜀定理判断解的存在性

系数最大公约数 \(\gcd(3,5)=1\)，\(1\mid7\)，因此方程存在无穷多组整数解。

步骤 2：求一组特解

试算得：当 \(x=4\) 时，

\(3\times4-5y=7 \implies 12-5y=7 \implies y=1\)

即一组特解为 \(\boldsymbol{(x_0,\ y_0)=(4,\ 1)}\)。

步骤 3：写出通解公式

对于不定方程 \(ax+by=c\)，通解形式为

\(\begin{cases} x=x_0+\dfrac{b}{d}\,t\\ y=y_0+\dfrac{a}{d}\,t \end{cases}\quad(t\in\mathbb{Z})\)

其中 \(d=\gcd(a,b)\)

本题 \(a=3,\ b=-5,\ d=1\)，代入得： \(\boldsymbol{\begin{cases} x=4+5t\\ y=1+3t \end{cases}\quad(t\in\mathbb{Z})}\)

验证

将通解代入原方程： \(3(4+5t)-5(1+3t)=12+15t-5-15t=7\)

等式成立，通解正确。

---

Find all integer solutions of the linear Diophantine equation \(\boldsymbol{73x+28y=1}\).

求关于 \(x,y\) 的方程 \(\boldsymbol{73x+28y=1}\) 的整数解。

解答（扩展欧几里得算法，裴蜀定理应用）

步骤 1：验证解的存在性

辗转相除法求最大公约数： \(\begin{align*} 73&=2\times28+17\\ 28&=1\times17+11\\ 17&=1\times11+6\\ 11&=1\times6+5\\ 6&=1\times5+1\\ 5&=5\times1+0 \end{align*}\)

得 \(\gcd(73,28)=1\)，\(1\mid1\)，因此方程存在无穷多组整数解。

步骤 2：回代求一组特解

从最后一个非零余数开始，反向表示 1： \(\begin{align*} 1&=6-1\times5\\ &=6-1\times(11-1\times6)=2\times6-1\times11\\ &=2\times(17-1\times11)-1\times11=2\times17-3\times11\\ &=2\times17-3\times(28-1\times17)=5\times17-3\times28\\ &=5\times(73-2\times28)-3\times28=\boldsymbol{5\times73-13\times28} \end{align*}\)

对比 \(73x+28y=1\)，得一组特解：

\(\boldsymbol{x_0=5,\quad y_0=-13}\)

步骤 3：写出通解公式

对于方程 \(ax+by=c\)，通解形式为 \(\begin{cases} x=x_0+\dfrac{b}{d}\,t\\ y=y_0-\dfrac{a}{d}\,t \end{cases}\quad(t\in\mathbb{Z})\)

其中 \(d=\gcd(a,b)=1\)，代入得全部整数解： \(\boldsymbol{\begin{cases} x=5+28t\\ y=-13-73t \end{cases}\quad(t\in\mathbb{Z})}\)

验证

\(73(5+28t)+28(-13-73t)=365+2044t-364-2044t=1\)

等式成立，通解正确。

---