發新話題
打印

115建國中學二招

回覆 5# ruee29 的帖子

填充12. 以下只證明 \( p, q \) 兩數中至少有一數為 3 或 2 (11/18 補充修正,(2) 證明中 \( \pm 1 \) 的矛盾,需要排除模 2)

歸謬地設 \( p,q \) 均大於 3。
(1) \( 3^{q-1}≡-1 (mod  p) \), \( 3^{q-1}≡-1 (mod  p) \)
由費瑪小定理有 \( 3^p≡3 (mod  p) \), \( 3^q≡3 (mod  q) \)
而由 \( pq∣3^p+3^q \) 可得 \( 3^p+3^q≡0 (mod  p) \) ⇒ \( 3+3^q≡0 (mod  p) \) ⇒ \( 3^{q-1}≡-1 (mod  p) \) ⇒ \( 3^{2q-2}≡1 (mod  p) \),
同理 \( 3^{p-1}≡-1 (mod  q) \), \( 3^{2p-2}≡1 (mod  q) \),(1) 證畢。

令 \( n_p,n_q \) 分別為最小的正整數使得 \( 3^{n_p}≡1 (mod  p) \) 及 \( 3^{n_q}≡1 (mod  q) \)
(2) \( \frac{2q-2}{n_p} \) , \( \frac{2p-2}{n_q} \)  均為奇數。
由(1)得 \( 3^{q-1}≡-1 (mod  p) \) 及 \( 3^{2q-2}≡1 (mod  p) \),故 \( \frac{2q-2}{n_p} \)  為奇數(若為偶數,則 \(  \frac{2q-2}{n_p} \cdot \frac12 =  \frac{q-1}{n_p} \)  為整數,而得 \( 3^{q-1}≡1 (mod  p) \) 而矛盾),
同理 \( \frac{2p-2}{n_q} \)  為奇數,(2)證畢。

令 \( k_p,k_q \) 分別為最大的正整數使得 \( 2^{k_p}∣n_p \) 及 \( 2^{k_q}∣n_q \)
(3) \( k_p,k_q \) 也是分別為最大的正整數使得 \( 2^{k_p}∣2q-2 \) 及 \( 2^{k_q}∣2p-2 \)。
由(2)知  \( \frac{2q-2}{n_p} \) , \( \frac{2p-2}{n_q} \) 為奇數,故 \( k_p,k_q \) 也是分別為最大的正整數使得 \( 2^{k_p}∣2q-2 \) 及 \( 2^{k_q}∣2p-2 \)。(3) 證畢。

由 \( n_p \) 的定義及費馬小定理可推得 \( n_p∣p-1 \),又 \( 2^{k_p}∣n_p \),因此 \( 2^{k_p}∣p-1 \) ⇒ \( 2^{k_p+1}∣2p-2 \),再由 (3) 知 \( k_p+1 \leq k_q \) ⇒ \( k_p<k_q \),同理 \( k_q<k_p \) 而得矛盾。

[ 本帖最後由 tsusy 於 2026-11-18 17:37 編輯 ]
網頁方程式編輯 imatheq

TOP

發新話題