费马小定理, 英語, fermat, little, theorem, 是数论中的一个定理, 假如a, displaystyle, 是一个整数, displaystyle, 是一个質数, 那么a, displaystyle, 是p, displaystyle, 的倍数, 可以表示为, displaystyle, equiv, pmod, 如果a, displaystyle, 不是p, displaystyle, 的倍数, 这个定理也可以写成更加常用的一种形式, displaystyle, equiv, pmod, . 费马小定理 英語 Fermat s little theorem 是数论中的一个定理 假如a displaystyle a 是一个整数 p displaystyle p 是一个質数 那么a p a displaystyle a p a 是p displaystyle p 的倍数 可以表示为 a p a mod p displaystyle a p equiv a pmod p 如果a displaystyle a 不是p displaystyle p 的倍数 这个定理也可以写成更加常用的一种形式 a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p 1 註 1 費馬小定理的逆敘述不成立 即假如a p a displaystyle a p a 是p displaystyle p 的倍数 p displaystyle p 不一定是一个質数 例如2 341 2 displaystyle 2 341 2 是341 displaystyle 341 的倍数 但341 11 31 displaystyle 341 11 times 31 不是質数 滿足費馬小定理的合數被稱為费马伪素数 目录 1 历史 1 1 卡邁克爾數 2 证明 2 1 方法一 2 2 方法二 2 3 方法三 3 應用 4 推广 4 1 欧拉定理 4 2 卡邁克爾函數 4 3 多项式除法 5 注释 6 参见 7 參考历史 编辑 皮埃爾 德 費馬 皮埃爾 德 費馬于1636年发现了这个定理 在一封1640年10月18日的信中他第一次使用了上面的书写方式 在他的信中费马还提出a是一个素数的要求 1736年 歐拉出版了一本名為 一些與素數有關的定理的證明 拉丁文 Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio 2 的論文集 其中第一次给出了證明 但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明 有些數學家獨立提出相關的假說 有時也被錯誤地稱為中國猜想 當2 p 2 mod p displaystyle 2 p equiv 2 pmod p 成立時 p是質數 這是費馬小定理的一個特殊情況 然而 這一假說的前設是錯的 例如 2 341 2 mod 341 displaystyle 2 341 equiv 2 pmod 341 而341 11 31是一個偽素數 所有的偽素數都是此假說的反例 卡邁克爾數 编辑 主条目 卡邁克爾數 如上所述 中國猜想仅有一半是正确的 符合中國猜想但不是素数的数被称为伪素数 更极端的反例是卡迈克尔数 假設a displaystyle a 與561互质 則a 560 displaystyle a 560 被561除都余1 这样的数被称为卡邁克爾數 561是最小的卡邁克爾数 Korselt在1899年就给出了卡邁克爾數的等价定义 但直到1910年才由卡邁克爾 Robert Daniel Carmichael 发现第一个卡邁克爾数 561 1994年William Alford Andrew Granville及Carl Pomerance证明了卡邁克爾数有无穷多个 证明 编辑方法一 编辑 i 若a displaystyle a 是整数 p displaystyle p 是质数 且gcd a p 1 displaystyle gcd a p 1 若p displaystyle p 不能整除x y displaystyle x y 则p displaystyle p 不能整除a x y displaystyle a x y 取整數集A displaystyle A 为所有小於p displaystyle p 的正整数集合 A displaystyle A 构成p displaystyle p 的完全剩余系 即A displaystyle A 中不存在两个数同余p displaystyle p B displaystyle B 是A displaystyle A 中所有的元素乘以a displaystyle a 组成的集合 因为A displaystyle A 中的任何两个元素之差都不能被p displaystyle p 整除 所以B displaystyle B 中的任何两个元素之差也不能被p displaystyle p 整除 換句話說 gcd a p 1 displaystyle gcd a p 1 考慮1 a 2 a 3 a p 1 a displaystyle 1 times a 2 times a 3 times a p 1 times a 共 p 1 displaystyle p 1 個數 將它們分別除以p displaystyle p 餘數分別為r 1 r 2 r 3 r p 1 displaystyle r 1 r 2 r 3 r p 1 則集合 r 1 r 2 r 3 r p 1 displaystyle r 1 r 2 r 3 r p 1 為集合 1 2 3 p 1 displaystyle 1 2 3 ldots p 1 的重新排列 即1 2 3 p 1 displaystyle 1 2 3 ldots p 1 在餘數中恰好各出現一次 這是因為對於任兩個相異k a displaystyle k a 而言 k 1 2 3 p 1 displaystyle k 1 2 3 ldots p 1 其差不是p displaystyle p 的倍數 所以不會有相同餘數 且任一個k a displaystyle k a 亦不為p displaystyle p 的倍數 所以餘數不為0 因此 1 2 3 p 1 1 a 2 a p 1 a mod p displaystyle 1 cdot 2 cdot 3 cdot dots cdot p 1 equiv 1 cdot a cdot 2 cdot a cdot dots cdot p 1 cdot a pmod p 即 W W a p 1 mod p displaystyle W equiv W cdot a p 1 pmod p 在这里W 1 2 3 p 1 displaystyle W 1 cdot 2 cdot 3 cdot ldots cdot p 1 且 W p 1 displaystyle W p 1 因此将整个公式除以W displaystyle W 即得到 a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p 3 也即 a p a mod p displaystyle a p equiv a pmod p ii 若p displaystyle p 整除a displaystyle a 则显然有p displaystyle p 整除a p displaystyle a p 即a p a 0 mod p displaystyle a p equiv a equiv 0 pmod p 方法二 编辑 参见 中一新生之夢 若p displaystyle p 为质数 n displaystyle n 为整数 且p n displaystyle p geq n 考慮二項式係數 p n p n p n displaystyle tbinom p n tfrac p n p n 並限定n displaystyle n 不為p displaystyle p 或0 displaystyle 0 則由於分子有質數p displaystyle p 但分母不含p displaystyle p 故分子的p displaystyle p 能保留 不被約分而除去 即 p n displaystyle tbinom p n 恆為p displaystyle p 的倍數 4 再考慮 b 1 p displaystyle b 1 p 的二項式展開 模p displaystyle p 則 b 1 p p p b p p p 1 b p 1 p p 2 b p 2 p 2 b 2 p 1 b 1 p 0 b 0 mod p displaystyle b 1 p equiv dbinom p p b p dbinom p p 1 b p 1 dbinom p p 2 b p 2 dots dbinom p 2 b 2 dbinom p 1 b 1 dbinom p 0 b 0 pmod p p p b p p 0 b 0 mod p displaystyle equiv dbinom p p b p dbinom p 0 b 0 pmod p b p 1 mod p displaystyle equiv b p 1 pmod p 因此 b 1 p b p 1 mod p displaystyle b 1 p equiv b p 1 pmod p b 1 p 1 1 mod p displaystyle equiv b 1 p 1 1 pmod p b 2 p 1 1 1 mod p displaystyle equiv b 2 p 1 1 1 pmod p b 3 p 1 1 1 1 mod p displaystyle equiv b 3 p 1 1 1 1 pmod p displaystyle dots 1 1 1 1 b 1 mod p displaystyle equiv begin matrix underbrace 1 1 dots 1 1 b 1 end matrix pmod p b 1 mod p displaystyle equiv b 1 pmod p 令a b 1 displaystyle a b 1 即得a p a mod p displaystyle a p equiv a pmod p 3 方法三 编辑 在抽象代数教科书中 费马小定理常作为教授拉格朗日定理时的一个简单例子 5 显然只需考虑 a p 1 displaystyle a p 1 情形 此时模 p displaystyle p 所有非零的余数 在同余意义下对乘法构成一个群 这个群的阶是 p 1 displaystyle p 1 考虑群中的任何一个元素 b displaystyle b 根据拉格朗日定理 b displaystyle b 的阶必整除群的阶 证毕 應用 编辑計算2 100 displaystyle 2 100 除以13的餘數2 100 2 12 8 4 mod 13 displaystyle 2 100 equiv 2 12 times 8 4 pmod 13 2 12 8 2 4 mod 13 displaystyle equiv 2 12 8 cdot 2 4 pmod 13 1 8 16 mod 13 displaystyle equiv 1 8 cdot 16 pmod 13 16 mod 13 displaystyle equiv 16 pmod 13 3 mod 13 displaystyle equiv 3 pmod 13 故餘數為3 證明對於任意整數a而言 a 13 a displaystyle a 13 a 恆為2730的倍數 易由a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p 推得a n p 1 1 1 n a a mod p displaystyle a n p 1 1 equiv 1 n cdot a equiv a pmod p 其中n displaystyle n 為正整數 故對指數13操作如下 13減1為12 12的正因數有1 2 3 4 6 12 分別加1 為2 3 4 5 7 13 其中2 3 5 7 13為質數 根據定理的延伸表達式 a 13 a displaystyle a 13 a 為2的倍數 為3的倍數 為5的倍數 為7的倍數 為13的倍數 即2 3 5 7 13 2730的倍數 推广 编辑欧拉定理 编辑 费马小定理是欧拉定理的一个特殊情况 如果 a n 1 displaystyle a n 1 那么 a f n 1 mod n displaystyle a varphi n equiv 1 pmod n 这里 f n displaystyle varphi n 是欧拉函数 欧拉函数的值是所有小于或等于 n displaystyle n 的正整数中与 n displaystyle n 互質的数的个数 假如 n displaystyle n 是一个素数 则 f n n 1 displaystyle varphi n n 1 即费马小定理 证明上面证明费马小定理的群论方法 可以同理地证明欧拉定理 考虑所有与 n displaystyle n 互素的数 这些数模 n displaystyle n 的余数所构成的集合 记为 S displaystyle cal S 并将群乘法定义为相乘后模 n displaystyle n 的同余 显然 S displaystyle cal S 是一个群 因为它对群乘法封闭 若 a n 1 displaystyle a n 1 和 b n 1 displaystyle b n 1 则 a b n 1 displaystyle ab n 1 含幺元 即 1 且任何一个元素 a displaystyle a 的逆元素也在集合中 因为若 a S displaystyle a in cal S 则由群乘法封闭性任何a displaystyle a 的幂次都在 S displaystyle cal S 中 所以 a displaystyle langle a rangle 是 S displaystyle cal S 这个有限集的子集 根据定义 S displaystyle cal S 的阶是 f n displaystyle varphi n 于是根据拉格朗日定理 S displaystyle cal S 中任何一个元素的阶必整除 f n displaystyle varphi n 证毕 卡邁克爾函數 编辑 主条目 卡邁克爾函數 卡邁克爾函數比欧拉函数更小 费马小定理也是它的特殊情况 a l n 1 mod n displaystyle a lambda n equiv 1 pmod n 多项式除法 编辑 因為p x p x p k x p x k displaystyle p x p x Rightarrow p k x p x k 所以由x N mod x p x k displaystyle x N pmod x p x k 的結果可以得出x N mod p k displaystyle x N pmod p k 的結果用多項式除法可以得出x N displaystyle x N 除以 x p x k displaystyle x p x k 的次數少於p k displaystyle p k 的餘式例如3 x 3 x displaystyle 3 mid x 3 x 由多項式除法得到x 5 x 2 1 x 3 x x displaystyle x 5 x 2 1 x 3 x x 則x 5 x mod 3 displaystyle x 5 equiv x pmod 3 這個餘式的一般結果是 x p k i 1 k 1 i 1 k i x p k p 1 i mod p k displaystyle displaystyle x pk equiv sum i 1 k 1 i 1 binom k i x pk p 1 i pmod p k 除式 x p k p 1 n i 1 k 1 i 1 n i 1 i 1 n k k i x p k p 1 i mod p k displaystyle displaystyle x pk p 1 n equiv sum i 1 k 1 i 1 binom n i 1 i 1 binom n k k i x pk p 1 i pmod p k n 0时为除式 用数学归纳法证明余式 6 求x 1000 mod 5 2 displaystyle x 1000 pmod 5 2 x 10 4 n n 2 x 6 n 1 x 2 mod 5 2 displaystyle x 10 4n equiv n 2 x 6 n 1 x 2 pmod 5 2 x 1000 249 x 8 248 x 4 24 x 8 23 x 4 mod 5 2 displaystyle x 1000 equiv 249x 8 248x 4 equiv 24x 8 23x 4 pmod 5 2 注释 编辑 符号的应用请参见同餘和模算数 参见 编辑费马大定理 拉格朗日定理參考 编辑 Fermat s Little Theorem 页面存档备份 存于互联网档案馆 WolframMathWorld 英文 A proof of certain theorems regarding prime numbers 2012 12 11 原始内容存档于2015 06 16 3 0 3 1 許介彥 費馬小定理 PDF 科學教育月刊 私立大葉大學電機工程學系 2006年10月 第293期 37 44 2015 04 18 原始内容 PDF 存档于2015 04 18 How is x y p x p y p mod p for any prime number p Mathematics Stack Exchange 2018 09 27 2021 04 26 原始内容存档于2022 03 25 英语 聂灵沼 丁石孙 代数学引论 第二版 北京 高等教育出版社 2000 第33页 ISBN 7 04 008893 2 使用 accessdate 需要含有 url 帮助 黄嘉威 多项式除法解高次同余 数学学习与研究 2015 9 第104页 2015 07 19 原始内容存档于2020 10 20 取自 https zh wikipedia org w index php title 费马小定理 amp oldid 75763553, 维基百科,wiki,书籍,书籍,图书馆,