高中生解题中素数的数学证明

费马理论

a是整数，p是质数，那么

a^p==a(mod山口

如果p|a，原公式显然成立。

如果p不能被a整除，即(a，p)=1。

然后，1a，2a，...(p-1)a不能被p整除。

和1a，2a的余数，...(p-1)a除以P不等于。

这一步表明了归谬法:如果有整数C和D，而1

因此，1a，2a的余数，...(p-1)a除以P不等于。

但是，除以P最多只有(p-1)个余数。根据鸽子洞原理，1a，2a，...(p-1)a除以P正好是1，2的某种排列，...(p-1)。

根据同余的定义

必须有1 * 2 * 3 *...* (P-1) = = 1A * 2A * 3A...(P-1) A (mod P)

设w=(p-1)！

W = = w * a (p-1) (mod p)

因为w不能被p整除，所以a (p-1) = = 1 (mod p)。

即a p = = a (mod p)