我如何證明如果gcd(m,n)≠1gcd(m,n)≠1text{gcd}(m,n) neq 1，結果是ppp或者qqq在 RSA 中？

我明白那個 $ \text{gcd}(m,n) $ 需要是 $ 1 $ 所以我們可以應用歐拉定理，如果不是 $ 1 $ , 結果是主要因素之一 $ n $ . 但是為什麼結果總是這樣 $ p $ 或者 $ q $ ? 不能是別的號碼嗎？

讓 $ m $ 和 $ n $ 是兩個素數的乘積，如 RSA： $ n=pq $ 和 $ m = rs $ .

如果 $ m=n $ 那麼我們就無法了解素數，

如果 $ m\not= n $ 和 $ \gcd(m,n) >1 $ ： 自從 $ m\not =n $ 然後 $ 1<\gcd(m,n) < \min(m,n) $

gcd 是除數集交集的最大值 $ D_n={1,p,q,n} $ 和 $ D_m = {1,r,s,m} $ 因此我們現在知道 $ \gcd(m,n) \in {p,q}\cap {r,s}\subset{p,q,r,s} $ 因此 gcd 返回一個素數除數 $ n $ 和 $ m $ .

一個積極的 $ d’ $ 和 $ d’\mid n $ 和 $ d’\mid x $ 稱為公約數，其中最大的稱為最大公約數 $ d = \gcd(x,n) $ .

自從 $ n $ 是兩個不同素數的乘積，那麼任何公約數都必須除 $ n $ . 由算術基本定理， $ n $ 是唯一的（由訂單決定），即 $ n=p\cdot q $

因此任何公約數 $ x $ 和 $ n $ 必須至少劃分一個 $ 1,p,q,pq=n $ .

• $ 1 $ 當且當 $ p\not\mid x $ 或者 $ q\not\mid x $
• $ p $ 如果 $ p \mid x $ 和 $ q \not\mid x $
• $ q $ 如果 $ q \mid x $ 和 $ p \not\mid x $
• $ n $ 如果 $ x \equiv 0 \bmod n $

作為結論 $ \gcd(x,n) \in {1,p,q,n} $

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