證明Gcd_(e,λ(N))=1⟺Gcd_(e,φ(N))=1GCd(和,λ(ñ))=1⟺GCd(和,披(ñ))=1gcd(e, lambda(N)) = 1 hspace{1mm} Longleftrightarrow hspace{1m…
什麼是事實的證據 $ gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1 $
在哪裡：
$ N = P \cdot Q $ 在哪裡 $ P $ 和 $ Q $ 都是素數。
$ \varphi(N) $ 是歐拉 phi 函式
$ \lambda(N) $ 是卡邁克爾函式
證明大綱如下：
$ gcd(a,b)=1 $ 相當於聲稱 $ \not\exists p_\text{ prime}: p|a \land p|b $ （也就是說，不存在素數 $ p $ 這是兩者的一個因素 $ a $ 和 $ b $ )
現在，對於所有素數 $ p $ , $ p | \phi(N) $ 當且當 $ p | \lambda(N) $ （也就是說，對於所有素數 $ p $ , 要麼它們是兩者的一個因素 $ \phi(N) $ 和 $ \lambda(N) $ ，或者兩者都不是）。這可以通過檢查關係看出 $ \phi(N) = (p-1)(q-1) $ 和 $ \lambda(N) = (p-1)(q-1)/gcd(p-1,q-1) $ ，並觀察如果 $ gcd(p-1,q-1) $ 有一個主要的功率因數 $ r^n $ , 那麼兩者 $ p-1 $ 和 $ q-1 $ 是的倍數 $ r^n $ ， 因此 $ (p-1)(q-1) $ 有 $ r^{2n} $ 作為一個因素，所以 $ (p-1)(q-1)/gcd(p-1,q-1) $ 擁有 $ r^n $ （因此 $ r $ ) 作為一個因素。
因此，如果 $ gcd(e, \lambda(N))=1 $ ， 然後：
- 對於任何主要因素 $ p $ 的 $ e $ , $ p $ 不是一個因素 $ \lambda(N) $
- 因此，對於任何主要因素 $ p $ 的 $ e $ , $ p $ 不是一個因素 $ \phi(N) $
- 因此， $ gcd(e, \phi(N))=1 $
反之亦然簽證，顯示等效性。