(n^k-n)是八個質數的公倍數，求k

Question

這是我偶然發現的難題喔！說穿了也很簡單，來考考各位高手。
k是正整數，且對於任意正整數n而言，(n^k-n)可以同時被2,3,5,7,13,17,19,37整除，也就是說(n^k-n)恆為這八個質數的公倍數。請問k可以是多少？
我的答案是145(過幾天我會告訴大家我怎麼找到這數字的，也許大家可以想想這數字是怎麼來的)，不知道還有沒有更小的k值？若有，請提供並給證明。謝謝！
大家切磋討論一下囉！

這樣好了，給點提示，如果只要求(n^k-n)是2,3,5,7的公倍數，那麼k只要是13就夠了。

抱歉，k不等於1

Answer 1

令2,3,5,7,13,17,19,37依序為p1, p2,..., p8..........n且 P = Πpi.........i=1令 K = lcm(p1-1, p2-1,..., p8-1)對每一個 i 而言根據費瑪小定理 n(pi-1) ≣ 1 (mod pi) 對所有與pi互質的n則 nK ≣ 1 (mod pi) 對所有與pi互質的n所以 n(K+1) ≣ n (mod pi) 對所有的整數n則 n(K+1)-n ≣ 0 (mod pi) 對所有的整數n所以 對每一個 i 而言 pi 都整除 n(K+1)-n所以 P 整除 n(K+1)-n所以K+1=lcm(2-1,3-1,5-1,7-1,13-1,17-1,19-1,37-1)+1=lcm(1,2,4,6,12,16,18,36)+1=144+1=145至於會不會有更小的k就留給聰明的你嚕

2005-05-27 13:26:48 補充：
其實這問題等價於
是在存在小於p的正整數k
使得p都可以整除n^k-n

要是這樣的k不存在的話
那這題就不會有更小的k了

2005-05-27 13:40:31 補充：
其實不會有更小的k啦

2005-05-27 20:09:30 補充：
會這麼寫只要是為了一般性啦
只要p_i是質數就可以了

2005-05-30 22:38:20 補充：
阿 不是要証明沒有更小的k
想說過幾天再回答的說

2005-06-01 10:02:14 補充：
其實這跟費馬小定理差不多啦

這是費馬小定理
當gcd(n,p)=1時都有
n^p=1(mod p)

那對一個n
n^1,n^2,n^3,...(mod p)
一直算一下一定會有1出現
我們有興趣的就是最小的k
使得n^k=1(mod p)

我們定義這個k叫做n模p的order
顯得的k最大就是p-1

ps:當然要是gcd(n,p)不為1就不能有n^k=1(mod p)

2005-06-01 10:04:26 補充：
例如p=5

2=2(mod 5)
2^2=4(mod 5)
2^3=3(mod 5)
2^4=1(mod 5)

所以2模5的order就是4

所以5要能整除n^k-n的話, k最小就是4

2005-06-01 10:05:18 補充：
只要對所有的p都存在order是p-1的數的話
那得到我們所要的不會有更小的K

2005-06-01 10:11:21 補充：
而對p而言
模p的order=p-1的數
定義成p的primitive root

所以只要對所有的p
都存在primitive root的話
我們的問題就得証了

2005-06-01 10:12:46 補充：
而對p而言
模p的order=p-1的數
定義成p的primitive root

所以只要對所有的p
都存在primitive root的話
我們的問題就得証了

2005-06-01 10:19:14 補充：
而p的primitive root的個數
剛好就是φ(φ(p))=φ(p-1)>0個
所以就得証啦

φ是尤拉推廣費馬小定理時所定義的函數
φ(n)是定義成小於n且與n互質的數的個數

至於p的primitive root的個數
為何是φ(φ(p))個
那又是一連串的定理的

以上定理
參考DM Burton. Elementary Number Theory, 4/e

Answer 2

台灣首家合法娛樂城開幕囉!

體育博彩、真人對戰、現場遊戲、彩球

投注高賠率，歡迎您來體驗!

官方網站 aa777.net

Answer 3

嗯!這是一個好問題.........

Answer 4

我想太快了，我知道那兒想錯了。看來還是寫下來，不要單在腦中想好。先留機會給網友吧，我是知道怎樣處理的。

2005-05-27 10:56:58 補充：
應該沒錯了，證明你我深知肚明，就留給其他人吧。

先把各數減 1，取最小公倍數加 1。
如你的例子有：
lcm(1, 2, 4, 6) = 12
再加 1 就是 13。

你題目則是：
lcm(1, 2, 4, 6, 12, 16, 18) = 144
再加 1 就是 145

Answer 5

n可以是1，因為我說了，"對任意正整數n都成立"，難決定的是k，k=1當然是一個解，但它是平凡解，所以要排除掉。
是要用費馬小定理沒錯，可是不是那樣求。95顯然不合，2^95個位數是8，減掉2變成6，個位數是6的整數會是5的倍數嗎？在5這一關就過不了。
13=(2 + 3 + 5 + 7) - 4那只是巧合，不是這樣算的。

2005-05-27 19:13:02 補充：
dd:
我猜你真的是數學相關科系的人，而非像我這樣的業餘者。
從你用"Π"就知道了，在正式與好寫易懂之間，你選擇了前者。
你直接說P=2*3*5*7*13*17*19*37不就好了？你把"Π"搬出來用不見得比較好寫(要三行)，更重要的是，對於閱覽者必然更難懂，可見你一定是習慣了這樣的寫法，所以寧選擇Π。我有沒有猜對？

2005-05-27 19:22:48 補充：
會想到這個問題，是因為前幾年我剛會一點同餘時，看到了一個有趣的証明：
n^13-n恆可以被2,3,5,7,13整除。
我用很笨的方法，例如要證明n^13-n恆可以被13整除，就證明n=0,1,2...12都成立，那麼任一整數n都成立。
用同樣的方法，證明n^13-n可以被2,3,5,7整除，整個證明才完成。
直到認識費馬小定理，類似的問題我才一點一點拼湊到這個更快的方法。

2005-05-30 23:43:41 補充：
dd:
你不是說沒有了嗎？而且我都等那麼多天了，反正我重點不在這裡。啊！抱歉，我不求甚解。
(其實是因為最近在想一些怪怪的題目想考大家，無心想這個問題，真抱歉！)
而且要證明沒有更小的k值對我太難了，我試過，沒有頭緒。