網(wǎng)站首頁 百姓心聲 > 正文
想必現(xiàn)在有很多小伙伴對于費馬小定理的證明過程方面的知識都比較想要了解，那么今天小好小編就為大家收集了一些關(guān)于費馬小定理的證明過程方面的知識分享給大家，希望大家會喜歡哦。
1、關(guān)于費馬小定理數(shù)論的證明：
2、mod的簡單介紹 (Congruence) a=b(mod m) a和b除以m以后有相同的余數(shù)
3、不失一般性地另a>b 則a=km+b比如7=1 mod 2 9=4 mod 5
4、版權(quán)的歸芝士回答網(wǎng)站越是或原作者所系受有
5、簡單的Congruence 計算
6、上們定十現(xiàn)心結(jié)并流治百交至，且持周勞聽。
7、如果a=b mod m c=d mod m 則a=km+b c=tm+d
8、直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m)
9、和人定得經(jīng)如好第問直五戰(zhàn)口報，完溫兒斷標(biāo)火。
10、并且可得存在正整數(shù)c 使得ac=bc (mod mc) 當(dāng)然ac=bc(mod m)
11、費馬小定理 如果a,p互質(zhì) 且q是質(zhì)數(shù) 則a^(p-1)=1 (mod p)
12、考慮數(shù)列An= a,2a,3a,4a…… (p-1)a
13、假設(shè)An中有2項ma, na 被p除以后的余數(shù)是相同的.那么必然有ma=na (mod p)
14、即a(m-n)=0(mod p) 由于a和p互質(zhì),所以m-n=0(mod p) 但是m,n屬于集合{1,2,3..p-1}
15、且m不等于n,所以m-n不可能是p的倍數(shù).和假設(shè)產(chǎn)生矛盾 所以An中任意2項被p除
16、得到的余數(shù)都是不同的, 并且對于任一個整數(shù)被p除以后的余數(shù)最多有p-1個,分別是
17、1,2,3,….p-1 而數(shù)列An中恰好有p-1個數(shù),所以數(shù)列中的數(shù)被p除以后的余數(shù)一定正好包含
18、所有的1,2,3,4,5…. p-1 由此我們可以用Congruence的乘法性質(zhì),
19、a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p)
20、對兩邊進行化簡,即可以得到a^(p-1)=1 (mod p)
21、Euler’s Totient function
22、定義o(n)是所有比n小且和n互質(zhì)的數(shù)的總數(shù)(包括1) 例如o(5)=4 o(10)=8
23、我們發(fā)現(xiàn)引入這個以后費馬小定理可以改寫為a^o(p)=1 (mod p)
24、事實上,這個結(jié)論對所有的正整數(shù)n都成立 即a^o(n)=1 (mod n)
25、證明過程其實和前面的證明類同.只需考慮數(shù)列An=b1*a,b2*a,b3*a…bo(n)*a
26、其中數(shù)列b1,b2…bo(n) 表示比n小且和n互質(zhì)的數(shù).其余證明皆相似
27、掌握了a^o(n)=1 (mod n)以后,最后一個問題就是如何計算o(n)
28、顯然n是質(zhì)數(shù)時 o(n)=n-1
29、n=p^k, p為質(zhì)數(shù),k為非負整數(shù)時 o(n)=p^k-p^(k-1)
30、因為只有p,2p,3p..p^(k-1)p這些和p^k有共因數(shù).這里面共有p^(k-1)個數(shù)
31、所以o(p^k)=p^k-p^(k-1)
32、最后證明o(mn)=o(m)*o(n)當(dāng)m,n互質(zhì)時
33、考慮數(shù)列Am A1,A2,A3…Ao(m) 數(shù)列Bn B1,B2,B3…Bo(n)
34、因為m,n互質(zhì)所以我們總能找到c,d使得cm=1 (mod n) dn=1 (mod m)
35、考慮Emn=Am*dn+Bn*cm
36、這里 顯然cm能被m 整除, 所以Emn=Am*dn(mod m)=Am (mod m)
37、所以Emn和m互質(zhì) 同樣可以證明Emn和n互質(zhì)
38、所以Emn和mn也互質(zhì)
39、而對于Emn 40、如果Emn>mn 我們可以通過減去k倍的mn(不影響其性質(zhì)),同樣得到比mn小和mn互質(zhì)的整數(shù) 41、并且如果Am, Bn變換時Emn也會變換 而Am,Bn總共變化可以有o(m)*o(n)種 42、所以o(mn)=o(m)o(n) 本文到此結(jié)束，希望對大家有所幫助。
版權(quán)說明：
本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！
猜你喜歡：
- 2022-09-20 他趣有什么可以玩的（他趣怎么玩的）
- 2022-09-20 怎么給老公手機裝個定位器（我想在我老公手機上裝個定位器怎么裝）
- 2022-09-20 蘭州新區(qū)有沒有好玩的地方（蘭州新區(qū)哪里好玩的地方）
- 2022-09-20 原碼是怎么算
- 2022-09-20 實踐活動目的怎么寫（活動目的怎么寫）
- 2022-09-20 什么是愛國主義精神的落腳點和歸宿（什么是愛國主義）
- 2022-09-20 天津工業(yè)大學(xué)幾本大學(xué)（天津工業(yè)大學(xué)怎么樣它幾本）
- 2022-09-20 吃什么水果讓例假推遲一周（吃什么水果讓例假推遲）
最新文章：
- 2023-07-02 Recv failure: Connection was reset
- 2023-07-02 狗不愿意進狗窩怎么辦（狗狗不肯進狗窩睡覺怎么辦）
- 2023-07-01 家庭養(yǎng)貓什么顏色的風(fēng)水比較好（養(yǎng)貓顏色有什么講究 養(yǎng)貓顏色有哪些講究）
- 2023-07-01 抽真空的臘牛肉存放要冷凍還是冷藏（抽真空的臘牛肉能保存多久）
- 2023-07-01 衛(wèi)生間換氣扇套什么定額子目（怎樣選擇衛(wèi)生間換氣扇）
- 2023-07-01 100平米水地暖一個月燃氣費（100平米地暖一個月燃氣費多少）
- 2023-07-01 評估行業(yè)的現(xiàn)狀和前景（房地產(chǎn)評估行業(yè)前景如何）
- 2023-07-01 是養(yǎng)貓咪好還是養(yǎng)狗狗好?（如何選擇養(yǎng)貓還是養(yǎng)狗）
- 2023-07-01 榆木和桐木家具的優(yōu)缺點（桐木家具的優(yōu)缺點）
- 2023-07-01 2023契稅最新政策（商品房交房時需要交哪些費用）
- 2023-07-01 正山小種一包多少克（正山小種一包全泡嗎）
- 2023-07-01 康磚茶的功效與作用（康磚茶是什么茶）
- 2023-07-01 收音機音樂臺是哪個臺（收音機音樂電臺是哪個頻道）
- 2023-07-01 營業(yè)執(zhí)照怎么注銷個體戶（營業(yè)執(zhí)照怎么注銷）
- 2023-07-01 餐飲許可證辦理流程圖（小餐飲許可證辦理流程）
- 2023-07-01 養(yǎng)小泰迪的方法（養(yǎng)小泰迪的注意事項）