Re: [中學]餘數問題

[kilva (嗡嗡)]

※ 引述《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* 嗎？
→ kilva       : 我還真有想過，中途就放棄了XD
推 ddxu2       : 最後應該只需要分別算1，3，5，7的6次方除以2^3的餘
→ ddxu2       : 數；1，2，4，5，7，8的6次方除以3^2的餘數；7的以
→ ddxu2       : 此類推。就證明了？
→ kilva       : 還要證明當a、b互質，且m%a=1, m%b=1，則m%ab=1
→ kilva       : 嗯！這樣就噔完了。
→ kilva       : 證完了