證明任意正整數的13次方減自己必定可被2730整除

Question

n為正整數，證明(n13-n)必定可被2730整除。既然大家最近有興趣，樂於挑戰這類問題，那麼就來個大的唄！選方法最漂亮的。

把n^13-n分解成
(n-1)n(n+1)(n^2+1)(n^4-n^2+1)(n^2+n+1)(n^2-n+1)
再慢慢討論，是個方法。但不是最漂亮的。

有這麼難嗎？
開放因式分解討論法好了，誰最先答出來，最佳解答就給他。

R.Johnson：
你沒想過和同餘結合起來嗎？你的方法太"辛苦"了點
若n=0,1,2,3...(p-1)時，(n^13-n)皆為p的倍數，則對於任意整數n，(n^13-n)必為p的倍數。
所以要證它是13的倍數，只要確定n=0到12時，它都是13的倍數即可。
但是這樣還是太大(有計算機另當別論)，所以可以改成用n=0,1,2,3,4,5,6,(-6),(-5),(-4),(-3),(-2),(-1)分別代入計算。

Answer 1

可以看出來吧
a最大值=56786730

2005-10-03 01:30:07 補充：
2730=2*3*5*7*13任意p ∈S={2,3,5,7,13}根據費馬小定理對任意整數n都有np-1 ≡ 1(mod p)所以 p | np-1-1 | n13-n而S中每個元素均為prime故 2730 = Πp∈S p | n13-n

2005-10-03 23:22:30 補充：
意思差不多呀
只是我有用到
n-1 | n^13-n
n^2-1 | n^13-n
n^4-1 | n^13-n
n^6-1 | n^13-n
n^12-1 | n^13-n

Answer 2

數大就是美
漂亮的解法!

n^13-n=(n-1)n(n+1)(n^2+1)(n^4-n^2+1)(n^2+n+1)(n^2-n+1)
2730=2*3*5*7*13
a,b,c,d,e皆為整數

因數2:
n=2a時,n^13-n有因數2
n=2a+1時,n-1=2a,有因數2 =>n^13-n有因數2
因數3:
n=3b時,n^13-n有因數3
n=3b+1時,n-1=3b,有因數3 =>n^13-n有因數3
n=3b-1時,n+1=3b,有因數3 =>n^13-n有因數3
因數5:
n=5c時,n^13-n有因數5
n=5c+1時,n-1=5c,有因數5 =>n^13-n有因數5
n=5c-1時,n+1=5c,有因數5 =>n^13-n有因數5
n=5c+2時,n^+1=5(5c^2+4c+1),有因數5 =>n^13-n有因數5
n=5c-2時,n^+1=5(5c^2-4c+1),有因數5 =>n^13-n有因數5
因數7:
n=7d,n^13-n有因數7
n=7d+1時,n-1=7d,有因數7 =>n^13-n有因數7
n=7d-1時,n+1=7d,有因數7 =>n^13-n有因數7
n=7d+2時,n^2+n+1=7(7d^2+5d+1),有因數7 =>n^13-n有因數7
n=7d-2時,n^2-n+1=7(7d^2-5d+1),有因數7 =>n^13-n有因數7
n=7d+3時,n^2-n+1=7(7d^2+5d+1),有因數7 =>n^13-n有因數7
n=7d-3時,n^2+n+1=7(7d^2-5d+1),有因數7 =>n^13-n有因數7
因數13:
n=13e時,n^13-n有因數13
n=13d+1時,n-1=13d,有因數13 =>n^13-n有因數13
n=13d-1時,n+1=13d,有因數13 =>n^13-n有因數13
n=13d+2時,n^4-n^2+1=13Q+16-4+3,有因數13 =>n^13-n有因數13
(Q是未知數部分,一定有因數13)
n=13d-2時,n^4-n^2+1=13R+16-4+3,有因數13 =>n^13-n有因數13
(R是未知數部分,一定有因數13)
n=13d+3時,n^2+n+1=13(13d^2+7d+1),有因數13 =>n^13-n有因數13
n=13d-3時,n^2-n+1=13(13d^2-7d+1),有因數13 =>n^13-n有因數13
n=13d+4時,n^2-n+1=13(13d^2+4d+1),有因數13 =>n^13-n有因數13
n=13d-4時,n^2+n+1=13(13d^2-4d+1),有因數13 =>n^13-n有因數13
n=13d+5時,n^2+1=13(13d+10+2)),有因數13 =>n^13-n有因數13
n=13d-5時,n^2+1=13(13d-10+2)),有因數13 =>n^13-n有因數13
n=13d+6時,n^4-n^2+1=13W+1296-36+1
=13W+13*97,有因數13 =>n^13-n有因數13
(W是未知數部分,一定有因數13)
n=13d-6時,n^4-n^2+1=13F+1296-36+1
=13F+13*97,有因數13 =>n^13-n有因數13
(F是未知數部分,一定有因數13)


=>n^13-n有因數2,3,5,7,13,
因為n為正整數且2730=2*3*5*7*13,
所以2730可以整除(n^13-n)

2005-09-25 20:14:38 補充：
用同餘就不好看了,要列就列漂亮一點

Answer 3

n的條件是不是還要加上一個不等於1

Answer 4

dd：
我知道你知道那個方法，所以拜託慢幾天出手，我想看看有沒有其他人知道。

2005-09-22 00:23:13 補充：
不必呀！0的確可被2730整除呀！0是2730的0倍。

2005-09-22 00:28:08 補充：
話再說回來，我現在才發現n^13-n可分解為(n-1)n(n+1)(n^2-n+1)(n^2+1)(n^2+n+1)(n^4-n^2+1)七個數相乘，第1到第3數是公差1的等差數列，第4到第6數是公差n的等差數列。好美麗的數學！

2005-09-25 01:39:37 補充：
是要用費馬小定理，但是，怎麼用？

2005-09-25 21:13:53 補充：
老王：
差一點吧！？費馬小定理裡，2,3,5,7所用的指數分別是1,2,4,6，而這題則限定指數是13耶！希望你能把你完整的証明寫在"回答區"中。

R.Johnson：
用同餘不好看？

2005-09-25 21:36:48 補充：
若n=0,1,2,3...(p-1)時，(n^13-n)皆為p的倍數，則對於任意整數n，(n^13-n)必為p的倍數。
p=2
n=0時，0^13≡0(mod 2)
n=1時，1^13≡1(mod 2)

p=3
n=0時，0^13≡0(mod 3)
n=±1時，(±1)^13≡±1(mod 3)

p=5
n=0時，0^13≡0(mod 5)
n=±1時，(±1)^13≡±1(mod 5)
n=±2時，(±2)^13≡±2*(4)^6≡±2*(-1)^6≡±2(mod 5)

2005-09-25 21:49:06 補充：
p=7
n=0時，0^13≡0(mod 7)
n=±1時，(±1)^13≡±1(mod 7)
n=±2時，(±2)^13≡±2*(8)^4≡±2*(1)^4≡±2(mod 7)
n=±3時，(±3)^13≡±3*(9)^6≡±3*(2)^6≡±3*64≡±3(mod 7)

p=13
n=0時，0^13≡0(mod 13)
n=±1時，(±1)^13≡±1(mod 13)
n=±2時，(±2)^13≡±2*(64)^2≡±2*(-1)^2≡±2(mod 13)
n=±3時，(±3)^13≡±3*(27)^4≡±3*(1)^4≡±3(mod 13)

2005-09-25 21:49:25 補充：
p=13
n=±4時，(±4)^13≡±4*(64)^4≡±4*(-1)^4≡±4(mod 13)
n=±5時，(±5)^13≡±5*(25)^6≡±5*(-1)^6≡±5(mod 13)
n=±6時，(±6)^13≡±6*(36)^6≡±6*(-3)^6≡±6*(-27)^2≡±6*(-1)^2≡±6(mod 13)

所以n^13-n為2,3,5,7,13的公倍數
應該簡潔多啦！怎會不好看？

2005-09-26 21:35:25 補充：
老王：
跟你說只差一點就是真的只差一點點嘛！「費馬小定理裡，2,3,5,7所用的指數分別是1,2,4,6，並非13」，我只能提示到這裡，再説下去就破壞你思考的樂趣了。
當初笨笨的我以上面那個同餘方法證明這個證明時，沒有多大成就感；但是當我利用費馬小定理頓悟出一個更好的方法時(還可以推廣喔！)，那種愉悅真是無可言喻，希望你也能得到它。

2005-09-27 21:24:39 補充：
嗯！八個質數的乘積，好大！！已經呼之欲出了，老王。

2005-09-28 12:40:37 補充：
老王：
方法知道了，會證明嗎？要不要回答看看？

2005-10-03 21:16:09 補充：
k為正整數，p為質數，若(k-1)為(p-1)的倍數，則對於任意整數n，(n^k-n)恆為p的倍數。
證明：
n為p的倍數時，顯然成立。
當n不為p的倍數時，
令k-1=(p-1)m，m為正整數
根據費馬小定理，
n^(p-1)≡1(mod p)
n^[(p-1)m]≡1^m(mod p)
n^(k-1)≡1(mod p)
n^k≡n(mod p)
因此(n^k-n)為p的倍數

因此，13-1=12，12的因數有1,2,3,4,6,12，加1變成2,3,4,5,7,13，其中2,3,5,7,13是質數。n^13-n恆為2,3,5,7,13的最小公倍數2730的倍數。