Board logo

標題: 1061中山大學雙週一題 [打印本頁]

作者: oceanli    時間: 2017-10-19 12:15     標題: 1061中山大學雙週一題

第2題
證明對於正偶數\(n\),\(n^2-1\)整除\(2^{n!}-1\)。
高中數學,有可能用數學歸納法證明嗎
http://www.math.nsysu.edu.tw/~problem/2017f/1061Q&A.htm
作者: thepiano    時間: 2017-10-19 13:33     標題: 回復 1# oceanli 的帖子

目前還在徵答,請不要回答!
作者: thepiano    時間: 2017-10-21 08:12     標題: 回復 2# thepiano 的帖子

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

小弟覺得數歸應該做不出來!
作者: 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

(嘗試不使用尤拉定理或費馬小定理解本題)

n = 2 時命題成立,以下考慮 n > 2 的情形。

令 2^n! - 1 = M,只要證明 (n+1) | M 與 (n-1) | M 即可。


(n+1) | M 的證明:

考慮 n+1 個數 2⁰+1,2¹+1,2²+1,...2ⁿ+1 :

1. 若其中有兩者對於模 n+1 同餘,則其差為 n+1 的倍數。則易知:

存在 p∈N,1 ≤ p ≤ n,滿足 (n+1) | (2^p -1),又 (2^p -1) | M,得證。

2. 若此 n+1 個數對模 n+1 皆不同餘,則存在 q∈N,1 ≤ q ≤ n,滿足 (n+1) | (2^q +1),又 (2^q +1) | M,得證。


(n-1) | M 的證明:

仿上述 1. (亦可考慮 n 個數: 2¹,2²,...2ⁿ),其中必然有兩者對於模 n-1 同餘,同理得證。


綜上,原命題成立。





歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0