, を相異なる素数とし,
証明:
定理 17.2 を
に対して適用すると,
さて, 証明すべき式は, であるが, 仮定よりある整数 が存在して が成り立つことおよび を用いると, を で割った余りが であることがわかる. 証明おわり.
上のような条件をみたす数の組の例としては, たとえば
RSA 暗号系では, を秘密にし,
を公開する.
を公開鍵, を秘密鍵と呼ぶ.
( は 未満の数) の暗号化は,
さて, これのどこが暗号なんだろうと思った人もいるかもしれない. が公開されているのなら, を素因数分解して, , を求め, をもとめれば, 秘密鍵 がわかってしまうではないか! ここで, 素因数分解は最大公約数 (GCD) の計算に比べて, コストのかかる計算だということを思い出してほしい. , を十分大きい素数にとると, の素因数分解分解の計算は非常に困難になる. したがって , の秘密が保たれるのである.
参考: 量子計算機はこの素因数分解を高速にやってしまうということを Shor が示した. これが現在量子計算機がさかんに研究されている, ひとつの きっかけである.