1061中山大學雙週一題

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

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

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

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

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

由歐拉φ函數定理，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 !

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

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 同餘，同理得證。


綜上，原命題成立。