作者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/cn.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