数论概论读书笔记 9.同余式、幂与费马小定理

同余式、幂与费马小定理

前面我们讨论了关于同余式、同余方程的一些性质

小结一下，互质这个条件我觉得很重要

①对于ac≡bc(mod m)$ac\equiv bc(modm)$ 如果gcd(c,m)=1$gcd(c,m)=1$ 则可以消去c 得到a≡b(mod m)$a\equiv b(modm)$

②对于同余方程 ax≡c(mod m)$ax\equiv c(modm)$ 若gcd(a,m)=1$gcd(a,m)=1$ ，同余式恰好有一个解 （c=1,x即为a的模m下的数论逆元 。显然只有a,m互质时，a才有逆元）

之前我们研究的是两个数相乘取模后之间的性质，现在考虑另一个操作，即幂

取整数a,考虑它的幂a,a2,a3,...,$a,a^2,a^3,...,$ 模m.

在这些幂中存在某种规律吗？我们先考虑m为素数的情况，这时往往能有更好的“模式”，这种现象在数论中（尤其在同余理论中）很普遍。（素数有个很好的性质是，与所有不是它倍数的数互质,这样子既有互质的性质，且模数又为素数） 而正如开始所示，在互质下，往往有很好的结论。

先对素数p=3,5,7 列出整数a=0,1,2,…和一些幂去模p 看来需要三个二维表，找一下“模式”

我们发现a2(mod 3)a4(mod 5)$a^2(mod3)a^4(mod5)$与 a6(mod 7)$a^6(mod7)$ 值均为1（a>0)

取更大的素数p=11发现 a10≡1(mod 11)$a^{10}\equiv 1(mod11)$ 在a=1,2,3,4…,10时都是成立

由此可得到下述猜想

非要在这个区间吗？细想是不用的，只要a$a$不是p的倍数即可

这就是著名的费马小定理（1640年提出）

费马小定理描述了有关大数的一个令人惊讶的事实

定理9.1（费马小定理）. 设p是素数，a是任意整数且p∤a$p\nmid a$ 则 ap−1≡1(mod p)$a^{p-1}\equiv 1(modp)$

证明 （详细书本p44）

引理9.2. 设p$p$是素数，a是任何整数且 p∤a$p\nmid a$ 则数

与数

相同，尽管它们的次序不同。 引理9.2的证明再次用到素数整除性质 ，以及鸽巢原理。

证明：数列a,2a,3a,...,(p−1)a$a,2a,3a,...,(p-1)a$包含p−1$p-1$个数，显然没有一个数被p$p$整除 ，假设从中取出两个数ja和ka是关于p同余的，即p|(j−k)a$p|(j-k)a$ 又p是素数且p不整除a，所以p整除(j−k)$(j-k)$ 但是|j−k|<p−1$|j-k|<p-1$ 所以j−k=0$j-k=0$ 即j=k$j=k$

这表明，这p-1个数模p不同 由于任何数mod p仅有p−1$p-1$个不同的非零值，证毕。

利用该引理，即可完成对费马小定理的证明，可得到

由于(p−1)!$(p-1)!$与p互质（显然除了1没有其它公共因子了），可以消去它（开头有提到这个性质） 则ap−1≡1(mod p)$a^{p-1}\equiv 1(modp)$

证毕。

使用费马小定理还可以进行素数测试。