欧拉-费马定理，是初等数论的重要成果，具有众多应用，包括现代密码学。它们可以通过许多不同的方法来证明，每种方法都提供有趣的见解。

在本文中，我将以它们为借口介绍群论，这是一门非常美丽且应用广泛的数学学科。

我首先陈述我打算证明的定理，内容不多。它们的内容和符号将在本文中解释。

费马小定理

如果p是素数并且a是任何小于p 的整数，则

整数

让我们回顾一下关于整数的一些事实。当我们将一个整数除以另一个整数时，我们得到一个商和一个余数。如果我用n除以a，余数为0，则a称为n的约数。除了 1 和它本身之外没有任何约数的数称为素数。如果两个数没有公约数，则称它们为互质数或互质数。整数的一个基本属性是它们可以唯一地写成素数的乘积。这使得素数成为数论中的重要组成部分。

有一个程序可以确定两个数是否互质，如果不是，则找到它们的约数。给定两个整数a和b，它们的最大公约数 (Greatest Common Divisor)或 GCD 是整除a和b的最大数。如果 GCD 为 1，则整数a和b互质。一个实际的质数与所有其他整数互质。

以下是 GCD 的一些示例：

GCD(15, 9) = 3

GCD(30, 45) = 15

GCD(15, 28) = 1

有一个用于计算 GCD 的递归算法。它被称为欧几里德算法，它非常简单，只需几行Python代码即可实现。欧几里德算法的结果是以下定理：

定理： GCD 是一个线性组合。存在整数s,t使得 as+nt = GCD(a,n)

我省略了证明，它不难但有点乏味并且与我希望涵盖的主题无关。

模运算

对于任意两个整数a, n，数字a mod n表示a除以n的余数。例如，
8 模 5 = 3

7 模 6 = 1

3 模 8 = 3

16 模 8 = 0

-1 模 9 = 8

解释表达式a mod n = b 的等效方法是说n除(ab)。

我们可以将乘法与模运算结合起来：

5 * 3 模 4 = 15 模 4 = 3

8 * 5 模 7 = 40 模 7 = 5 模 7

8 * 12 模 7 = 96 模 7 = 5 模 7

有一个巧妙的技巧可以使最后两个计算更容易。我可以先计算每个被乘数的模，而不是先计算乘积然后取模，如下所示：

8 * 12 模 7 = (8 模 7)*(12 模 7) 模 7= 1*5 模 7 = 5 模 7

一般来说：

a *b mod n = (a mod n)*(b mod n) mod n

这是关于一般算术的重要结果，稍后会派上用场：

定理：如果 GCD(a,n) = 1，则存在 x < n，使得 ax = 1 mod n。

证明：我在上一节中已经说明 GCD 是一个线性组合，因此存在整数 s,t 使得as+nt = 1，这意味着as =1- nt，由此得出as = 1 mod n . s 可能不小于n，但没关系，因为我们可以设置x = s mod n，然后它遵循

斧 = 1 模 n。

QED

群论

群是对具有可逆二元运算的集合的数学抽象。例如，如果我将一个实数a乘以一个数b ，我可以通过再次乘以1/b来恢复原始数字。一个群的重要特征是（1）它有一个元素叫做单位元，它的作用很像乘以 1 和（2）每个元素都有一个倒数。

用更正式的语言来说：

Group 是具有二元运算的集合G，用 * 表示，具有以下性质：

1. G中存在一个元素1（恒等式），使得对于G中的彼此g，1*g=g*1=g
2. 对于G中g中的每个元素，存在另一个元素g?1，称为g的逆元素，使得g*g?1=g?1*g = 1
3. 对于G中的任何元素g,h,z，(g*h)*z = g*(h*z)

最后一个属性称为关联性。如果我们还具有对于任意两个元素 g ,h, g*h = h*g 的性质，则该群称为交换群。如果集合G的元素个数有限，则它是一个有限群，元素的个数称为群的阶，用 || 表示。出于本文的目的，我们将只处理有限交换群。

操作 * 可以代表满足这些属性的任何操作。它可能是乘法、加法、函数的组合，甚至是完全不同的东西。例如，考虑四个二进制字符串 00,01,10,11。这些字符串在异或运算 XOR 下形成一个组。在这种情况下，标识元素是 00，因为

我们将再次遇到这个群体，使用不同的结构和符号，但它具有相同的属性。

我使用符号 a2 来代表 a*a 。通常，每当我将 a 自身“乘以”k 次时，我会将结果表示为 a?

子群是G的子集H，它本身就是一个群。这意味着H必须包含身份，并且如果任何元素h在H中，则它的逆元素也必须在H中。

这是为有限群构造子群的一种方法。取任何不是恒等式的元素g，并形成幂g,g2,g3 ,...。由于群体是有限的，这些力量不能无限期地持续下去，但最终，元素将开始重复。事实上，在某些时候，会有一些 g?=1 的。这就是为什么这个子群被称为循环的并用<g>表示的原因。g?=1 的最小数k称为g的阶，它是<g>中元素的数量。

组的例子

乘法下的整数是不是群的例子。有一个恒等元，但没有乘法逆元，因为没有整数可以与 3 相乘，例如，得到 1。

有理数（0 除外）是一个群，因为任何非零有理数，写为两个整数的商/ 具有乘法逆数/ a。当然，这是一个无限群。

如果我们不使用正则乘法，而是使用模乘法，则有一种方法可以用整数构建有限群。但我们必须小心，因为有些情况我们想避免。例如，2 *3 mod 6 = 0。因此，2 和 3 没有 mod 6 的乘法逆元。

对于任何整数n，我们将集合U(n)定义为小于n且与? n互质的所有整数a。

定理：定义为 {k < n，使得 GCD(k,n) = 1} 的集合 U(n) 是乘法 mod n 下的有限交换群。

证明：

模乘法继承了普通乘法的交换律和结合律，所以我们已经有了这些性质。我们还有身份元素，它仍然是 1。此外，根据它的定义，集合是有限的。我们只需要确定逆的存在。

在上一节中，我们证明了如果GCD(a, n)= 1，则存在x < n使得ax = 1 mod n，这意味着x是a的倒数。

QED

例子：

U(4)= {1,3}

U(p) = {1,2,3,..p-1} 对于素数 p

U(8) = {1,3,5,7}

让我们仔细看看最后一个例子。注意

32 = 52 = 72 = 3*5*7 = 1 mod 8

此外，

3*5 = 7 模 8，5*7 = 3 模 8，7*3 = 5 模 8。

这与我之前使用符号 00,01,10,11 和 XOR 运算构建的组完全相同！

拉格朗日定理

我们现在准备建立关于有限群的第一个重要事实。我们的最终目标，即欧拉-费马定理，将是这一事实的简单结果。

拉格朗日定理子群的阶数除以群的阶数。

证明 ：

令H为有限群G的非平凡子群。非平凡意味着H不等于G，也不是 仅包含身份元素 {1} 的群。让|H| = k是H的阶数

让我们按某种顺序枚举H的元素：

H = {1,h1,h2, ...}

然后对于G的每个元素g，形成定义为的集合 g*H

{g, g*h1, g*h2, …}

请注意，由于逆元的存在， g*H中的所有元素都是不同的，这意味着g*H与H具有相同数量的元素。

我们需要确定以下事实：对于G的两个不同元素g1和g2，集合g1*H和g2*H要么相同要么不相交。

假设它们不相交，因此它们有一个公共元素x。那么，在G中存在a、b，在H中存在 h1、h2，这样：

x= a*h1和x = b*h2

令y为a*H的任意元素，我可以将其写为y = a*h。然后

现在，请注意因为H是一个子群并且元素h、h1、h2都属于H，所以h2*h1?1*h也属于 H。这意味着y属于b*H，这意味着如果它们有任何公共元素，集合a*H和b*H是相同的。

我们建立的最后一个事实，即不同的集合a*H是不相交的，是证明定理的关键。由于G的每个元素g都属于这些集合之一（特别是g*H），因此G可以写成不相交集合的并集。假设有m 个这样的不相交集合。此外，这些集合中的每一个都具有相同数量的元素k。这意味着|G| = mk = m|H| ，也就是说，H的阶数除以G的阶数。

QED

我应该指出，虽然我关注的是交换群，但拉格朗日定理对于非交换群也适用，因为它的证明中没有使用交换性。

欧拉费马定理

引用库尔特·哥德尔的话，我们现在来到练习的对象。首先，我将介绍最后一点符号。我们之前看到的集合U(n)的阶有一个特殊的名字，称为 E uler's totient 函数

()=|U(n)| = #{k<n 使得 GCD(k,n) = 1}。

这是小于n且与?? n互质的正整数的数目。

以下推论是拉格朗日定理的直接推论：

推论：对于有限群 G 的每个元素 g

结论

这是对群的快速介绍，我们在其中建立了有限群的拉格朗日定理，然后用它来证明欧拉-费马定理和费马小定理。这些定理在现代密码学中有重要的应用，例如 RSA 算法和 Diffie-Hellman 密钥交换。我很快就会写另一篇文章，我将在本文介绍的材料的基础上解释这些密码分析算法。