推 huang419 :每次看到大師的文 都讓我學習到了許多 04/03 15:08
※ 引述《Bourbaki (大狐狸)》之銘言：
: 1. 729=27^2
: 71289=267^2
: 試證71111288889為某個正整數的平方
: 這題完全看不出在幹什麼
: 2. 561=3*11*17
: 證明a^561≡a (mod 561) for all a
: 這題的前一小題是341=11*31 證明2^341≡2 (mod 341)
: 但這似乎是完全不同的狀況
:
找了一些資料.順便也談談561這個數
p
費馬小定理說 if p is prime ==> a ≡ a (mod p) ,a為任何整數
n
這時候就有人發想說.反推是否成立.就是 a ≡ a (mod n) ==> n is prime ???
341
這時候 a = 2 ,n =341.跳出來說 2 ≡ 2 (mod 341),但341不是質數阿
於是將這類型滿足上式的數.稱為pseudo prime(偽質數).而對應的底稱為 base
如 341 is pseudo-prime to the base 2 .當然還有許多偽質數.
http://ppt.cc/wZmV 對應不同的底.也有不同的偽質數.
不過這樣.也還未結束.因為費馬小定理的逆推.a是任何整數的.也就是如果有n
n
滿足對任何的a有.a ≡ a (mod n ).這樣條件變更嚴格了.n總會是質數吧 ?
561
n= 561 又跳出來說話. a ≡ a(mod 561 ).於是滿足這類型的數.稱為
Carmichael number.(絕對偽質數) http://ppt.cc/XAqO .於是對費馬小定理的
發想.就此打住.這樣的結果.也少了一個.人們可以對大質數的檢定.
[可以想見.如果逆推成立.對質數的檢定會多有效率!@]
來解題嚕:
3 561 3*187 187 3*62+1 63 3*21
a ≡ a(mod3) ,a ≡ a ≡a ≡ a ≡ a ≡ a
7*3 7 3
≡a ≡a ≡ a ≡a (mod3 )
11 561 11*51 51 11*4+7 11
a ≡ a (mod11), a ≡ a ≡a ≡ a ≡ a ≡ a(mod11)
17 561
a ≡ a(mod17) , a ≡ ...........................≡ a (mod 17)
561
===> a ≡ a (mod 561)
Q.E.D
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.162.84.241
※ 編輯: coolbetter33 來自: 1.162.84.241 (03/12 02:38)
※ 編輯: coolbetter33 來自: 1.162.84.241 (03/12 02:40)