推 Starvilo : Apmo 題目 12/09 19:59
※ 引述《adamchi (adamchi)》之銘言：
: 設n為正整數,且所有與n互質的正整數m都滿足
: m^6除以n的餘數等於1,則n之最大可能值為何?
: 答:504
這個應該不是中學做法不過就寫一下:
所求為 Carmichael Function λ(n) 取值為 6 的因數的所有 n 值中的最大值
https://tinyurl.com/y5hz9frt
(會說是 6 的因數而不只是取值 6 的原因是
例如 λ(4) = 2, 雖然 m=1,3 有 m^2 mod 4 餘 1, 但 m^6 mod 4 也顯然餘 1
不過根據下面的計算, 其實我們只求 λ(n) = 6 的 n 值也沒差)
若照公式列出質數次方的值則有:
λ(2) = 1, λ(4) = 2, λ(8) = 2, λ(16) = 4 以上不合
λ(3) = 2, λ(9) = 6, λ(27) = 18 以上不合
λ(5) = 4 以上不合
λ(7) = 6, λ(49) = 42 以上不合
更大的質數顯然也不合
這裡不合的原因都是值不是 6 的因數, 會讓接下來的運算求得不符需要的值
對一般整數, λ(n) 的求法是拆成個別質數次方求值得求其 LCM
容易知道上面合的這三組質數次方 (2, 4, 8), (3, 9), (7)
每組取至多一個乘起來都是所要的 n 值
因此 n 最大可以取 8*9*7 = 504 即為所求
(即是 λ(504) = LCM(λ(8), λ(9), λ(7)) = LCM(2, 6, 6) = 6 )
====
然後順帶扔一個 OEIS 數列上來: http://oeis.org/A270562
--
Ace Snake Santa Clover Junpei June Seven Lotus 9th man cabin kitchen casino
shower operating room laboratory Ｔ Ｈ Ｅ chart captain quarter confinement
torture room steam engine room cargo chapel library study incinerator Gigantic
Q director office security Ｎ Ｏ Ｎ Ａ Ｒ Ｙ archives control laboratory
pec treatment garden pantry gaulem bay rec room crew quarters infirmary lounge
elevator Tenmyouji Quark Dio Ｇ Ａ Ｍ Ｅ Ｓ Luna Phi Sigma Alice Clover K
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.234.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1607506795.A.D90.html
※ 編輯: LPH66 (106.1.234.196 臺灣), 12/09/2020 17:41:03