[中學] 2019AIME一題~

[adamchi (adamchi)]

試求 2019^8 + 1最小的奇數質因數

答:97

請問:怎麼使用費馬小定理解之,謝謝~


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.197.122 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1615131031.A.A5C.html
推 TimcApple   : 設 2019^8 = -1, 2019^16 = 1 (mod p)
→ TimcApple   : p = 16k + 1 = 17, 97, ...
→ TimcApple   : 其中 2019 = -4, 2019^4 = 1 (mod 17) 不合
→ TimcApple   : 接著 2019 = -18, 2019^2 = 33
→ TimcApple   : 2019^4 = 22, 2019^8 = -1 (mod 97)
→ TimcApple   : 因此答案是 97