- 这是一个关于初等数论的入门级别文章
- 适合中学数学水平的读者
- 主要内容:唯一分解定理,互质,最大公因数,最小公倍数,同余关系,同余类,完全剩余系,缩剩余系,欧拉函数,欧拉定理,费马小定理,中国剩余定理,逆元。
求正整数 的最后两位数
看到类似这样求一个数的某次方的最后几位数的问题,
没有接触过初等数论的同学可能第一反应是小学的做法:找规律。
可以看出来 的个位是 循环,循环周期是
而十位是 循环,循环周期是
所以 最后两位是
接触过一点初等数论的同学表示这种方法too young,因为这个问题可以用欧拉定理(Euler's theorm)秒杀。
如果正整数 和整数 互质,那么就有
其中欧拉函数 是「小于 的正整数中和 互质的数」的个数
因为
我们又知道 ,所以
利用好欧拉定理我们还可以解决很多类似的问题(部分选自Brilliant)
- 求 的最后两位数
- 求 除以 的余数
- 求 的最后三位数
- 有多少个正整数 使得 和 的个位数相同?
- 的奇数次方末尾总会出现其本身 , 等等。 以内有多少个正整数有这样的性质?
我们首先从初等数论最基本的几个概念说起
1.唯一质数分解定理(Unique factorisation theorm)
任何一个正整数 都可以唯一地分解为一组质数的乘积
其中 ,我们称这个分解为 的标准分解
2.互质(Coprime)、最大公因数(GCD)和最小公倍数(LCM)
对于整数 我们记 和 为 的最大公因数和最小公倍数,有时候我们会直接把他们简写为 和 。如果 ,我们称 互质,也就是说他们没有任何共同的质因数。
它有几个基本的性质,对于正整数
- 贝祖定理:总能找到整数 使得
2.同余关系(Congruence relations)
整数 和 除以 的余数相同,则称 模 同余,计作
如果对于整数 有
那么可以把他们相加或相减
也可以把他们相乘
通过这两条性质,我们容易知道,如果 那么
对于任意整系数多项式 都成立,这个结论很重要哦,经常会用
这里需要注意的一点是,如果整数 满足
那么只有当 互质时才可以把两边的 直接约掉,得到 ,更一般的
3.同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)
通过一个整数模 的余数,我们可以把所有整数分成 类,记
为模 余 的同余类(也叫剩余类)举个例子
是模 余 的同余类
从 中各挑出一个数就组成了一个模 的完全剩余系(完系)
其中
换言之, 个模 互相不同余的整数组成一个模 的完全剩余系。
我们称 为模 的最小非负完全剩余系(最小非负完系)。
取一个模 的完全剩余系 ,取出里面所有和 互质的数,这些数组成一个模 的缩剩余系(缩系),记为
其中 是序言里提到的欧拉函数,代表「小于 的正整数中和 互质的数」的个数。
注意,因为 ,每一个模 的缩剩余系有相同数量的元素(缩剩余系中的每一个数所属的同余类是确定的,所以总有确定的 个同余类)
如果缩剩余系 满足 ,那么称其为模 的最小正缩剩余系(最小正缩系)。
4.欧拉函数(Euler's totient function)
对于正整数 , 代表「小于 的正整数中和 互质的数」的个数,这个函数被称为欧拉函数;欧拉还告诉我们
其中 取到 的所有质因数
所以我们可以很方便的计算一个正整数欧拉函数的值,比如
欧拉函数还有一些非常有用的性质(跳过不影响下一部分的阅读)
- 如果正整数 那么 是偶数
- 如果 ,那么
- 对于正整数 有
- 对于正整数 有
- 特别地,如果 互质,那么
- 对于正整数 有
- 对于正整数 有
接下来我们进入正题:欧拉定理
如果正整数 和整数 互质,那么就有
其中 是欧拉函数
以下是证明
考虑模 的最小正缩系
已知 我们在 的每一个元素前面都乘一个
利用反证法可以证明 也是一个模 的缩系(其元素的同余类的顺序有可能会改变,但是这并没有任何影响),假设
其中 ,因为 互质可以将两边消去 ,那么就得到
这是不可能的,因为 中的元素互相模 不同余,矛盾啦!
接下来的思路就比较清晰了,因为 和 都是模 的缩系
显然 所以可以两边消去它
然后我们就证毕啦,是不是意外的简单?
另外,如果我们让 是一个质数,我们就可以从欧拉定理推出费马小定理(Fermat's little theorm)
如果 是质数,那么 对于任意整数 都成立
当然,费马小定理也可以用归纳法证明,假设 ,那么
当 时,二项式系数 的分子中有 ,分母中每一个乘子都不能整除 (因为 是质数),所以 能够整除 ,进而得到 。当 时显然成立,所以定理成立。
接下来我们看看如何证明
首先考虑 ,其中 是质数, 是非负整数
如果要使 ,只能让 等于 的倍数
在 范围内, 的倍数有 总共 个,所以
然后我们证明对于 有 ,我们首先构造两个集合,第一个集合是模 的最小正缩系 ,第二个集合定义为
其中 分别是模 的最小正缩系,显然 和
如果我们证明存在一个双射 ,就证明了
我们让
首先我们用反证法证明 是单射,假设 满足 且 那么
显然因为 我们能得出 ,这与我们的假设矛盾(因为 是模 的缩系, 是 的两个不同的元素,所以他们模 不同余)。接下来,中国剩余定理告诉我们
如果整数 和正整数 ,同余方程组
在 范围内有且只有一个解
通过中国剩余定理我们能够证明 是满射,所以 是双射。
所以对于 就有 ,假设 的标准分解为
其中 ,那么
证毕
序言中题目的解答
求 的最后两位数
正确答案是
因为 和 不互质,我们把它拆成
注意到
再拆一次
这里取 因为要保证它能被 整除,接着
因为 能被 整除,所以最后两位是
求 除以 的余数
正确答案是
因为 ,我们只需分别找出这个数模 的余数
因为
因为
因为
可以列出同余方程组
由中国剩余定理,我们解得
求 的最后三位数
正确答案是
因为
从 我们能够得到
因为 以及 且
所以
最后开几个坑
- Part 2 介绍一下Wilson定理,中国剩余定理,欧几里得算法(即辗转相除法)和其扩展
- Part 3 待定,以后有时间就更
来源:知乎 www.zhihu.com
作者:Daniel Xiang
【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。 点击下载