[理工] 离散数论 mistel PTT批踢踢实业坊

[理工] 离散数论

楼主: mistel (Mistel) 2019-10-12 23:11:35

https://i.imgur.com/DoctXNw.jpg
请问561不是质数，为什么可以确定跟a跟n互质，a^560同余1（mod 561)？
还有请问为什么答案分子要再扣1，分母要扣2呢？

作者: Ricestone (麦饭石) 2019-10-12 23:54:00

因为那就是Carmichael number的性质分母跟分子都是因为题目有说不选1

作者: DingDang827 (叮叮当) 2019-10-13 00:04:00

b在(1,n-1] 均匀分布所以不包含1和561

作者: Ricestone (麦饭石) 2019-10-13 00:13:00

如果有个跟10互质的m，3^m=1 mod 11 则因为互质，所以会有 ma + 10b = 1代一代就得到3^1 = 1 mod11 矛盾

继续阅读

[理工] 计组 p487u0424064 [理工] 计组p64yoz4ni [理工] 计组指令问题yoz4ni [理工] 线代同步对角化AndrewTsai46 [理工] 离散布林代数ouskit [理工] 计组 Strong/Weak ScalingAirComm [理工] 线代_关于函数空间fmtshk [理工] 计组下册196！Aa841018 [理工]Divide and conquer 的递回abcd012345 [理工] 离散_语言文法fmtshk

Contact Us: admin [ a t ] ucptt.com