大家好，欢迎来到IT知识分享网。
费马小定理
问题：
对 ∀ ( a , p ) = 1 ， p 是 质 数 ∃ a p − 1 ≡ 1 ( m o d p ) 对\forall(a,p)=1，p是质数\\ \exists~a^{p-1}\equiv1(mod~p)\\ 对∀(a,p)=1，p是质数∃ ap−1≡1(mod p)
证明
先来第一个引理：
如 果 ( c , m ) = 1 , a c ≡ b c ( m o d m ) 则 a ≡ b ( m o d m ) 如果(c,m)=1, ac\equiv bc(mod~m)\\ 则a\equiv b(mod~m)\\ 如果(c,m)=1,ac≡bc(mod m)则a≡b(mod m)
证明：
∵ a c ≡ b c ( m o d m ) ∴ a c − b c ≡ 0 ( m o d m ) ∴ ( a − b ) c ≡ 0 ( m o d m ) ∵ ( c , m ) = 1 ∴ c 在 模 m 下 存 在 逆 元 c − 1 ∴ ( a − b ) c c − 1 = 0 ( m o d m ) ∴ a − b ≡ 0 ( m o d m ) ∴ a ≡ b ( m o d m ) \because ac\equiv bc(mod~m)\\ \therefore ac-bc\equiv0(mod~m)\\ \therefore(a-b)c\equiv0(mod~m)\\ \because (c,m)=1\\ \therefore c在模m下存在逆元c^{-1}\\ \therefore (a-b)cc^{-1}=0(mod~m)\\ \therefore a-b\equiv0(mod~m)\\ \therefore a\equiv b(mod~m)\\ ∵ac≡bc(mod m)∴ac−bc≡0(mod m)∴(a−b)c≡0(mod m)∵(c,m)=1∴c在模m下存在逆元c−1∴(a−b)cc−1=0(mod m)∴a−b≡0(mod m)∴a≡b(mod m)
再来第二个引理：
给 定 一 个 数 m ， 和 对 应 的 一 个 完 全 剩 余 系 { a 1 , a 2 , a 3 . . . , a m − 1 } ∀ ( c , m ) = 1 , { a 1 c , a 2 c , a 3 c , a p − 1 c } 在 模 m 下 也 是 一 个 完 全 剩 余 系 给定一个数m，和对应的一个完全剩余系\{a_1,a_2,a_3…,a_{m-1}\}\\ \forall(c,m)=1,\{a_1c,a_2c,a_3c,a_{p-1}c\}在模m下也是一个完全剩余系\\ 给定一个数m，和对应的一个完全剩余系{
a1,a2,a3...,am−1}∀(c,m)=1,{
a1c,a2c,a3c,ap−1c}在模m下也是一个完全剩余系
证明：
假 设 在 { a 1 c , a 2 c , a 3 c , a p − 1 c } 中 , ∃ a i c ≡ a j c ( m o d m ) ( i ≠ j ) 则 根 据 引 理 1 ， 可 知 a i ≡ a j ( m o d m ) 与 条 件 中 的 a i , a j 是 属 于 一 个 完 全 剩 余 系 下 矛 盾 ， 所 以 假 设 不 成 立 得 证 ： { a 1 c , a 2 c , a 3 c , a p − 1 c } 的 每 一 个 值 在 模 m 下 都 不 相 等 根 据 抽 屉 原 理 可 知 { a 1 c , a 2 c , a 3 c , a p − 1 c } 也 是 一 个 完 全 剩 余 系 。 假设在\{a_1c,a_2c,a_3c,a_{p-1}c\}中,\exists a_ic\equiv a_jc(mod~m)(i\neq j)\\ 则根据引理1，可知a_i\equiv a_j(mod~m)\\ 与条件中的a_i,a_j是属于一个完全剩余系下矛盾，所以假设不成立\\ 得证：\{a_1c,a_2c,a_3c,a_{p-1}c\}的每一个值在模m下都不相等\\ 根据抽屉原理可知\{a_1c,a_2c,a_3c,a_{p-1}c\}也是一个完全剩余系。 假设在{
a1c,a2c,a3c,ap−1c}中,∃aic≡ajc(mod m)(i=j)则根据引理1，可知ai≡aj(mod m)与条件中的ai,aj是属于一个完全剩余系下矛盾，所以假设不成立得证：{
a1c,a2c,a3c,ap−1c}的每一个值在模m下都不相等根据抽屉原理可知{
a1c,a2c,a3c,ap−1c}也是一个完全剩余系。
接下来就是证明费马小定理了：
对 于 一 个 素 数 p ， 我 们 先 构 造 一 个 模 p 的 完 全 剩 余 系 { 0 , 1 , 2 , 3 , . . . , p − 1 } 。 对 于 ∀ a , 满 足 ( a , p ) = 1 ， 则 { 0 , a , 2 a , 3 a , . . . , ( p − 1 ) a } 也 是 一 个 完 全 剩 余 系 ∴ 1 × 2 × 3… × ( p − 1 ) ≡ a × 2 a × 3 a . . . × ( p − 1 ) a ( m o d p ) ( p − 1 ) ! ≡ a p − 1 ( p − 1 ) ! ( m o d p ) ∵ ( ( p − 1 ) ! , p ) = 1 ， 引 理 1 ∴ a p − 1 = 1 ( m o d p ) 对于一个素数p，我们先构造一个模p的完全剩余系\{0, 1,2,3,…,p-1\}。\\ 对于\forall a,满足(a,p)=1，则\{0, a,2a,3a,…,(p-1)a\}也是一个完全剩余系\\ \therefore 1\times2\times3…\times(p-1)\equiv a\times2a\times3a…\times(p-1)a(mod~p)\\ (p-1)!\equiv a^{p-1}(p-1)!(mod~p)\\ \because ((p-1)!,p)=1， 引理1\\ \therefore a^{p-1}=1(mod~p)\\ 对于一个素数p，我们先构造一个模p的完全剩余系{
0,1,2,3,...,p−1}。对于∀a,满足(a,p)=1，则{
0,a,2a,3a,...,(p−1)a}也是一个完全剩余系∴1×2×3...×(p−1)≡a×2a×3a...×(p−1)a(mod p)(p−1)!≡ap−1(p−1)!(mod p)∵((p−1)!,p)=1，引理1∴ap−1=1(mod p)
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/145866.html
