数论概论读书笔记 9.同余式、幂与费马小定理
同余式、幂与费马小定理
前面我们讨论了关于同余式、同余方程的一些性质
小结一下,互质这个条件我觉得很重要
①对于 如果 则可以消去c 得到
②对于同余方程 若 ,同余式恰好有一个解 (c=1,x即为a的模m下的数论逆元 。显然只有a,m互质时,a才有逆元)
之前我们研究的是两个数相乘取模后之间的性质,现在考虑另一个操作,即幂
取整数a,考虑它的幂 模m.
在这些幂中存在某种规律吗?我们先考虑m为素数的情况,这时往往能有更好的“模式”,这种现象在数论中(尤其在同余理论中)很普遍。(素数有个很好的性质是,与所有不是它倍数的数互质,这样子既有互质的性质,且模数又为素数) 而正如开始所示,在互质下,往往有很好的结论。
先对素数p=3,5,7 列出整数a=0,1,2,…和一些幂去模p 看来需要三个二维表,找一下“模式”
我们发现与 值均为1(a>0)
取更大的素数p=11发现 在a=1,2,3,4…,10时都是成立
由此可得到下述猜想
非要在这个区间吗?细想是不用的,只要不是p的倍数即可
这就是著名的费马小定理(1640年提出)
费马小定理描述了有关大数的一个令人惊讶的事实
定理9.1(费马小定理). 设p是素数,a是任意整数且 则
证明 (详细书本p44)
引理9.2. 设是素数,a是任何整数且 则数
与数
相同,尽管它们的次序不同。 引理9.2的证明再次用到素数整除性质 ,以及鸽巢原理。
证明:数列包含个数,显然没有一个数被整除 ,假设从中取出两个数ja和ka是关于p同余的,即 又p是素数且p不整除a,所以p整除 但是 所以 即
这表明,这p-1个数模p不同 由于任何数mod p仅有个不同的非零值,证毕。
利用该引理,即可完成对费马小定理的证明,可得到
由于与p互质(显然除了1没有其它公共因子了),可以消去它(开头有提到这个性质) 则
证毕。
使用费马小定理还可以进行素数测试。