為什麼這篇餘數問題鄉民發文收入到精華區：因為在餘數問題這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者kilva (嗡嗡)看板Math標題Re: [中學]餘數問題時間Wed Dec 9 22:51...
餘數問題 在 小嵐 Beryl Instagram 的最佳解答
2021-08-03 12:59:52
O7O6 午覺睡太多 寫程式的除錯旅程 卡住30分鐘原來是餘數問題 規則與邏輯與服從 #程式的詩...
※ 引述《adamchi (adamchi)》之銘言：
: 設n為正整數,且所有與n互質的正整數m都滿足
: m^6除以n的餘數等於1,則n之最大可能值為何?
: 答:504
只要m=1,...,n-1中與n互質的數，m^6除以n的餘數均等於1，其他所有
正整數m=kn+1,...,kn+(n-1)中與n互質的數，m^6除以n的餘數均等於1。
先看質數部分
n=2時，1^6%2=1，符合。
n>2時，因2^6-1=63=3^2*7，只有3與7有機會。
n=3時，1^6%3=1, 2^6%3=1，符合。
n=7時，因費馬小定理，m^6%7=1 for m=1,...,6，符合。
因此，可知n的最大可能值之質因數一定只有2、3或7。
又，5與2、3、7互質，且5^6-1=15624=2^3*3^2*7*31，
所以n的最大可能值<=2^3*3^2*7=504。
剩下如何證明504符合題目要求，就不知道了。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.116.174 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1607525480.A.BFF.html
※ 編輯: kilva (1.171.116.174 臺灣), 12/09/2020 22:53:41
推 Vulpix : 剩下的不就是算一遍 Z_504* 嗎？ 12/09 22:55
→ kilva : 我還真有想過，中途就放棄了XD 12/09 23:01
推 ddxu2 : 最後應該只需要分別算1，3，5，7的6次方除以2^3的餘 12/09 23:42
→ ddxu2 : 數；1，2，4，5，7，8的6次方除以3^2的餘數；7的以 12/09 23:42
→ ddxu2 : 此類推。就證明了？ 12/09 23:42
→ kilva : 還要證明當a、b互質，且m%a=1, m%b=1，則m%ab=1 12/09 23:50
→ kilva : 嗯！這樣就噔完了。 12/09 23:51
→ kilva : 證完了 12/09 23:52