作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 離散 數論
時間Sat Oct 12 23:11:35 2019
https://i.imgur.com/DoctXNw.jpg
請問561不是質數，為什麼可以確定跟a跟n互質，a^560同餘1（mod 561)？
還有請問為什麼答案分子要再扣1，分母要扣2呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.174.132 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1570893097.A.516.html
※ 編輯: mistel (223.137.174.132 臺灣), 10/12/2019 23:23:47
1F：→ Ricestone: 因為那就是Carmichael number的性質10/12 23:54
感謝，完全沒看過這個名詞...太恐怖了
另外請問：
https://i.imgur.com/wgIQSTV.jpg
為什麼這題可以確定3^x跟1同餘的那個x會在10的正因數裡呢？
2F：→ Ricestone: 分母跟分子都是因為題目有說不選110/13 00:02
3F：→ DingDang827: b在(1,n-1] 均勻分布所以不包含1和56110/13 00:04
感謝！
※ 編輯: mistel (223.137.174.132 臺灣), 10/13/2019 00:06:11
4F：→ Ricestone: 如果有個跟10互質的m，3^m=1 mod 11 則 10/13 00:13
5F：→ Ricestone: 因為互質，所以會有 ma + 10b = 1 10/13 00:14
6F：→ Ricestone: 代一代就得到3^1 = 1 mod11 矛盾10/13 00:16
感謝！
※ 編輯: mistel (223.137.174.132 臺灣), 10/13/2019 00:21:09