[理工] 離散數論 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