转眼欧拉系列已经写了10篇，进入尾声的同时也是渐入佳境。前面我们聊到的是立体和平面几何，图论，复数领域的欧拉定理，相关内容请戳：
而今天要介绍的，是谈到欧拉所不得不提的一个重要成就，那就是欧拉数论定理。如果说数学是科学的皇后，那数论就是数学的掌上明珠，关于数论的研究仿佛就像探究宇宙的真理一般，奥妙无穷。数论欧拉定理无疑是璀璨的数论星河里最亮的一颗，今天，我们尝试着用不同层级的角度来理解它，证明它，从一般初等数论一直讲到群论。在讲欧拉定理前，我们先来看其更特殊而简单的形式：费马小定理。费马小定理：若a为整数，p为质数，那么a ^ p - p一定是p的倍数，用模运算的符号可以写为：当a不是p的倍数的时候，p | a ^ p, p都必不成立，因此也可以把结论写为：当p不是质数的时候，只要(a, p) == 1，也会有a ^ phi(p) == 1(mod p)， phi(p)是欧拉函数，表示比p小的与p互质的数的数量。这个结论不是别的，正是欧拉定理：a，m是正整数，(a, p) = 1，有a ^ phi(p) == 1(mod p)。
当p为质数的时候，有phi(p) = p - 1，此时退化为费马小定理。那这个结论怎么证明呢？我们先来看一下基于mod运算的一个传统证明，再来看一个揭露其物理意义和结构的巧妙解法。首先证明：对于数列a, 2a, ......, (p - 1)a，共(p - 1)个数，设他们除以p的余数分别为r1, r2, ......, r(p - 1)，它刚好是1:(p - 1)的一个排列。证明如下：因为gcd(a, p) = 1，作为素数gcd(k, p) = 1对任意正整数k < p成立，因此序列{r(p - 1)}没有一个是0。显然，以上序列中任意两个的差的绝对值也仍然是序列中的元素，因此也不可能被p整除，故序列{r(p - 1)}的任意两个值不相等，该序列为1:(p - 1)上的双射，即排列。a * 2a * ...... * (p - 1)a == r1 * r2 * ...... * r(p - 1)(mod p)a ^ (p - 1) * (p - 1)! == (p - 1)!(mod p)（模乘法交换律和结合律）a ^ (p - 1) == 1(mod p)（模运算性质）用这个思路同步证明欧拉定理也很简单，只需要把上面的1:(p - 1)改成所有小于p并与其互质的数的集合x1, x2, ......, xphi(p)，其余步骤就都是一样的了。从中你也可以体会这里的变化，欧拉函数表示的是小于p的与其互质的数的集合的大小，而这个集合本身定义出的这些元素才是关键，它们都和p互质才使得推导成立。如果你还记得我们在《序列周期性与魔术（四）——周期序列数学性质深入探秘》系列文章里所提到的Residues Module A Prime定理的相关内容，会发现它就是费马小定理证明所用的引理，只不过那里是直接在数牌的时候用上了，这儿是在mod乘法上的结论。证明是证明出来了，可这个结论除了能做题以外，有什么实际的数学模型背景呢？我们先来看看a ^ p是什么，在排列组合中，乘方一般计算的是给定集合大小为底数a，放回采样地取指数p那么长的序列的方法总数。于是我们可以想象一组跑马灯，长度为p，每个位置一共有a种颜色，显然，除非所有位置的颜色都一样，那么对于这样任意的一个序列{a_p}，其循环移位，也就是序列{a_((i + q) mod p)}，取q = 1, 2, ......, p - 1加上其原始序列，一共有p个，他们两两之间显然互不相同。因为，如果有任意q1 != q2(q1 < q2)，a_((i + q1) mod p) = a_((i + q2) mod p)，即a_((i + q1 - q2) mod p) = a_(i mod p)，说明序列是个以q1 - q2为周期的周期序列。这要求(q2 - q1) | p，又p是质数，所以只能是q2 - q1 = 1，这时候刚好对应的是所有颜色都一样的序列，这样的序列一共有a个，除了他们以外，一共有a ^ p - a个序列，他们以其循环序列是否仅仅相差相位被分割成若干集合，每个集合大小是p，因此a ^ p - a == 0 (mod p)，又a不是p的倍数，所以a ^ (p - 1) - 1 == 0 (mod p)，即a ^ (p - 1) == 1(mod p)，费马小定理得证。因此，这便给出了费马小定理的一个物理意义和应用背景，那就是对于一个定长序列，其互相差相位的序列可以构成循环群，在长度为质数的时候，这个循环群的大小就是长度，除了字母集合数量那么多个周期长度为1的序列除外。但是很遗憾，我绞尽脑汁也没找到这个思路拓展到欧拉定理的方法，可能真的只适合证明这个特例而已吧！另外的证明方法还有用二项式定理展开的，和我们的主线没有关系，暂时不讲了，但是还有个基于群论观点的证明，再次让我看到了用更高级别数学来降维打击的巨大威力。考虑(a, p) = 1的情况，此时所有mod p的余数，构成mod p乘法群，因为p是质数，所以这个群的阶为p - 1。于是对于群内任意元素a，以其为生成元生成的群为整个群的循环子群，有a ^ d == 1(mod p)。根据拉格朗日定理，a生成群的阶整除整个群的阶，因此a ^ (p - 1) == 1 ^ (p - 1) / d == 1(mod p)，故原命题得证。这里，其实并不要求p一定是质数，只要(a, p) = 1，其mod p的乘法群的大小是phi(p)，a是其中的元素，就有a ^ phi(p) == 1(mod p)，这个式子就是著名的欧拉定理了。首先，我们有一类运算，叫做带模运算，即在普通的整数加法，乘法基础上，再取某个正整数的mod值，再这样一个运算下来构建一个数学结构。此时它们的逆运算，减法和除法，也都是在新的运算意义下来定义的。加法得到的叫做整数模n加法群，它把所有的整数都归为了n个等价类，取0:(n - 1)就可以构成该群的一个元素代表集合，叫做完全代表系。这个群并不是凭空捏造的，而是有足够的实际应用背景，任何和周期有关的东西，本质都是这个群是上的运算。比如时间的计算，18点后10个小时是几点，周期函数的计算，sin(2pi + x) = sin(x)，一个正六边形的对称性等等，背后都是这个结构。世界没有那么新鲜，有很多周而复始出现的对象，因此这个结构囊括了这一大类的现象。还有一类叫做整数模n乘法群，对应的整数乘法mod n这样一个运算，其互质同余类可以构成一个群（其逆元素的存在性用到配数定理，详细内容专门文章再讲），也称为mod n的既约剩余类，这些元素的集合也叫作完全剩余系，其大小就是与n互质的比n小的元素的个数，记作phi(n)，没错，这就是著名的欧拉函数了，它是正整数n对应的mod n乘法群的大小，也就是和n互质的比n小的正整数的个数。此时，a ^ phi(n) == 1 mod n说的意思就是，以a为生成元生成的循环群的大小必定是phi(n)的约数，因为它是整个群的子群（拉格朗日定理），大小为这个元素的阶，必定是群的阶的因数，因此这样的mod乘方下来必定得到单位元1。关于以上提到的群和元素的阶，裴蜀定理，拉格朗日定理以及欧拉函数的一些性质的详细内容，以及依据这个性质设计的魔术，我们另外再找专门文章来讲，不再展开。
|
