[理工] 99清大離散小問題

看板Grad-ProbAsk作者 (Yueh)時間7年前 (2017/02/06 12:37), 7年前編輯推噓7(703)
留言10則, 6人參與, 最新討論串1/1
http://i.imgur.com/yih28jx.jpg
這題是99清大計科 在寫這題的時候先用了費馬小定理 接著測試7^1~7^28找最小解,很費時 解答部分只測了7^7 、7^14 想問為何可以只測試平方項 另外想問考試答題時,若答案是組合數,可以直接以組合數作答嗎?還是乘開比較好呢? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.160.75 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486355821.A.55A.html

02/06 12:48, , 1F
應該也要測7^2, 7^4,不過用看的就知道不是餘1 ?
02/06 12:48, 1F

02/06 12:51, , 2F
如果不是質數的話,費馬小定理的通式次方要放尤拉函數
02/06 12:51, 2F

02/06 12:54, , 3F

02/06 12:54, , 4F
這裡面有提到
02/06 12:54, 4F

02/06 13:06, , 5F
28的因數感覺都有嫌疑
02/06 13:06, 5F
那像是7^3 7^5這些非28因數的值為何可以跳過不測呢 ※ 編輯: hasuekee29 (223.137.160.75), 02/06/2017 13:53:33

02/06 14:00, , 6F
應該是因為他會是一個以7為generator的cyclic group
02/06 14:00, 6F

02/06 14:01, , 7F
所以order會在28的因數內?
02/06 14:01, 7F

02/06 17:29, , 8F
已知7^28=1 若7^3 = 1 = > 7^27 = 1 => 7^28 = 7 矛盾 用
02/06 17:29, 8F

02/06 17:29, , 9F
這邊去想你就知道為什麼只要檢查28的因數了
02/06 17:29, 9F

02/06 17:30, , 10F
感謝aa大,我已秒懂
02/06 17:30, 10F
了解,謝謝以上幾位大大考前救援 ※ 編輯: hasuekee29 (223.137.160.75), 02/06/2017 21:07:27
文章代碼(AID): #1Ob_rjLQ (Grad-ProbAsk)