[理工] 離散 數論

[mistel (Mistel)]

https://i.imgur.com/DoctXNw.jpg

請問561不是質數，為什麼可以確定跟a跟n互質，a^560同餘1（mod 561)？

還有請問為什麼答案分子要再扣1，分母要扣2呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.174.132 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1570893097.A.516.html
※ 編輯: mistel (223.137.174.132 臺灣), 10/12/2019 23:23:47
→ Ricestone: 因為那就是Carmichael number的性質
感謝，完全沒看過這個名詞...太恐怖了
另外請問：
https://i.imgur.com/wgIQSTV.jpg
為什麼這題可以確定3^x跟1同餘的那個x會在10的正因數裡呢？
→ Ricestone: 分母跟分子都是因為題目有說不選1
→ DingDang827: b在(1,n-1] 均勻分布所以不包含1和561
感謝！
※ 編輯: mistel (223.137.174.132 臺灣), 10/13/2019 00:06:11
→ Ricestone: 如果有個跟10互質的m，3^m=1 mod 11 則
→ Ricestone: 因為互質，所以會有 ma + 10b = 1
→ Ricestone: 代一代就得到3^1 = 1 mod11 矛盾
感謝！
※ 編輯: mistel (223.137.174.132 臺灣), 10/13/2019 00:21:09