同余： 两个整数 a , b a,b a,b，若它们除以整数 m m m所得的余数相等，则称 a a a同余于 b b b模 m m m。
记作： a ≡ b ( m o d ?? m ) a≡b (\mod m) a≡b(modm)
欧拉定理： 如果 n n n和 a a a互质，则有
a φ ( n ) ≡ 1 ( m o d ?? n ) a^{\varphi(n)}\equiv 1(\mod n) aφ(n)≡1(modn)
证明：
在 1 ～ n 1\sim n 1～n中，所有与 n n n互质的数为
a 1 , a 2 , . . . , a φ ( n ) ? ? ? ? ? ① a_1,a_2,...,a_{\varphi(n)}·····① a1?,a2?,...,aφ(n)??????①
∵ ∵ ∵ a a a与 n n n互质
∴ a ? a 1 , a ? a 2 , . . . , a ? a φ ( n ) 均 与 n 互 质 ? ? ? ? ? ② ∴a*a_1,a*a_2,...,a*a_{\varphi(n)}均与n互质·····② ∴a?a1?,a?a2?,...,a?aφ(n)?均与n互质?????②
① ① ①式与 ② ② ②式 % n \%n %n相同，顺序可能不同。
证明：
【欧拉定理与费马小定理】假设 a ? a i ≡ a ? a j ( m o d ?? n ) , i ≠ j a*a_i\equiv a*a_j(\mod n),i≠j a?ai?≡a?aj?(modn),i?=j
消去 a a a,得
a i ≡ a j ( m o d ?? n ) , 与 ① 矛 盾 a_i\equiv a_j(\mod n),与①矛盾 ai?≡aj?(modn),与①矛盾
证毕。
令 ① ① ①的所有数乘积 = ② =② =②的所有数乘积：
a 1 ? a 2 ? ? ? a φ ( n ) = a φ ( n ) ? a 1 ? a 2 ? ? ? a φ ( n ) ( m o d ?? n ) a_1·a_2···a_{\varphi(n)}=a^{\varphi(n)}·a_1·a_2···a_{\varphi(n)}(\mod n) a1??a2????aφ(n)?=aφ(n)?a1??a2????aφ(n)?(modn)
消去 a 1 ? a 2 ? ? ? a φ ( n ) a_1·a_2···a_{\varphi(n)} a1??a2????aφ(n)?得
a φ ( n ) ≡ 1 ( m o d ?? n ) a^{\varphi(n)}\equiv 1(\mod n) aφ(n)≡1(modn)
证毕。
费马小定理： 在欧拉定理中，若 n n n为质数 p p p,即
a φ ( p ) ≡ 1 ( m o d ?? p ) a^{\varphi(p)}\equiv 1(\mod p) aφ(p)≡1(modp)
∵ φ ( p ) = p ? 1 ∵\varphi(p)=p-1 ∵φ(p)=p?1
∴ a p ? 1 ≡ 1 ( m o d ?? p ) ∴a^{p-1}\equiv 1(\mod p) ∴ap?1≡1(modp)
推荐阅读
- 深度学习|正则化方法笔记
- kmeans|【ML31】Advanced K-means clustering algorithm
- 概率论|#统计学相关,Z分布,推断性统计
- yxc|AcWing 寒假每日一题 2021-01-19 找硬币
- 面试|面经自己汇总（三维视觉算法&机器学习&深度学习）——持续更新
- 数学建模与Matlab|层次分析法及matlab代码
- #|Python剑指offer打卡-4
- #|机器学习入门三
- #|【Task12】LeetCode腾讯精选打卡