数论：不定方程

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

不定方程是数论的核心研究对象之一，指“未知数个数多于方程个数，且未知数受整数（或正整数）限制”的方程，典型代表如二元一次不定方程、勾股数方程，而费马问题则是不定方程领域的经典猜想。不定方程的核心是“整数解的存在性与表示”，不同类型的不定方程解法各有侧重：

1. 二元一次不定方程：先通过\( \gcd(a,b) \mid c \)判断存在性，再用辗转相除法或观察法求特解，最后代入通解公式；

2. n元一次不定方程：通过“降元法”转化为多个二元方程，逐步求解，注意参数的个数（n元方程通解含n-1个独立参数）；

3. 勾股数：本原勾股数用欧几里得公式表示，非本原勾股数由本原勾股数乘正整数得到，可通过模运算分析其性质；

4. 费马问题：费马大定理解决了高次幂和的不定方程解的存在性，费马小定理则是模运算和素数判定的重要工具。

一、不定方程的基本概念

设含\( k \)个未知数\( x_1, x_2, \dots, x_k \)的方程（或方程组）为：\( F(x_1, x_2, \dots, x_k) = 0 \)

若方程个数少于\( k \)，且要求解为整数解（或正整数解、非负整数解），则称其为不定方程（也叫“丢番图方程”，以古希腊数学家丢番图命名）。

解的存在性：并非所有不定方程都有解（如\( x^2 + y^2 = -1 \)无整数解）；

解的个数：若有解，可能有有限个（如\( x^2 + y^2 = 2 \)仅有4组整数解），也可能有无限个（如\( x + y = 1 \)有无限组整数解）；

解的表示：若有无限解，需用“参数形式”表示所有解（如二元一次不定方程的通解）。

二、二元一次不定方程（核心类型）

二元一次不定方程是最基础的不定方程，形式简单、解法成熟，是学习更复杂不定方程的基础。

1. 标准形式与解的存在性

标准形式：设\( a, b, c \)为整数，且\( a, b \)不同时为0，则二元一次不定方程的标准形式为：\( ax + by = c \)

解的存在定理（核心定理）

方程\( ax + by = c \)有整数解的充要条件是：\( \gcd(a, b) \mid c \)（即\( a \)与\( b \)的最大公约数能整除常数项\( c \)）。

必要性：若存在整数\( x_0, y_0 \)满足\( ax_0 + by_0 = c \)，由整除性质“\( \gcd(a,b) \mid ax_0 \)且\( \gcd(a,b) \mid by_0 \)”，得\( \gcd(a,b) \mid (ax_0 + by_0) = c \)；

充分性：由最大公约数的“线性表示定理”，存在整数\( x', y' \)使得\( ax' + by' = \gcd(a,b) \)。若\( \gcd(a,b) \mid c \)，设\( c = \gcd(a,b) \cdot k \)（\( k \)为整数），则\( x_0 = kx' \)、\( y_0 = ky' \)满足\( ax_0 + by_0 = c \)，即方程有解。

通解公式（所有解的表示）

若方程\( ax + by = c \)有一个特解\( (x_0, y_0) \)，令\( d = \gcd(a, b) \)，\( a = d \cdot a' \)，\( b = d \cdot b' \)（此时\( \gcd(a', b') = 1 \)），则方程的所有整数解（通解）为：

\( \begin{cases} x = x_0 + t \cdot b' \\ y = y_0 - t \cdot a' \end{cases} \quad (t \in \mathbb{Z}) \)

或等价形式（\( t \)为任意整数，符号可调整，只要保证\( ax + by \)的增量为0）：

\( \begin{cases} x = x_0 - t \cdot b' \\ y = y_0 + t \cdot a' \end{cases} \quad (t \in \mathbb{Z}) \)

关键说明

\( t \)的作用：\( t \)每取一个整数，就对应一组解；\( t \)遍历所有整数时，得到方程的所有解；

为何用\( b' \)和\( a' \)：因\( \gcd(a', b') = 1 \)，保证\( x \)和\( y \)的增量不会产生重复解，且能覆盖所有解。

解法步骤（三步法）

1. 判断解的存在性：计算\( d = \gcd(a, b) \)，若\( d \nmid c \)，则方程无解；若\( d \mid c \)，进入下一步；

2. 求一个特解：

方法1（辗转相除法逆推）：通过辗转相除法求\( d = \gcd(a, b) \)时，反向推导线性组合\( ax' + by' = d \)，再乘\( k = c/d \)得特解\( (x_0, y_0) = (k x', k y') \)；

方法2（观察法）：对系数较小的方程，直接观察得特解（如\( 2x + 3y = 5 \)，观察得\( x=1, y=1 \)）；

3. 写通解：代入通解公式，整理得所有整数解。

三、n元一次不定方程（推广类型）

n元一次不定方程是二元情况的自然推广，形式和解法均遵循类似逻辑。

1. 标准形式与解的存在性

标准形式

设\( a_1, a_2, \dots, a_n, c \)为整数，且\( a_1, a_2, \dots, a_n \)不同时为0，则n元一次不定方程的标准形式为：

\( a_1 x_1 + a_2 x_2 + \dots + a_n x_n = c \)

解的存在定理

方程有整数解的充要条件是：\( \gcd(a_1, a_2, \dots, a_n) \mid c \)（即所有系数的最大公约数能整除常数项\( c \)）。

证明思路：对n归纳，n=2时即二元情况；假设n=k时成立，n=k+1时，令\( d_k = \gcd(a_1, \dots, a_k) \)，则方程等价于“\( d_k t + a_{k+1} x_{k+1} = c \)”（其中\( a_1 x_1 + \dots + a_k x_k = d_k t \)），由二元情况的存在性得证。

2. 解法步骤（降元法）

n元一次不定方程的核心解法是“逐步降元”，将其转化为多个二元一次不定方程求解：

1. 计算\( d_2 = \gcd(a_1, a_2) \)，解二元方程\( a_1 x_1 + a_2 x_2 = d_2 t_2 \)（\( t_2 \)为新参数），得\( x_1, x_2 \)用\( t_2 \)表示的通解；

2. 计算\( d_3 = \gcd(d_2, a_3) \)，解二元方程\( d_2 t_2 + a_3 x_3 = d_3 t_3 \)（\( t_3 \)为新参数），得\( t_2, x_3 \)用\( t_3 \)表示的通解，代入第一步结果，得\( x_1, x_2, x_3 \)用\( t_3 \)表示的解；

3. 重复上述步骤，直到方程化为\( d_n t_n + a_n x_n = c \)（\( d_n = \gcd(a_1, \dots, a_n) \)），解此二元方程得\( t_n, x_n \)的通解；

4. 回代所有参数，最终得到\( x_1, \dots, x_n \)用若干个独立参数表示的通解。

四、勾股数（二次不定方程经典案例）

勾股数对应“直角三角形三边长均为正整数”的情况，是二次不定方程\( x^2 + y^2 = z^2 \)的正整数解，具有明确的参数表示形式。

1. 基本定义与分类

定义

若正整数\( (x, y, z) \)满足\( x^2 + y^2 = z^2 \)，则称\( (x, y, z) \)为一组勾股数（或“毕达哥拉斯三元组”）。

分类

本原勾股数：若\( \gcd(x, y, z) = 1 \)（即三数互质），则称其为本原勾股数（如\( (3,4,5) \)、\( (5,12,13) \)）；

非本原勾股数：若\( \gcd(x, y, z) = d > 1 \)，则令\( x = d x' \)、\( y = d y' \)、\( z = d z' \)，此时\( (x', y', z') \)是本原勾股数（如\( (6,8,10) = 2 \times (3,4,5) \)，非本原）。

本原勾股数的性质

1. \( x, y \)一奇一偶，\( z \)为奇数（若\( x, y \)均偶，则\( z \)偶，\( d \geq 2 \)，非本原；若\( x, y \)均奇，则\( x^2 + y^2 \equiv 1 + 1 = 2 \mod 4 \)，但\( z^2 \equiv 0 \)或\( 1 \mod 4 \)，矛盾）；

2. \( \gcd(x, y) = \gcd(x, z) = \gcd(y, z) = 1 \)（若\( d \mid x \)且\( d \mid y \)，则\( d \mid z \)，与\( \gcd(x,y,z)=1 \)矛盾）。

2. 本原勾股数的参数公式（欧几里得公式）

所有本原勾股数（不妨设\( x \)为奇数，\( y \)为偶数）可表示为：

\( \begin{cases} x = m^2 - n^2 \\ y = 2mn \\ z = m^2 + n^2 \end{cases} \)

其中参数\( m, n \)满足：

1. \( m > n > 0 \)（正整数，且\( m > n \)保证\( x > 0 \)）；

2. \( \gcd(m, n) = 1 \)（保证三数互质）；

3. \( m, n \)一奇一偶（保证\( x = m^2 - n^2 \)为奇数，\( y = 2mn \)为偶数，\( z = m^2 + n^2 \)为奇数）。

说明

若交换\( x \)和\( y \)的位置，可得到另一组本原勾股数（如\( m=2, n=1 \)时，\( (3,4,5) \)和\( (4,3,5) \)）；

所有非本原勾股数可由本原勾股数乘一个正整数\( d \)得到（如\( d=3 \)，\( (3,4,5) \)变为\( (9,12,15) \)）。

五、费马问题（不定方程经典猜想）

费马问题是数论史上最著名的猜想之一，围绕“高次幂和”的不定方程展开，最终由安德鲁·怀尔斯于1995年证明。

1. 费马大定理（核心猜想）

猜想表述

对任意整数\( n > 2 \)，不定方程：

\( x^n + y^n = z^n \)

没有正整数解\( (x, y, z) \)。

历史背景

1637年，法国数学家费马在《算术》一书的页边写下猜想，并标注“我已找到一个绝妙的证明，但此处空间太小，写不下”；

此后358年，无数数学家尝试证明，直到1995年，英国数学家怀尔斯借助“椭圆曲线”和“模形式”的理论，完成了完整证明，将费马猜想变为“费马大定理”。

\( n=1 \)时，方程\( x + y = z \)有无限多正整数解（如\( (1,2,3) \)、\( (2,3,5) \)）；

\( n=2 \)时，方程即勾股数方程，有无限多正整数解（如\( (3,4,5) \)）；

\( n>2 \)时，不仅无正整数解，也无非零整数解（若存在非零解，可转化为正整数解，与定理矛盾）。

2. 费马小定理（相关定理，非猜想）

费马小定理是数论中的基础定理，虽与费马大定理名称相似，但内容和用途不同，主要用于模运算和素数判定。

定理表述

若\( p \)是素数，且\( \gcd(a, p) = 1 \)（\( a \)与\( p \)互质），则：\( a^{p-1} \equiv 1 \pmod{p} \)

推论

对任意整数\( a \)和素数\( p \)，有\( a^p \equiv a \pmod{p} \)（若\( \gcd(a,p)=1 \)，由定理直接得；若\( p \mid a \)，则\( a^p \equiv 0 \equiv a \pmod{p} \)）。

用途

素数判定的必要条件（若\( a^{n-1} \not\equiv 1 \pmod{n} \)，则\( n \)必为合数，如\( n=341 \)，\( 2^{340} \equiv 1 \pmod{341} \)，但341是合数，故仅为必要条件）；

简化模运算（如计算\( 3^{100} \mod 7 \)，因\( 7 \)是素数，\( 3^6 \equiv 1 \pmod{7} \)，故\( 3^{100} = 3^{6 \times 16 + 4} \equiv 1^{16} \times 3^4 = 81 \equiv 4 \pmod{7} \)）。

（一）二元一次不定方程（例题1-8）

例题1：判断方程\( 3x + 6y = 7 \)是否有整数解

解：计算\( d = \gcd(3, 6) = 3 \)，常数项\( c=7 \)。因\( 3 \nmid 7 \)，由解的存在定理，方程无整数解。

例题2：求方程\( 2x + 3y = 8 \)的所有整数解

解：

1. 存在性：\( d = \gcd(2, 3) = 1 \)，\( 1 \mid 8 \)，方程有解；

2. 求特解：观察得\( x=1, y=2 \)（因\( 2 \times 1 + 3 \times 2 = 8 \)），即特解\( (x_0, y_0) = (1, 2) \)；

3. 写通解：\( a' = 2/1 = 2 \)，\( b' = 3/1 = 3 \)，代入通解公式：

\( \begin{cases} x = 1 + 3t \\ y = 2 - 2t \end{cases} \quad (t \in \mathbb{Z}) \)

（验证：\( 2(1+3t) + 3(2-2t) = 2 + 6t + 6 - 6t = 8 \)，满足方程）。

例题3：求方程\( 4x + 6y = 10 \)的所有整数解

解：

1. 存在性：\( d = \gcd(4, 6) = 2 \)，\( 2 \mid 10 \)，方程有解；

2. 简化方程：两边除以\( d=2 \)，得\( 2x + 3y = 5 \)（先解简化方程，再还原）；

3. 求简化方程的特解：观察得\( x=1, y=1 \)（\( 2 \times 1 + 3 \times 1 = 5 \)）；

4. 简化方程的通解：\( a'=2/1=2 \)，\( b'=3/1=3 \)，通解为\( \begin{cases} x = 1 + 3t \\ y = 1 - 2t \end{cases} \)（\( t \in \mathbb{Z} \)）；

5. 原方程的通解：与简化方程相同（因除以的是\( d=2 \)，解不变），即上述通解。

例题4：用辗转相除法求方程\( 5x + 7y = 1 \)的一个特解

解：

1. 用辗转相除法求\( d = \gcd(5,7) \)：

\( 7 = 1 \times 5 + 2 \)

\( 5 = 2 \times 2 + 1 \)

\( 2 = 2 \times 1 + 0 \)，故\( d=1 \)；

2. 反向推导线性组合：

由\( 5 = 2 \times 2 + 1 \)，得\( 1 = 5 - 2 \times 2 \)；

由\( 7 = 1 \times 5 + 2 \)，得\( 2 = 7 - 1 \times 5 \)，代入上式：

\( 1 = 5 - 2 \times (7 - 5) = 3 \times 5 - 2 \times 7 \)；

3. 特解：对比\( 5x + 7y = 1 \)，得\( x_0=3, y_0=-2 \)（验证：\( 5 \times 3 + 7 \times (-2) = 15 - 14 = 1 \)）。

例题5：求方程\( 3x - 5y = 7 \)的所有正整数解

解：

1. 存在性：\( d = \gcd(3, -5) = 1 \)，\( 1 \mid 7 \)，方程有解；

2. 求特解：观察得\( x=4, y=1 \)（\( 3 \times 4 - 5 \times 1 = 12 - 5 = 7 \)）；

3. 写通解：\( a'=3/1=3 \)，\( b'=-5/1=-5 \)，通解为\( \begin{cases} x = 4 + (-5)t = 4 - 5t \\ y = 1 - 3t \end{cases} \)（\( t \in \mathbb{Z} \)）；

4. 求正整数解：需\( x > 0 \)且\( y > 0 \)：

\( 4 - 5t > 0 \implies t < 4/5 \)；

\( 1 - 3t > 0 \implies t < 1/3 \)；

因\( t \in \mathbb{Z} \)，故\( t \leq 0 \)。分别验证：

\( t=0 \)：\( x=4, y=1 \)（正解）；

\( t=-1 \)：\( x=9, y=4 \)（正解）；

\( t=-2 \)：\( x=14, y=7 \)（正解）；

...（\( t \)取负整数时，\( x, y \)均为正），故所有正整数解为：

\( \begin{cases} x = 4 - 5t \\ y = 1 - 3t \end{cases} \quad (t \in \mathbb{Z}, t \leq 0) \)

或等价表示为\( \begin{cases} x = 4 + 5k \\ y = 1 + 3k \end{cases} \quad (k \in \mathbb{N}) \)（\( k = -t \geq 0 \)）。

例题6：求方程\( 6x + 9y = 15 \)的非负整数解

解：

1. 简化方程：\( d = \gcd(6,9)=3 \)，\( 3 \mid 15 \)，两边除以3得\( 2x + 3y = 5 \)；

2. 求简化方程的通解：观察得特解\( (x_0, y_0)=(1,1) \)，通解为\( \begin{cases} x = 1 + 3t \\ y = 1 - 2t \end{cases} \)（\( t \in \mathbb{Z} \)）；

3. 求非负整数解：需\( x \geq 0 \)且\( y \geq 0 \)：

\( 1 + 3t \geq 0 \implies t \geq -1/3 \)；

\( 1 - 2t \geq 0 \implies t \leq 1/2 \)；

故\( t=0 \)，对应解\( x=1, y=1 \)；

验证：\( 6 \times 1 + 9 \times 1 = 15 \)，符合要求，故非负整数解仅为\( (1,1) \)。

例题7：求方程\( 2x + 4y = 8 \)的所有整数解

解：

1. 简化方程：\( d = \gcd(2,4)=2 \)，\( 2 \mid 8 \)，两边除以2得\( x + 2y = 4 \)；

2. 求特解：观察得\( x=4, y=0 \)；

3. 写通解：\( a'=1/1=1 \)，\( b'=2/1=2 \)，通解为\( \begin{cases} x = 4 + 2t \\ y = 0 - t \end{cases} \quad (t \in \mathbb{Z}) \)；

或整理为\( \begin{cases} x = 4 + 2t \\ y = -t \end{cases} \)（验证：\( 2(4+2t) + 4(-t) = 8 + 4t - 4t = 8 \)）。

例题8：证明方程\( 2x + 4y = 5 \)无整数解

解：计算\( d = \gcd(2,4)=2 \)，常数项\( c=5 \)。因\( 2 \nmid 5 \)，由二元一次不定方程解的存在定理，方程无整数解；

另证（模2分析）：左边\( 2x + 4y \equiv 0 + 0 = 0 \pmod{2} \)，右边\( 5 \equiv 1 \pmod{2} \)，左右模2不等，故无整数解。

（二）n元一次不定方程（例题9-12）

例题9：求方程\( x + 2y + 3z = 7 \)的所有整数解

解：用降元法，先固定\( z \)为参数，转化为二元方程：

1. 令\( z = t \)（\( t \in \mathbb{Z} \)），方程变为\( x + 2y = 7 - 3t \)（二元一次方程）；

2. 解二元方程\( x + 2y = 7 - 3t \)：

特解：观察得\( x_0 = 7 - 3t \)，\( y_0 = 0 \)（因\( (7-3t) + 2 \times 0 = 7-3t \)）；

通解：\( a'=1/1=1 \)，\( b'=2/1=2 \)，通解为\( \begin{cases} x = (7 - 3t) + 2s \\ y = 0 - s \end{cases} \quad (s \in \mathbb{Z}) \)；

3. 原方程的所有整数解（含两个参数\( s, t \)）：

\( \begin{cases} x = 7 - 3t + 2s \\ y = -s \\ z = t \end{cases} \quad (s, t \in \mathbb{Z}) \)

（验证：\( (7-3t+2s) + 2(-s) + 3t = 7 - 3t + 2s - 2s + 3t = 7 \)，满足方程）。

例题10：求方程\( 2x + 3y + 4z = 10 \)的所有非负整数解

解：降元法，先固定\( z \)（非负整数，故\( z \)的可能值：\( 4z \leq 10 \implies z=0,1,2 \)）：

1. 当\( z=0 \)时，方程变为\( 2x + 3y = 10 \)：

非负整数解：\( y=0 \implies x=5 \)；\( y=2 \implies x=2 \)；\( y \geq 4 \implies 3y > 10 \)，故解为\( (5,0,0) \)、\( (2,2,0) \)；

2. 当\( z=1 \)时，方程变为\( 2x + 3y = 6 \)：

非负整数解：\( y=0 \implies x=3 \)；\( y=2 \implies x=0 \)；故解为\( (3,0,1) \)、\( (0,2,1) \)；

3. 当\( z=2 \)时，方程变为\( 2x + 3y = 2 \)：

非负整数解：\( y=0 \implies x=1 \)；故解为\( (1,0,2) \)；

4. 综上，所有非负整数解为：\( (5,0,0) \)、\( (2,2,0) \)、\( (3,0,1) \)、\( (0,2,1) \)、\( (1,0,2) \)。

例题11：判断方程\( 2x + 4y + 6z = 5 \)是否有整数解

解：计算所有系数的最大公约数\( d = \gcd(2,4,6) = 2 \)，常数项\( c=5 \)。因\( 2 \nmid 5 \)，由n元一次不定方程解的存在定理，方程无整数解；

另证（模2分析）：左边\( 2x + 4y + 6z \equiv 0 \pmod{2} \)，右边\( 5 \equiv 1 \pmod{2} \)，矛盾，故无整数解。

例题12：求方程\( x + y + z = 6 \)的所有正整数解

解：此为“stars and bars”问题（正整数解个数公式：\( C_{n-1}^{k-1} \)，其中\( n=6 \)，\( k=3 \)，个数为\( C_5^2=10 \)），具体解如下：

固定\( x \)的正整数值（\( x=1,2,3,4 \)，因\( x \geq 1 \)且\( y,z \geq 1 \implies x \leq 4 \)）：

\( x=1 \)：\( y + z = 5 \)，正解为\( (1,1,4) \)、\( (1,2,3) \)、\( (1,3,2) \)、\( (1,4,1) \)；

\( x=2 \)：\( y + z = 4 \)，正解为\( (2,1,3) \)、\( (2,2,2) \)、\( (2,3,1) \)；

\( x=3 \)：\( y + z = 3 \)，正解为\( (3,1,2) \)、\( (3,2,1) \)；

\( x=4 \)：\( y + z = 2 \)，正解为\( (4,1,1) \)；

综上，所有正整数解共10组，即上述解。

（三）勾股数（例题13-17）

例题13：用欧几里得公式生成两组本原勾股数

解：欧几里得公式：\( x = m^2 - n^2 \)，\( y=2mn \)，\( z=m^2 + n^2 \)，需\( m > n > 0 \)，\( \gcd(m,n)=1 \)，\( m,n \)一奇一偶：

1. 取\( m=2 \)（偶），\( n=1 \)（奇）：\( \gcd(2,1)=1 \)，则\( x=4-1=3 \)，\( y=2×2×1=4 \)，\( z=4+1=5 \)，即\( (3,4,5) \)；

2. 取\( m=3 \)（奇），\( n=2 \)（偶）：\( \gcd(3,2)=1 \)，则\( x=9-4=5 \)，\( y=2×3×2=12 \)，\( z=9+4=13 \)，即\( (5,12,13) \)；

两组均为本原勾股数（\( \gcd(3,4,5)=1 \)，\( \gcd(5,12,13)=1 \)）。

例题14：判断\( (6,8,10) \)是否为本原勾股数，若不是，转化为本原勾股数

解：

1. 计算\( \gcd(6,8,10)=2 > 1 \)，故\( (6,8,10) \) 非本原勾股数；

2. 转化为本原勾股数：将三数除以\( d=2 \)，得\( (6/2, 8/2, 10/2) = (3,4,5) \)，\( (3,4,5) \)是本原勾股数。

例题15：求所有含正整数\( x=7 \)的本原勾股数

解：设本原勾股数为\( (7, y, z) \)，满足\( 7^2 + y^2 = z^2 \)，即\( z^2 - y^2 = 49 \)，因式分解得\( (z - y)(z + y) = 49 \)；

因\( z > y > 0 \)，且\( z - y < z + y \)，\( z - y \)与\( z + y \)均为正整数，且\( \gcd(z - y, z + y) = \gcd(z - y, 2z) = \gcd(z - y, 2) \)（因\( \gcd(z - y, z + y) \mid (z + y) - (z - y) = 2y \)，且\( \gcd(z,y)=1 \)）；

又\( 49=1×49 \)（唯一正整数分解，因49是素数7的平方），故：

\( \begin{cases} z - y = 1 \\ z + y = 49 \end{cases} \)

解得\( z=(1+49)/2=25 \)，\( y=(49-1)/2=24 \)；

故含\( x=7 \)的本原勾股数为\( (7,24,25) \)（验证：\( 7^2 + 24^2 = 49 + 576 = 625 = 25^2 \)）。

例题16：证明勾股数中必有一个数能被3整除

解：用反证法，假设存在勾股数\( (x,y,z) \)，且\( x,y,z \)均不被3整除；

整数模3的平方只能是0或1（因\( 0^2 \equiv 0 \)，\( 1^2 \equiv 1 \)，\( 2^2 \equiv 4 \equiv 1 \pmod{3} \)）；

因\( x,y \)不被3整除，故\( x^2 \equiv 1 \)，\( y^2 \equiv 1 \pmod{3} \)，则\( z^2 = x^2 + y^2 \equiv 1 + 1 = 2 \pmod{3} \)；

但\( z^2 \equiv 0 \)或\( 1 \pmod{3} \)，矛盾，故假设不成立，勾股数中必有一个数能被3整除。

例题17：求勾股数中最小的三个数均为正整数的非本原勾股数

解：本原勾股数中最小的是\( (3,4,5) \)，非本原勾股数由本原勾股数乘正整数\( d>1 \)得到；

取\( d=2 \)，则\( (3×2, 4×2, 5×2) = (6,8,10) \)，验证：\( 6^2 + 8^2 = 36 + 64 = 100 = 10^2 \)，且\( \gcd(6,8,10)=2>1 \)，故\( (6,8,10) \)是最小的非本原勾股数。

（四）费马问题（例题18-20）

例题18：用费马小定理计算\( 2^{100} \mod 11 \)

解：11是素数，且\( \gcd(2,11)=1 \)，由费马小定理：\( 2^{10} \equiv 1 \pmod{11} \)；

将\( 100 \)表示为\( 10×10 + 0 \)，则\( 2^{100} = (2^{10})^{10} \equiv 1^{10} = 1 \pmod{11} \)；

故\( 2^{100} \mod 11 = 1 \)。

例题19：证明方程\( x^3 + y^3 = z^3 \)没有正整数解（费马大定理n=3的特殊情况，简化证明）

解：用无穷递降法（费马本人曾用此方法证明n=4的情况，n=3的证明由欧拉完成，此处简化思路）：

假设存在正整数解\( (x_0, y_0, z_0) \)，满足\( x_0^3 + y_0^3 = z_0^3 \)，且\( z_0 \)是最小的正整数解；

1. 可设\( \gcd(x_0, y_0)=1 \)（若\( \gcd(x_0,y_0)=d>1 \)，则\( d^3 \mid z_0^3 \implies d \mid z_0 \)，令\( x_0=d x_1 \)，\( y_0=d y_1 \)，\( z_0=d z_1 \)，则\( x_1^3 + y_1^3 = z_1^3 \)，且\( z_1 < z_0 \)，与\( z_0 \)最小矛盾）；

2. 由\( \gcd(x_0,y_0)=1 \)，\( x_0, y_0 \)一奇一偶，不妨设\( x_0 \)奇，\( y_0 \)偶，则\( z_0 \)奇；

3. 因式分解：\( z_0^3 + (-y_0)^3 = x_0^3 \)，即\( (z_0 - y_0)(z_0^2 + z_0 y_0 + y_0^2) = x_0^3 \)；

4. 证明\( \gcd(z_0 - y_0, z_0^2 + z_0 y_0 + y_0^2)=1 \)：设\( p \)是素数，\( p \mid z_0 - y_0 \)且\( p \mid z_0^2 + z_0 y_0 + y_0^2 \)，则\( p \mid (z_0^2 + z_0 y_0 + y_0^2) - (z_0 + 2y_0)(z_0 - y_0) = 3y_0^2 \)，且\( p \mid x_0^3 \)，故\( p \mid 3 \)或\( p \mid y_0 \)；若\( p \mid y_0 \)，则\( p \mid z_0 \)，与\( \gcd(y_0,z_0)=1 \)矛盾；若\( p=3 \)，可进一步推导存在更小的解；

5. 因\( \gcd(z_0 - y_0, z_0^2 + z_0 y_0 + y_0^2)=1 \)，且其乘积为立方数，故两者均为立方数：\( z_0 - y_0 = a^3 \)，\( z_0^2 + z_0 y_0 + y_0^2 = b^3 \)，其中\( a^3 b^3 = x_0^3 \implies x_0 = ab \)；

6. 由\( z_0 = a^3 + y_0 \)，代入第二个方程得\( (a^3 + y_0)^2 + (a^3 + y_0)y_0 + y_0^2 = b^3 \)，整理得\( 3a^3 y_0 + 3a^6 + 3y_0^2 = b^3 \)，即\( 3y_0(a^3 + y_0) + 3a^6 = b^3 \)，进一步推导可得存在更小的解\( z_1 < z_0 \)，矛盾；

故假设不成立，方程\( x^3 + y^3 = z^3 \)没有正整数解。

例题20：用费马小定理判断123是否为素数

解：费马小定理是素数的必要条件：若n是素数，且\( \gcd(a,n)=1 \)，则\( a^{n-1} \equiv 1 \pmod{n} \)；若存在a使得\( a^{n-1} \not\equiv 1 \pmod{n} \)，则n是合数；

取a=2，n=123，\( \gcd(2,123)=1 \)，计算\( 2^{122} \mod 123 \)：

1. 因123=3×41，先计算\( 2^{122} \mod 3 \)和\( 2^{122} \mod 41 \)，再用中国剩余定理合并；

2. 模3：\( 2^2 \equiv 1 \pmod{3} \)，\( 122=2×61 \)，故\( 2^{122} \equiv 1^{61}=1 \pmod{3} \)；

3. 模41：41是素数，\( 2^{40} \equiv 1 \pmod{41} \)（费马小定理），\( 122=40×3 + 2 \)，故\( 2^{122} \equiv (1)^3 × 2^2 = 4 \pmod{41} \)；

4. 找x满足\( x \equiv 1 \pmod{3} \)且\( x \equiv 4 \pmod{41} \)：设x=41k + 4，代入得\( 41k + 4 \equiv 2k + 1 \equiv 1 \pmod{3} \implies 2k \equiv 0 \pmod{3} \implies k \equiv 0 \pmod{3} \)，令k=3m，x=123m + 4，故\( 2^{122} \equiv 4 \pmod{123} \)；

因\( 4 \not\equiv 1 \pmod{123} \)，故123是合数（实际123=3×41）。