费马—欧拉素数定理

大家好，欢迎来到IT知识分享网。

每个可表示为 4n + 1 形式的素数，只能用一种两数平方和的形式来表达。

十七世纪伟大的法国数学家费马（1601 – 1665 年）大约于 1660 年发现了这一著名的定

理。然而直到 1670 年才得以发表，在费马的儿子编辑的丢番图（Diophantus）著作中以附注的形式出现，不幸的是没有证明。不能肯定费马是否已经得出证明。

大约一百年后，才由欧拉第一次发表了这一定理的证明，这是他寻求解决但劳而无功的若干年后，才写出了论文“费马定理的证明，形为 4n + 1 素数可以表示为两数平方之和”

现在费马—欧拉定理已经有了好几种证法。下面的证明具有最简化的特色。

对于不熟悉数论的读者，我们将提供一些说明，这对于理解这一证明是必要的，并且对于第 22 题所讨论的问题也是有用的。同时必须记住此处和地方 22 题中所用字母均表示整数。

两个数 a 和 b [参照高斯（Gauss）著作]，当其差能被 m 所以整除时，就叫做对于模数 m 是同余的，写作：a ≡ b mod m，读作对模 m，a 与 b 同余。例如每个数对于模数（模）m 同余于被 m 除时所得的余数，如 65 ≡ 2 mod 7。余数一词有更广泛的意义，意味着对于任意选择的商做除法后所得的余数。例如，如果写成这样 65 /7=12 ，所留的余数为–19。

在许多可能的余数之中有两个余数特别重要：一为约定余数或称普通余数，它是正数而已

小于除数；一为最小余数，其绝对值不大于除数的一半。例如 89/13 除得的最小余数为–2。因89/13=7-2/13,这也可以写作 89 ≡ –2 mod 13。

对于同一模数同余，可应用下述不证自明的规则：

1、如两数同余于第三数，则此两数也彼此同余。

2、两个同余式可以相加，相减和相乘。

由

A ≡ B mod m，a ≡ b mod m

得到

A ± a ≡ B ± b mod m

及

Aa ≡ Bb mod m。

（例如由 A = B + Gm 和 a = b + gm 可以得到 Aa = Bb + pm（p 为整数），亦即 Aa ≡ Bb modm。）

3、 同余式a ≡ b mod m可乘以任意整数 g：

ag ≡ bg mod m。

只有当 g 为 a 与 b 的公约数而且 g 与模数 m 没有公约数时同余式才可以被 g 除。例如用 7

去除 49 ≡ 14 mod 5，我们得到一个正确的同余式 7 ≡ 2 mod 5。

如有 m 个正整数的数系中无两个数同余于模数 m，则该数系就称作一个模数 m 的完全剩余系。最简单的完全剩余系是 m 个普通余数 0，1，2，…，m – 1 的系，其次最简单的为m 的最小余数的系。

对于模数 m，每个 z 与完全剩余系 mod m 中的一个数且仅当一个数同余。

下述定理特别重要：

定理：如果用一个与模数没有公约数的数去乘完全剩余系的各数，则得到对于这一模数的又一个完全剩余系。

证：令模数为 m，a 是与 m 没有公约数的乘数。那么如果对于给定的剩余系由两个不相等的数 x 和 x′，

ax ≡ ax′ mod m

成立，则根据同余规则 3 必有 x ≡ x′ mod m，而这是不可能的。从这一定理可以直接得出：

a 与 m 没有公约数时同余式

ax ≡ b mod m

在每个完全剩余系modm中，具有一个而且仅有一个“根”x。

二次剩余

有两个无公约数的数，如其中一个数以相关的另一个数为模同余于某个平方数，则此数叫做另一数的二次剩余。如果不存在这样的平方数，则称为二次非剩余。例如 12 是 13 的二

次剩余，因为 12 ≡ 8^2 mod 13；–1 是 3 的二次非剩余，由于不存在一个平方数x^2，x^2 ≡ –1 mod 3。

以下为应用于奇素数模 p 的有关二次剩余定理：

1．如所给定两个数的平方彼此同余，例如

与 y 从 1，2，3，…，p – 1 的 Σ 系中选择以满足（0）式。对于 Σ 系中的每一个 x，只有唯一的共轭数 y，（由 xy ≡ D mod p 以及 xy′ ≡ D mod p 得到

xy ≡ xy′ mod p，

并由此而得到或y ≡ y′ mod p

y – y′ ≡ 0 mod p。

然而由于y和y′ 均小于或等于p – 1，所以仅当y = y′ 时二者的差才能被p整除。） 从Σ中任意选择x1，根据

x1y1 ≡ D mod p

来确定y1，进而我们从Σ中选取不等于x1和y1的一个数x2，且由

x2y2 ≡ D mod p

来确定y2，那么y2也不等于x1或y1。

用这种方法连续运算，直至所得的同余式中列出 Σ 中所有的数。