表明2ñ−1≡1（模組ñ)2ñ−1≡1(反對ñ)2^{N-1}equiv1pmod N什麼時候ñ=2p−1ñ=2p−1N=2^p-1為素數ppp

我在以前的考試中得到了這個問題，我做錯了。從那以後，我已經回顧了好幾次，但我似乎無法理解。我真的很想知道該怎麼做，所以如果有人可以逐步指導我（包括答案​​），我將不勝感激！謝謝！問題如下：

讓 $ p $ 是一個奇數素數並且 $ N=2^{p}-1 $ . 這個問題的目標是證明 $ 2^{N-1} $ 相當於 $ 1 \mod N $ ，即 $ N $ 通過費馬素數檢驗 $ a=2 $ .

$$ Note: This doesn’t mean that N is necessarily prime. For example, if $p=11$, $N=2047=2389$ and if $p=23$, then $N=8388607=47178481$. $$然後，執行以下操作： a) 解釋原因 $ 2^p $ 相當於 $ 1 \mod N $ 是真的

b) 證明 $ N-1 $ 相當於 $ 0 \mod p $

c) 使用 a 和 b 部分來證明 $ 2^{N-1} $ 相當於 $ 1 \mod N $

一種） $ 2^p \equiv 1 \mod N $ 因為 $ 2^p = N + 1 $ . 當你減少 $ \mod N $ （除以時取餘數 $ N $ )，剩下 1 個。

b) $ N - 1 = 2^p - 2 $

由費馬小定理， $ 2^p \equiv 2 \mod p $ :

$ 2^p - 2 \equiv 2 - 2 \equiv 0 \mod p $

C）

從 a) 我們知道 $ 2^p \equiv 1 \mod N $

從 b) 我們知道 $ N - 1 \equiv 0\mod p $ ， 所以 $ N-1 $ 是的倍數 $ p $ .

讓 $ N-1 = kp $ 對於某個整數 $ k $

$ 2^{N-1} = 2^{kp} $

$ (2^p)^{k} \equiv 1^k \equiv 1 \mod N $

引用自：https://crypto.stackexchange.com/questions/19983