费马小定理与欧拉定理详解

luyuanhong

费马小定理与欧拉定理详解

原创  software_math  计算机软件技术研究中心  2026 年 3 月 14 日 00:01  江西

费马小定理（Fermat's Little Theorem）和欧拉定理（Euler's Theorem）是初等数论中两个极其重要且密切相关的定理，它们主要描述了在模运算下幂的性质，常用于大整数模幂运算、素性测试、RSA 等场景。

1. 费马小定理（Fermat's Little Theorem）



2. 欧拉定理（Euler's Theorem）



3. 两者关系（最核心的一句话）



4. 快速对比表



5. 两个定理最经典的证明思路（乘法群角度）



6. 常见应用场景速览



计算机软件技术研究中心

ysr

两个定理都很重要，特别是欧拉原理，不仅仅可以用于RSA密码程序，还可以用于大素数的鉴定，是确定性的，原理成立的范围是11位以上的数，对于11位以下的数的素数检测可以用常规法。

ysr

170141183460469231731687303715884105729~170141183460469231731687303715884107729之间的素数有33个：（用时942.1406秒）
170141183460469231731687303715884105757  170141183460469231731687303715884105773  170141183460469231731687303715884105793  170141183460469231731687303715884105829  170141183460469231731687303715884105851  170141183460469231731687303715884105979  170141183460469231731687303715884106001  170141183460469231731687303715884106031  170141183460469231731687303715884106123  170141183460469231731687303715884106207
170141183460469231731687303715884106213  170141183460469231731687303715884106231  170141183460469231731687303715884106273  170141183460469231731687303715884106303  170141183460469231731687303715884106309  170141183460469231731687303715884106319  170141183460469231731687303715884106409  170141183460469231731687303715884106439  170141183460469231731687303715884106721  170141183460469231731687303715884106723
170141183460469231731687303715884106787  170141183460469231731687303715884107009  170141183460469231731687303715884107029  170141183460469231731687303715884107149  170141183460469231731687303715884107237  170141183460469231731687303715884107339  170141183460469231731687303715884107467  170141183460469231731687303715884107477  170141183460469231731687303715884107579  170141183460469231731687303715884107587
170141183460469231731687303715884107621  170141183460469231731687303715884107639  170141183460469231731687303715884107717

这是用我的判断程序找到的一组39位的大素数，原理就是用的欧拉原理，是确定性的，AI 说我的程序无法验证对不对，这不是胡说八道吗？
我已经用网上的判断分解软件验证了，这33个数都是素数，没有一个错误的！

ysr

其中的170141183460469231731687303715884106721  170141183460469231731687303715884106723，
是一对孪生素数

ysr

其中的170141183460469231731687303715884106439  170141183460469231731687303715884106721，是一对差为282的相邻素数对，好像是这33个素数中间距最大的一对相邻素数对了。

ysr

找到相邻素数的大间距有啥作用呢？其实有这样的作用：
如相邻素数p2-p1=282，理论上就可以在p2+2与2*p2+1之间找一组282项的等差数列，其中各项全部是素数，公差为2*3*5*…………*p，其中的p为282内的最大素数，不是说该数列各项全部在该区间中，而是仅仅首项在p2+2与2*p2+1之间而已。

ysr

欧拉定理和推论，统称为：欧拉原理。
RSA密码的原理就是利用的欧拉原理。

证明分三段：欧拉定理的证明，其推论的证明，RSA加解密过程的证明。（三个证明都是教科书上给出的，我只不过是择其简略的，复制黏贴，并整理在一起）

下面是欧拉定理的证明：
欧拉定理：a^φ(n)=1（mod n）
证明：
将1~n中与n互质的数按顺序排布：x1,x2……xφ(n) （显然，共有φ(n)个数）
我们考虑这么一些数：
m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)
数m1,m2,m3……mφ(n)（如果将其次序重新排列）必须相应地同余于x1,x2,x3……xφ(n).
故得出：m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)
或者为了方便：K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 （mod n），即a^[φ(n)]≡1 （mod n），得证。
当n为素数时就得到费马小定理：
费马小定理：对于质数p，任意整数a，均满足：a^p≡a（mod p）
而RSA密码的加解密过程不同于费马小定理。

欧拉定理的推论：
　　若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）
证明如下：（类似费马小定理的证明）
　　把目标式做一简单变形：a^(b - b mod φ（n）)* a^(b mod φ（n）)≡ a^(b mod φ（n）)（mod n），所以接下来只需要证明a^(b - b mod φ（n)）≡ 1 （mod n），又因为：（ b - b mod φ（n））| φ（n），不妨设：（ b - b mod φ（n））= q*φ（n）（q为自然数），则有a^(q*φ（n）)== （a^q）^φ（n），因为a，n互质，那么（a^q）与n也互质，那么就转换到了欧拉定理：（a^q）^φ（n）≡ 1 （mod n），成立。所以我们这个推论成立。b mod φ（n）是求模就是求余数的关系不是乘法，不等于b*φ（n），所以解释一下这一步：设b=q*φ(n)+r,其中0≤r<φ(n),即r=b mod φ(n).于是：
（ b - b mod φ（n））| φ（n），所以前面的成立。

RSA公钥密码解密过程的证明：
也就是证明下面的式子：c^d=m(mod n)。
因为根据加密规则：m^e=c(mod n)。
于是c可以写成：c=m^e-kn。
将c代入要我们证明的解密规则：（m^e-kn）^d=m（mod n）。
它等同于求证：m^（ed）=m（mod n）。
这个容易证明：
等式m^（ed）=m（mod n）可以用欧拉定理的推论简单证明的，证明如下：
证明：根据欧拉定理的推论，
若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）。
令b=ed，则m^(ed)=m^b，由于ed=1（mod φ（n）），所以m^(b mod φ（n）)=m （mod n）。
证毕！

当n为素数时照样成立，此时φ（n）=n-1.
所以，不同于费马小定理的，我们采用n为素数，当 φ（n）不等于n-1时，还原不回去明文m，就可以确定n为合数。
当n为素数时原理仍然成立，但此时n不用分解了，不安全了，但我们改变了其功能，不再是加密程序，而是用来判断n是否为素数。明文要小，位数要短，因为我们要判断的整数n是做除数的，除数比明文短余数就更短，还原不回去明文了，原理失效，如明文用123，则对11位以上的都有效，成立，低于11位的可以用常规法判断。我已经据此原理编成程序，用于快速判断大素数，是确定性的方法。

RSA公钥密码体制是上世纪70年代～80年代好像是，由3个数学家弄出来的，RSA分别是3位数学家的名字的开首字母。
这个原理就是前面证明过程中的恒等式：m^（ed）=m（mod n）。
数学家居然把它拆开成两个等式，两个过程，没有反例，不会出错。
比较这两个公式：a^p≡a（mod p）（费马小定理），m^（ed）=m（mod n）（欧拉原理）(其中ed=1（mod φ（n）），n为素数也成立)
显然二者不同，不能同日而语。

ysr

谁阻碍科学发展谁阻碍学术成果的发表，谁就是最大的汉奸王八蛋！