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

[hasuekee29 (Yueh)]

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
推 Transfat: 應該也要測7^2, 7^4,不過用看的就知道不是餘1 ?
推 joeboy: 如果不是質數的話，費馬小定理的通式次方要放尤拉函數
推 joeboy: http://i.imgur.com/46Wqw1G.jpg
→ joeboy: 這裡面有提到
推 Gabino: 28的因數感覺都有嫌疑
那像是7^3 7^5這些非28因數的值為何可以跳過不測呢
※ 編輯: hasuekee29 (223.137.160.75), 02/06/2017 13:53:33
推 hypnos135g: 應該是因為他會是一個以7為generator的cyclic group
→ hypnos135g: 所以order會在28的因數內?
推 aa06697: 已知7^28=1 若7^3 = 1 = > 7^27 = 1 => 7^28 = 7 矛盾 用
→ aa06697: 這邊去想你就知道為什麼只要檢查28的因數了
推 yupog2003: 感謝aa大，我已秒懂
了解，謝謝以上幾位大大考前救援
※ 編輯: hasuekee29 (223.137.160.75), 02/06/2017 21:07:27