整除

整除：设 $a,b\in \Z$ 且 $a\neq 0$ ，若 $\exist q\in \Z$ ，使得 $b=aq$ ，那么称 $a$ 整除 $b$ ，记作 $a\mid b$ ，并且称 $a$ 是 $b$ 的因数(约数)， $b$ 是 $a$ 的倍数。如果这样的整数 $q$ 不存在，就称 $a$ 不整除 $b$ ，记作 $a\nmid b$ 。

例如， $6\mid -24,\quad -4\mid 56,\quad 8\mid 0,\quad -4\nmid 14$

基本性质：设 $a,b,c\in\Z$

$a\mid b \iff -a\mid b \iff a\mid -b$ ；
若 $a\mid b,\ b\mid a$ ，则 $a=\pm b$ ；
若 $a\mid b,\ b\mid c$ ，则 $a\mid c$ ；
若 $a\mid b,\ a\mid c$ ，则 $\forall x,y\in\Z$ 恒有 $a\mid bx+cy$ ；
若 $m\in\Z,m\ne0$ ，则 $a\mid b \iff ma\mid mb$ ；
若 $b\ne0$ ，则 $a\mid b \implies |a|\leqslant |b|$ ；
若 $a\ne0, b=qa+c$ ，那么 $a\mid b \iff a\mid c$ ；

带余除法

带余除法：设 $a,b\in \Z$ 且 $b\neq 0$ ，则存在唯一的一对 $q,r\in\Z$ ，使得

$a=bq+r,\quad 0\leqslant r<|b|$

从数轴上可以直观的看到

现在证明 $q,r$ 的唯一性。我们假定 $a=bq_1+r_1=bq_2+r_2$ ，即 $r_1-r_2=b(q_2-q_1)$ 。于是 $b\mid r_1-r_2$ ，而 $-|b|<r_1-r_2<|b|$ ，因此 $r_1-r_2=0$ 即 $r_1=r_2$ ，从而 $q_1=q_2$ 。所以 $q,r$ 是唯一的。

我们把带余除法中唯一的 $q,r$ 分别叫做 $a$ 除以 $b$ 的商(quotien)和余数(remainder)。显然， $a$ 能被 $b$ 整除当且仅当余数 $r=0$ 。

素数

定义：除了1和它自身外，不能被其它正整数整除的正整数叫做素数，不是素数又不是1的正整数叫做合数。

由定义知，3，13，31是素数，12，14，81是合数，1既不是素数也不是合数。显然，2是唯一的偶素数，也是最⼩的素数。

容易发现，除了1以外，每个正整数的最⼩正因数 $p$ 是⼀个素数。任何⼤于1的整数，总可分解为⼀些素数的乘积。通常，把⼀个正整数的素数因数叫做它的素因数。

素数有无限多个：假设素数有有限个 $\mathbb P=\{p_1,p_2,\cdots,p_k\}$ ，记这 $k$ 个素数的乘积为 $N=p_1p_2\cdots p_k$ ，由此可知， $\forall p_i\in \mathbb P$ 有 $p_i\mid N$ ，但是 $p_i\nmid N+1$ ，所以 $N+1$ 一定能被某个素数整除，这就产生了矛盾。因此，素数有无限多个。

素数判别法：如果大于1的整数 $a$ 不能被所有不超过 $\sqrt{a}$ 的素数整除，那么 $a$ 一定是素数。

这个判别法实际上给出了⼀种寻找素数的有效⽅法，称为Eratosthenes筛法。

例如：找出1-100间的所有素数。

解：只需把1-100间的合数去掉即可。对于1-100间的每个合数 $a$ ，它一定能被某个不超过 $\sqrt{a}$ 的素数整除，从而能被不超过 $\sqrt{100}=10$ 的素数整除。我们知道，不超过10的素数为 2，3，5，7。接下来，我们去掉2，3，5，7和他们的倍数，剩下的就是不超过100的全部素数。

最大公约数

定义：给定两个整数 $a,b$ ，必有公共的因数，叫做它们的公约数。当 $a,b\neq0$ 时，在有限个公约数中最⼤的⼀个叫做 $a,b$ 的最⼤公约数(Greatest Common Divisor)，记作 $\gcd(a,b)$ 。如果 $\gcd(a,b)=1$ ，那么称 $a,b$ 是互素(relatively prime)的。

例如，-8和14的公约数为1，-1，2，-2，所以 $\gcd(-8,14)=2$ 。

类似的，我们可以定义三个及以上非零整数的最⼤公约数 $\gcd(a_1,a_2,\cdots,a_n)$ 和互素。

定理：设余数 $r=a\bmod b$ ，那么 $\gcd(a,b)=\gcd(b,r)$ 。

证明：设带余除法 $a=qb+r$ 。若 $d$ 是 $a,b$ 的公约数，即 $d\mid a,\ d\mid b$ ，则 $d\mid r=a-qb$ ，从而 $d$ 为 $b,r$ 的公约数。同理可证 $b,r$ 的公约数也是 $a,b$ 的公约数。因此得证。

按照这个思路，我们来求 $\gcd(1840,667)$ 。因为

$1840=667\times 2+506,\\ 667=506\times1+161,\\ 506=161\times3+23$

于是

$\gcd(1840,667)=\gcd(667,506)=\gcd(506,161)=\gcd(161,23)=23$

这种求最大公约数的⽅法，叫做辗转相除法，也称 Euclid 算法，它是⼀种古⽼⽽有效的算法。下面我们给出辗转相除法的一般形式

Euclidean_Algorithm

对于三个整数的最⼤公约数，可以转化为求两次两个整数的最⼤公约数

$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$

定理：设 $a,b\neq 0$ ，则 $\exist m,n\in\Z$ 使得 $\gcd(a,b)=am+bn$ 。

证明：不妨设 $b>0$ ，对 $a,b$ 用带余除法

$a=bq_1+r_1\quad (0\leqslant r_1<b)$

因为 $\gcd(a,b)=\gcd(b,r_1)$ ，若 $r_1=0$ ，则 $\gcd(a,b)=\gcd(b,r_1)=b$ 。此时有 $m=0$ ， $n=1$ 。

若 $r_1\neq0$ ，对 $b,r_1$ 用带余除法

$b=r_1q_2+r_2\quad(0\leqslant r_2<r_1)$

且 $\gcd(b,r_1)=\gcd(r_1,r_2)$ 。若 $r_2=0$ ，则 $\gcd(a,b)=\gcd(r_1,r_2)=a-bq_1$ 。此时有 $m=1$ ， $n=-q_1$ 。

若 $r_2\neq0$ ，对 $r_1,r_2$ 用带余除法，依次类推，总能找到符合条件的 $m,n$ 。这个性质对多于整数情形仍然成立。

推论1：若 $a\mid bc$ 且 $\gcd(a,b)=1$ ，则 $a\mid c$ 。

证明：因为 $\gcd(a,b)=1$ ，故 $\exists m,n\in\Z$ 使得 $am+bn=1$ 。于是 $(ac)m+(bc)n=c$ ，又因为 $a\mid ac,\ a\mid bc$ ，所以 $a\mid (ac)m+(bc)n=c$ 。

推论2：若素数 $p\mid ab$ ，则 $p\mid a$ 或 $p\mid b$ 。

证明：因为 $p$ 是素数，其正因数只有 $1,p$ ，所以 $\gcd(p,a)=1$ 或 $\gcd(p,a)=p$ 。若 $\gcd(p,a)=1$ ，由推论1得 $p\mid b$ 。若 $\gcd(p,a)=p$ 则 $p\mid a$ 。

最小公倍数

定义：对于两个⾮零整数 $a,b$ ，⼀定存在⼀个整数，它同时为 $a,b$ 的倍数，这个倍数叫做 $a,b$ 的公倍数。我们把 $a,b$ 的最⼩的正公倍数叫做最⼩公倍数(Least Common Multiple)，记作 $\text{lcm}(a,b)$ 。

类似的，我们可以定义三个及以上非零整数的最小公倍数 $\text{lcm}(a_1,a_2,\cdots,a_n)$ 。

定理：任意 $a,b$ 的最小公倍数 $m=\text{lcm}(a,b)$ 一定整除 $a,b$ 的公倍数。

证明：设 $n$ 是任意一个公倍数，对 $m,n$ 使用带余除法 $n=mq+r$ ，其中 $0\leqslant r< m$ 。假设 $m\nmid n$ ，则 $r> 0$ 。由 $a\mid m,\ b\mid m,\ a\mid n,\ b\mid n$ 得 $a\mid r,\ b\mid r$ ，即 $r$ 也是 $a,b$ 的公倍数。但 $r< m$ ，这与 $m=\text{lcm}(a,b)$ 矛盾。因此， $m\mid n$ 。

求得最小公倍数

$\gcd(a,b)\cdot \text{lcm}(a,b)=|ab|$

三个整数的最⼤公约数，总可以转化为求两次两个整数的最⼤公约数

$\text{lcm}(a,b,c)=\text{lcm}(\text{lcm}(a,b),c)$

算术基本定理

算术基本定理：任何⼤于1的整数 $n$ 总可以分解成素因数乘积的形式

$n=p_1p_2\cdots p_r$

其中 $p_i$ 是素数。如果不计分解式中素因数的次序，则这种分解式是惟⼀的，叫做素因数分解式。

将上述表示中相同的素数合并，可得

$n={p_1}^{m_1}{p_2}^{m_2}\cdots{p_s}^{m_r}$

称为标准素因数分解式。

证明：下面只证明素因式的唯一性。假定 $n$ 有两个素因式

$n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$

由于 $p_1$ 是素数，且 $p_1\mid q_1q_2\cdots q_s$ ，故 $p_1$ 整除 $q_1,q_2,\cdots,q_s$ 中的某个 $q_i$ ，当不计素因数的次序时，总可假定 $p_1\mid q_1$ ，而 $p_1,q_1$ 均为素数，故 $p_1=q_1$ ，于是 $p_2\cdots p_r=q_2\cdots q_s$ 。同理可得 $p_2=q_2$ ，依次类推，最后得 $r=s$ 且 $p_i=q_i$ 。所以， $n$ 的素因数分解式是唯一的。

下面我们来看素因数分解式的一个⾮常重要的应⽤｡

示例：求解 $\gcd(720,152)$ 和 $\text{lcm}(720,152)$ 。

解：容易知道

$720=2^4\times 3^2\times 5,\quad 152=2^3\times 19$

由此不难得到

$\begin{aligned} \gcd(720,152)&=2^3=8, \\ \text{lcm}(720,152)&=2^4\times 3^2\times 5\times 19=13680 \end{aligned}$

⼀般地，对于整数 $a,b$ ，找出它们所有的互异素因数，然后，将 $a,b$ 表示成这些素因数的幂的乘积，如果其中⼀个素因数在 $a$ 或 $b$ 中不出现，就将这个素因数的幂指数写作0，那么 $\gcd(a,b)$ 可以表示成这些素因数的幂的乘积，每个素因数的幂指数为其在 $a$ 与 $b$ 中的幂指数的最⼩者。⽽ $\text{lcm}(a,b)$ 也可以表示成这些素因数幂的乘积，每个素因数的幂指数为其在 $a$ 与 $b$ 中的幂指数的最大者｡

同余与同余方程

同余

定义：设 $n\in \Z^+,a,b\in\Z$ ，如果 $a,b$ 被 $n$ 除后余数相同，那么称 $a$ 和 $b$ 模 $n$ 同余，记作

$a\equiv b\pmod n$

例如 $12\equiv -6\pmod 9$

设 $a=nq_1+r_1,\ b=nq_2+r_2$ 。若 $a\equiv b\pmod n$ 则 $r_1=r_2$ ，并且 $a-b=n(q_1-q_2)$ ，于是 $n\mid(a-b)$ 。反过来，若 $n\mid a-b=n(q_1-q_2)+r_1-r_2$ ，则 $n\mid r_1-r_2$ ，而 $-n< r_1-r_2< n$ ，故 $r_1-r_2=0$ ，因此 $a\equiv b\pmod n$ 。于是我们有

$a\equiv b\pmod n \iff n\mid a-b$

由上式可得同余是等价关系：

自反性： $a\equiv a\pmod{m}$
对称性：若 $a\equiv b\pmod{m}$ ，则 $b\equiv a\pmod{m}$
传递性：若 $a\equiv b\pmod{m},\ b\equiv c\pmod{m}$ ，则 $a\equiv c\pmod{m}$

性质：设 $n\in \Z^+$ ，若 $a\equiv b\pmod n$ 且 $c\equiv d\pmod n$ 则

$a+c\equiv b+d\pmod n$
$ac\equiv bd\pmod n$
$ka\equiv kb\pmod n,\quad k\in \Z$
$a^m\equiv b^m\pmod n,\quad m\in \Z^+$

证明：(1) 因为 $a\equiv b\pmod n$ 且 $c\equiv d\pmod n$ ，所以 $n\mid a-b,\ n\mid c-d$ ，因此 $n\mid a-b+c-d$ ，即 $n\mid (a+c)-(b-d)$ ，所以 $a+c\equiv b+d\pmod n$ 。

利⽤同余的这些性质，我们可以简化数论中的许多问题｡

例如，如果今天为星期日，过 $n$ 天后是星期几？这个问题并不难回答，我们只需对 $n$ 和7用带余除法，由余数即可确定。但是，有时直接应⽤带余除法求余数是困难的，特别是当被除数较⼤时，如下例：

示例：今天为星期⽇，过 $2004^{2004}$ 天后是星期几？

分析： $2004^{2004}$ 这个数很⼤，我们很难直接判断7除 $2004^{2004}$ 的余数是几。现在，我们想办法把 $2004^{2004}$ 变⼩。⼀个⾃然的考虑是7除底数2004的余数是⼏，利用这个余数替换底数2004，然后降次，反复进⾏这个过程，直⾄去掉指数｡

解：因为 $2004=7\times 286+2$ ，所以 $2004\equiv 2\pmod 7$ 。由同余的性质有

$2004^{2004}\equiv 2^{2004}\pmod 7$

而 $2^{2004}=8^{668}$ 。又 $8\equiv 1\pmod 7$ ，所以 $8^{668}\equiv 1^{2004}\pmod 7$ 。因此

$2004^{2004}\equiv 1\pmod 7$

即 7 除 $2004^{2004}$ 的余数为1，所以结果是星期一。

定理：若 $ab\equiv ac\pmod n$ 且 $\gcd(a,n)=1$ 则 $b\equiv c\pmod n$

证明：因为 $\gcd(a,n)=1$ ，所以 $\exists k,l\in\Z$ 使得 $ak+nl=1$ ，因此 $n\mid nl=1-ak$ ，即 $ak\equiv1\pmod n$ 。又因为 $ab\equiv ac\pmod n$ ，所以 $kab\equiv kac\pmod n$ ，因此 $b\equiv c\pmod n$ 。

上述定理可以看作是同余意义下的消去律，前提是 $a$ 与 $n$ 必须互素。

剩余类

对正整数 $n$ ，模 $n$ 同余给出了整数之间的⼀种关系，这种关系我们称之为同余关系。利⽤同余关系，我们可以对整数集进⾏分类。例如，模2同余可将整数集分为奇数和偶数。

我们把所有与整数 $r$ 模 $n$ 同余的整数构成的集合叫做模 $n$ 的一个剩余类，记作 $r\bmod n$ 。

由剩余类的定义可知：

$r\bmod n=\{r+kn: k\in\mathbb Z\}$
$r\bmod n=s\bmod n \iff r\equiv s\pmod{n}$

我们把模 $n$ 的同余类全体构成的集合记为

$\mathbb{Z}_n=\{r\bmod m:0\leqslant r< m\}$

费马小定理：设 $p$ 是素数， $a$ 是任意整数，若 $\gcd(p,a)=1$ 则

$a^{p-1}\equiv 1\pmod p$

证明：由 $\gcd(p,a)=1$ 可知 $p$ 不是 $a$ 的素因数，又因为 $p$ 不是 $1,2,3,\dots,p-1$ 的素因数，所以 $a,2a,3a,\dots,(p-1)a$ 均不能被 $p$ 整除。又因为 $a,2a,3a,\dots,(p-1)a$ 模 $p$ 两两不同余，所以它们分别属于模 $p$ 的除 $0$ 以外的 $p-1$ 个不同的剩余类中。由同余的性质可知

$\begin{aligned} &a\cdot2a\cdot3a\cdots(m-1)a \\ \equiv &1\cdot2\cdot3\cdots(m-1)\pmod m \end{aligned}$

因此

$a^{m-1}(m-1)!\equiv(m-1)!\pmod m$

又由于 $(m-1)!$ 不含素因数 $m$ ，所以

$\gcd((m-1)!,m)=1$

由同余的消去律可知

$a^{m-1}\equiv1\pmod m$

欧拉定理：设 $m\in\Z^+,a\in\Z$ ，若 $\gcd(a,m)=1$ 则

$a^{\varphi(m)}\equiv 1\pmod m$

其中 $\varphi(m)$ 称为欧拉函数，表示 $1,2,\cdots,m$ 中与 $m$ 互素的正整数的个数。

证明：记 $\varphi(m)=r$ ，并用 $a_1,a_2,\dots,a_r$ 表示 $1,2,3,\dots,m$ 中所有与 $m$ 互素的整数。因为 $\gcd(a,m)=1$ ，所以 $aa_1,aa_2,\dots,aa_r$ 与 $m$ 均是互素的。从而它们分属于模 $m$ 的 $r$ 个剩余类 $a_1\bmod m,\ a_2\bmod m,\ \dots,\ a_r\bmod m$ 。由同余的性质可得：

$a^ra_1a_2\cdots a_r\equiv a_1a_2\cdots a_r\pmod m$

又因为 $a_1,a_2,\dots,a_r$ 均与 $m$ 互素，由同余的消去律可得

$a^{\varphi(m)}\equiv1\pmod m$

在欧拉定理中，如果 $m$ 为素数，此时 $\varphi(m)=m-1$ ，那么我们得到了费马小定理。欧拉定理和费马小定理有许多重要的应用，利用它们可以简化许多计算。

同余方程

通常我们把含有未知数的同余式叫做同余方程，一次同余方程的一般形式为

$ax\equiv b\pmod n$

其中 $n\in\Z^+,a,b\in\Z$ 且 $a\neq0$ 。

若存在 $c\in\Z$ 使得同余式 $ac\equiv b\pmod n$ 成立，则把 $x\equiv c\pmod n$ 叫做一次同余方程的解。例如， $x\equiv 3\pmod 6$ 是 $5x\equiv 3\pmod 6$ 的解。

如果 $x\equiv d\pmod n$ 也是同余方程的解，且 $c\equiv d\pmod n$ ，那么我们将这两个解视作一样的。实际上，在这种意义下，一次同余方程的解可理解为模 $n$ 的一个剩余类，是一个集合，而不是一个整数。因此，要判断一个模 $n$ 的剩余类是不是同余方程的解，只需选取剩余类中的一个代表元，看它是否使同余式成立即可。

由上面的分析可知，解剩余类环中的方程总可以转化为解某个同余方程。与我们熟悉的解一元一次方程、一元二次方程等过程类似。接下来，我们来讨论一次同余方程解的情况：

情形一：当 $\gcd(a,n)=1$ 。我们知道，当 $\gcd(a,n)=1$ 时，存在整数 $k,l$ ，使得 $ak+nl=1$ ，于是 $n\mid nl=1-ak$ ，即 $ak\equiv1\pmod n$ 。因此

$ax\equiv b\pmod n\iff ax\equiv(ak)b\pmod n\iff x\equiv kb\pmod n$

因此，同余方程仅有一个解 $x\equiv kb\pmod n$ 。

情形二：再讨论 $\gcd(a,n)=d>1$ 的情形。不妨设 $x\equiv c\pmod n$ 为同余方程的一个解，则 $ac\equiv b\pmod n$ ，从而 $n\mid ac-b$ 。由于 $d\mid a$ ， $d\mid n$ ，故 $d\mid ac$ ， $d\mid ac-b$ ，从而

$d\mid ac-(ac-b)=b$

这表明，同余方程有解时，必有 $d\mid b$ 。那么，当 $d\mid b$ 时，同余方程是否一定有解呢？

记 $a=a'd$ ， $n=n'd$ ， $b=b'd$ ，则 $\gcd(a',n')=1$ 。注意到

$ax\equiv b\pmod n\iff n\mid ax-b\iff n'd\mid(a'x-b')d\iff n'\mid a'x-b'$

于是同余方程可化简为

$a'x\equiv b'\pmod {n'}$

由于 $\gcd(a',n')=1$ ，由情形一的讨论知，简化后的同余方程有惟一解 $x\equiv k'b'\pmod {n'}$ ，此时 $x=k'b'+n'l$ ，其中 $l$ 为任意整数。

对 $l,d$ 用带余除法： $l=dq+r$ ，其中 $0\leqslant r\leqslant d-1$ 。则

$x=k'b'+n'(dq+r)=k'b'+nq+n'r$

于是

$x\equiv k'b'+n'r\pmod n$

其中 $r=0,1,\cdots, d-1$ 。容易检验，它们都是同余方程的解。

综上所述，我们得到下面的结论。

定理：一次同余方程 $ax\equiv b\pmod n$ 有解，当且仅当 $\gcd(a,n)\mid b$ 。此时，解的个数 $d=\gcd(a,n)$ 。

示例：解一次同余方程 $9x\equiv 6\pmod{15}$ 。

解：注意到 $\gcd(9,15)=3$ ，且 $3\mid 6$ ，故同余方程有3个解。原方程可化简为 $3x\equiv 2\pmod{5}$ 。由于 $3\times 2\equiv 1\pmod 5$ ，故 $x\equiv 2\times 2=4\pmod 5$ 。所以，原同余方程的三个解分别为

$x\equiv 4+5\times 0=4\pmod{15} \\ x\equiv 4+5\times 1=9\pmod{15} \\ x\equiv 4+5\times 2=14\pmod{15}$

中国剩余定理

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？

即解同余方程组

$\begin{cases} x\equiv 2\pmod 3 \\ x\equiv 3\pmod 5 \\ x\equiv 2\pmod 7 \end{cases}$

容易检验，若存在正整数 $k$ 使得每个同余式都成立时，所有模 $3\times5\times 7=105$ 同余 $k$ 的整数，也使得上述方程组成立。反过来，若还有整数 $l$ 使得上述方程组成立，那么

$l\equiv k\pmod 3,\ l\equiv k\pmod 5,\ l\equiv k\pmod 7$

于是 $3\mid l-k,\ 5\mid l-k,\ 7\mid l-k$ ，从而 $3\times5\times 7\mid l-k$ ，即 $l\equiv k\pmod{105}$ 。

通常，我们把 $x\equiv k\pmod{105}$ 叫做同余方程组的解，在这个意义下，同余方程组只有一个解。

「物不知数」问题最早见于《孙子算经》中，并有该问题的具体解法。中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组。

中国剩余定理：设 $m_1,m_2,\cdots,m_r$ 是两两互素的正整数，解同余方程组

$x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \vdots \\ x\equiv a_r\pmod {m_r}\\$

计算所有模数的积 $n$ ；
对于第 $i$ 个方程：
- 计算 $m_i=n/n_i$
- 计算 $m_i$ 在模 $n_i$ 下的逆元 $m_i^{-1}$
- 计算 $c_i=m_im_I^{-1}$
方程组在模 $n$ 下的唯一解为

$x=\sum_{i=1}^r a_ic_i\pmod n$

指数与原根

不定方程

公元200多年，古希腊数学家丢番图Diophantus曾讨论了某些不定⽅程，因⽽也有⼈把不定⽅程叫做Diophantus⽅程。

一次不定方程（linear Diophantine equation）是形如

$a_1x_1+a_2x_2+\cdots+a_nx_n=b$

的不定方程，其中 $a_i$ 都是整数．本章的目标是寻找它的全体整数解。

二元一次不定方程

首先考虑二元一次不定方程：

$ax+by=c\tag{1}$

其中 $a,b,c\in\Z$ ，且 $a,b\neq0$ 。

显然，这类不定方程不一定有整数解。例如， $2x+4y=1$ 没有整数解，因为对任意 $x,y\in\Z$ ， $2x+4y$ 恒为偶数，它不可能等于1。

我们感兴趣的是，不定方程 (1) 何时有整数解？有解时是否有无穷多个整数解？这些整数解是否有统一的表达式？当然，还有一个问题就是如何求出所有的整数解。

首先看不定方程 (1) 有解时，整数 $a,b,c$ 具有什么特征。观察不定方程 $ax+by=c$ 的形式，自然联想到它与整除、同余之间的联系。假定不定方程 (1) 有整数解 $x=x_0,\ y=y_0$ 。因为 $\gcd(a,b)\mid a,\ \gcd(a,b)\mid b$ ，所以 $\gcd(a,b)\mid ax_0+by_0=c$ 。也就是说，不定方程 (1) 有解时，整数 $a,b,c$ 必须满足：

$\gcd(a,b)\mid c$

整数 $a,b,c$ 的这种特征能否保证不定方程 (1) 有整数解呢？

下面我们来检验一下。设 $d=\gcd(a,b)\mid c$ ，令 $a=a'd,\ b=b'd,\ c=c'd$ ，则不定方程 (1) 简化为

$a'x+b'y=c'\tag{2}$

其中 $\gcd(a',b')=1$ 。由最大公约数的性质，存在一对整数 $u,v$ ，使得 $a'u+b'v=1$ 。于是 $a'(uc')+b'(vc')=c'$ ，从而有 $a(c'u)+b(c'v)=c$ 。那么 $x=c'u,\ y=c'v$ 就是不定方程 (1) 的整数解。

综合上述，我们可以得到不定方程 (1) 有整数解的一个判别准则。

定理：不定方程 $ax+by=c$ 有整数解，当且仅当 $\gcd(a,b)\mid c$ 。

从前面的分析可以看出，当不定方程 (1) 有整数解时，它可以化简为 $x,y$ 的系数互素的不定方程 (2) 。基于这个事实，对有整数解的不定方程 (1) ，我们不妨假定 $\gcd(a,b)=1$ ，设 $x=x_0,\ y=y_0$ 为不定方程 (1) 的整数解。容易检验，对任意整数 $t$

$\begin{cases}x=x_0+bt \\y=y_0-at\end{cases}\tag{3}$

均为不定方程 (1) 的整数解。这意味着不定方程 (1) 有整数解时，必有无穷多个整数解。

不定方程的每个解是否都可以用表达式 (3) 表示呢？

任取不定方程 (1) 的整数解 $x=x',\ y=y'$ ，则有 $ax'+by'=c$ 。因为 $ax_0+by_0=c$ ，所以

$a(x'-x_0)=b(y_0-y')$

从而 $b\mid a(x'-x_0)$ 。因为 $\gcd(a,b)=1$ ，所以 $b\mid x'-x_0$ 。于是存在整数 $t$ ，使得 $x'-x_0=bt$ ，即 $x'=x_0+bt$ ，代入上式得 $y'=y_0-at$ 。这表明，不定方程 (1) 的每个解都可以表示成 (3) 式的形式。

通常，我们把 (3) 式叫做不定方程 (1) 的整数通解，而把 $x=x_0,\ y=y_0$ 叫做不定方程 (1) 的一个特解。综上所述，我们得到下面的结论。

定理：设 $\gcd(a,b)=1$ ，则不定方程 $ax+by=c$ 的整数通解为

$\begin{cases}x=x_0+bt \\y=y_0-at\end{cases}$

其中 $t$ 为任意整数， $x=x_0,\ y=y_0$ 为不定方程 $ax+by=c$ 的一个特解。

从上述结论可以看出，要描述二元一次不定方程的所有整数解，只需知道它的一个特解即可。对某些比较简单的不定方程，如当 $a,b$ 的绝对值较小时，我们可以直接通过观察或试验得到它的一个特解。

示例：求不定方程 $5x+3y=10$ 的整数通解。

解：因为 $\gcd(5,3)=1$ ，而 $1\mid10$ ，所以原不定方程有整数解。容易观察， $5x+3y=1$ 有一个特解 $x=-1,\ y=2$ 。因此， $x=-10,\ y=20$ 就是原不定方程的一个特解。由上述结论，原不定方程的整数通解为

$\begin{cases}x=-10+3t \\y=20-5t \end{cases}$

其中 $t$ 为任意整数。

对某些较复杂的二元一次不定方程 $ax+by=c$ ，其中 $\gcd(a,b)=1$ ，我们很难直接观察出它的一个特解。这时候，我们可以通过辗转相除法求它的一个特解。其过程如下：

注意到，当 $b=1$ 时，我们容易观察出不定方程 $ax+by=c$ 的一个特解 $x_0=1,\ y_0=c-a$ 。

下面假定 $b>1$ ，并且对 $a,b$ 用辗转相除法得

$\begin{align*} a&=bq_1+r_1,\\ b&=r_1q_2+r_2,\\ r_2&=r_3q_3+r_4,\\ &\cdots\cdots\\ r_{n-2}&=r_{n-1}q_n+r_n\ (r_n=1)\end{align*}$

我们规定， $k_0=0,\ k_1=1$ ，然后由递推关系式 $k_i=k_{i-2}-q_ik_{i-1}\ (i=2,\cdots,n)$ 依次计算出 $k_2,\cdots,k_n$ 。根据大衍求一术的算法原理知， $r_i\equiv ak_i\pmod b$ ，于是 $b\mid r_i-ak_i$ 。特别地，当 $i=n$ 时， $b\mid1-ak_n$ 。我们选取

$\begin{cases} x_0=k_nc \\ y_0=\dfrac{c(1-ak_n)}{b} \end{cases}$

容易检验， $x=x_0,\ y=y_0$ 就是不定方程 $ax+by=c$ 的一个特解。根据前面的过程，我们可以写出下面算法流程图：

示例：求不定方程 $13x+74y=2$ 的一个特解。

解：因为 $\gcd(13,74)=1$ ，我们对 $13,74$ 用辗转相除法，得

$\begin{align*} 13&=74\times0+13,\\ 74&=13\times5+9,\\ 13&=9\times1+4,\\ 9&=4\times2+1, \end{align*}$

因此 $q_2=5,\ q_3=1,\ q_4=2$ 。再由递推关系式依次计算得

$\begin{align*} k_2&=(-5)\times1+0=-5,\\ k_3&=(-1)\times(-5)+1=6,\\ k_4&=(-5)+(-2)\times6=-17. \end{align*}$

因此

$\begin{cases} x=(-17)\times2=-34,\\ y=\dfrac{2(1-13\times(-17))}{74}=6 \end{cases}$

是不定方程 $13x+74y=2$ 的一个特解。

多元一次不定方程

本节以三元一次不定方程为例说明多元一次不定方程的解法。三元一次不定方程的一般形式为

$ax+by+cz=d\tag{1}$

其中 $a,b,c\in\Z^+,\ d\in\Z$ 。

仿照讨论二元一次不定方程的方式，首先看不定方程 (1) 有整数解时， $a,b,c,d$ 有什么特征。设 $x=x_0,\ y=y_0,\ z=z_0$ 是不定方程 (1) 的整数解。因为 $\gcd(a,b,c)\mid a,\ \gcd(a,b,c)\mid b,\ \gcd(a,b,c)\mid c$ ，所以 $\gcd(a,b,c)\mid ax_0+by_0+cz_0=d$ 。

当 $\gcd(a,b,c)\mid d$ 时，不定方程 (1) 是否一定有整数解呢？

我们记 $\gcd(a,b)=m$ ，由于 $\gcd(m,c)=\gcd(a,b,c)\mid d$ ，故二元一次不定方程

$mt+cz=d\tag{2}$

有整数解，不妨设 $t=t_0,\ z=z_0$ 。考虑二元一次不定方程

$ax+by=mt_0\tag{3}$

由于 $\gcd(a,b)=m\mid mt_0$ ，所以不定方程 (3) 有整数解 $x=x_0,\ y=y_0$ 。注意到 $ax_0+by_0+cz_0=mt_0+cz_0=d$ ，所以 $x=x_0,\ y=y_0,\ z=z_0$ 是不定方程 (1) 的一组整数解。

综上所述，我们得到不定方程 (1) 有整数解的一个判断准则。

定理：三元一次不定方程 $ax+by+cz=d$ 有整数解的充要条件为 $\gcd(a,b,c)\mid d$ 。

从前面的分析可以看出，当 $\gcd(a,b,c)\mid d$ 时，要求不定方程 (1) 的全部整数解，我们可以先求不定方程 (2) 的整数通解，得到 $t$ 和 $z$ 的表达式。然后用 $t$ 的表达式代替不定方程 (3) 中的 $t_0$ ，求出它的整数通解，得到 $x$ 和 $y$ 的表达式。最后，联合 $x,y$ 和 $z$ 的表达式就给出了不定方程 (1) 的全部整数解。