Math Pro 數學補給站 » 高中的數學 » 1061中山大學雙週一題

oceanli 發表於 2017-10-19 12:15

1061中山大學雙週一題

第2題
證明對於正偶數\(n\)，\(n^2-1\)整除\(2^{n!}-1\)。
高中數學，有可能用數學歸納法證明嗎
[url]http://www.math.nsysu.edu.tw/~problem/2017f/1061Q&A.htm[/url]

thepiano 發表於 2017-10-19 13:33

回復 1# oceanli 的帖子

目前還在徵答，請不要回答！

thepiano 發表於 2017-10-21 08:12

回復 2# thepiano 的帖子

已經徵答結束，官方罕見的嚴厲聲明
[url]http://www.math.nsysu.edu.tw/~problem/[/url]

小弟覺得數歸應該做不出來！

oceanli 發表於 2017-10-23 22:37

回復 3# thepiano 的帖子

感謝，不是有意討徵答之解，有用非數歸解出，是想說是否有機會用數歸，但能力有限，卡關無法突破，無意造成困擾！

howt 發表於 2017-10-27 00:56

由歐拉φ函數定理，n是正偶數時， 有 n^2-1 |  2^{ φ(n^2-1) } -1

因此只要證明 φ(n^2-1) | n !  即可

n是正偶數，因此 n+1  與 n-1 互質 ， 故  φ(n^2-1)  =  φ(n+1) *φ(n-1)

又由定義知 φ(n+1) <n+1 , φ(n-1) <n+1 ....(A)


令 n+1 的(奇)質因數分解為 p1^{x1}*p2^{x2} ...*pn^{xn} ，那麼 φ(n+1) = p1^{x1 -1 } p2^{x2 -1 } ...pn^{xn -1 }  *(p1 -1)*(p2-1)...*(pn-1)

類似的令 n-1 = q1^{y1 } *q2^{y2} ...*qm^{ym} ， 則  φ(n-1) = q1^{y1 -1 } q2^{y2 -1 } ...qm^{ym -1 }  *(q1 -1)*(q2-1)...*(qm-1)

由於 n+1 跟 n-1 互質 ，因此任意兩個 pi 跟 qj 都不相同，故任意兩個 (pi-1) 和 ( qj -1) 也不相同

類似的任意兩個 pi 跟 qj-1 也不相同 (p 與 q-1互質)

結合(A)可知，上面 φ(n+1) 跟 φ(n-1) 的因數完全相異 ，且都 <n+1 ，因此所有因數都是 < n+1 的相異數

故 φ(n^2-1) | n !

cefepime 發表於 2017-10-30 00:16

[size=3](嘗試不使用尤拉定理或費馬小定理解本題)[/size]
[size=3][/size]
[size=3]n = 2 時命題成立，以下考慮 n > 2 的情形。[/size]
[size=3][/size]
[size=3]令 2^n! - 1 = M，只要證明 (n+1) | M 與 (n-1) | M 即可。[/size]
[size=3][/size]
[size=3][/size]
[size=3][color=black][b](n+1) | M 的證明:[/b][/color][/size]
[size=3][/size]
[size=3]考慮 n+1 個數 2⁰+1，2¹+1，2²+1，...2ⁿ+1 :[/size]
[size=3][/size]
[size=3]1. 若其中有兩者對於模 n+1 同餘，則其差為 n+1 的倍數。則易知:[/size]
[size=3][/size]
[size=3]存在 p∈N，1 ≤ p ≤ n，滿足 (n+1) | (2^p -1)，又 (2^p -1) | M，得證。[/size]
[size=3][/size]
[size=3]2. 若此 n+1 個數對模 n+1 皆不同餘，則存在 q∈N，1 ≤ q ≤ n，滿足 (n+1) | (2^q +1)，又 (2^q +1) | M，得證。[/size]
[size=3][/size]
[size=3][/size]
[size=3][b](n-1) | M 的證明:[/b][/size]
[size=3][/size]
[size=3]仿上述 1. (亦可考慮 n 個數: 2¹，2²，...2ⁿ)，其中必然有兩者對於模 n-1 同餘，同理得證。[/size]
[size=3][/size]
[size=3][/size]
[size=3]綜上，原命題成立。[/size]
[size=3][/size]

查看完整版本: 1061中山大學雙週一題