黄博士网: 在线数学手册软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 关于 | 科学 | 数学 | 手册 | 软件 | 计算器 | 电化学 | 虚拟实验室 | 帮助 | 论坛 | 联系 | English

欧拉定理与费马定理

欧拉定理

若\( \left( {k,m} \right) = 1 \),则\[ k^{\phi \left( m \right)} \equiv 1\left( {\bmod m} \right) \] 式中\[ \phi \left( m \right) \] 为欧拉函数.

费马小定理

p为素数,则对所有整数a,有 \[ a^p \equiv a\left( {\bmod p} \right) \] 也可写作: \[ a^{p - 1} \equiv 1\left( {\bmod p} \right) \] 显然费马定理是欧拉定理的特例.

欧拉定理证明(费马小定理证明)

设\( a_1 ,a_2 , \cdots a_{\phi \left( m \right)} \)构成m的一缩剩余系,若\( \left( {k,m} \right) = 1 \),则\[ ka_1 ,ka_2 , \cdots ka_{\phi \left( m \right)} \]这\( \phi \left( m \right) \)个数都与m互素,对于其中任意两个\( ka_i \)和\( ka_j \),这两个数的差为\( k\left( {a_i - a_j } \right) \),显然这个数不能被m整除,所以\( ka_i \)和\( ka_j \)对m不同余,因此\( ka_1 ,ka_2 , \cdots ka_{\phi \left( m \right)} \)构成一缩剩余系.因此有 \[ a_1 a_2 \cdots a_{\phi \left( m \right)} \equiv ka_1 ka_2 \cdots ka_{\phi \left( m \right)} \equiv k^{\phi \left( m \right)} a_1 a_2 \cdots a_{\phi \left( m \right)} \left( {\bmod m} \right) \] 再由同余性质5°,得到\[ k^{\phi \left( m \right)} \equiv 1\left( {\bmod m} \right) \]




参阅


Copyright 2000-2017 DrHuang.com