フェルマーの小定理が純粋数学の枠を飛び出し、世界のインフラとして定着した決定打が公開鍵暗号「RSA暗号」の発明です。1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エードルマンの3名によって考案されたこの暗号系は、オイラーによる小定理の一般化（オイラーの定理）を数学的基盤としています。
RSA暗号が成立する決定的なカラクリ
RSA暗号では、巨大な2つの素数 $p, q$ の積である合成数 $N = pq$ を公開鍵の一部とします。オイラーのトーシェント関数 $\phi(N)$ は、互いに素な自然数の個数を表し、素数の積であれば $\phi(N) = (p-1)(q-1)$ と簡潔に求まります。
暗号化鍵 $e$ と復号鍵 $d$ は、$ed \equiv 1 \pmod{\phi(N)}$ を満たすように設計されます。送信者が平文 $M$ を暗号文 $C \equiv M^e \pmod N$ として送信した際、受信者は手元の秘密鍵 $d$ を用いて以下のように平文を復元します。
$$C^d \equiv (M^e)^d = M^{ed} = M^{1 + k\phi(N)} \equiv M \cdot (M^{\phi(N)})^k \equiv M \cdot 1^k \equiv M \pmod N$$
ここで $M^{\phi(N)} \equiv 1 \pmod N$ と変換できる根拠こそが、フェルマーの小定理を合成数へと拡張したオイラーの定理です。素因数分解の困難性を安全性の根拠にしつつ、復号の成立そのものは小定理の系（発展形）に完全に依存しています。私たちがスマートフォンで行うクレジットカード決済やSSL/TLS通信の裏側では、アクセスするたびにフェルマーの着想が実行されているのです。
競技プログラミングにおける「余り計算」とモジュラ逆元
一方、情報科学を学ぶ学生やソフトウェアエンジニアが直面する最も身近な応用例が、競技プログラミング（AtCoderなど）における「巨大な組み合わせ数の余り計算」です。組み合わせ記号 $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ などの計算では、答えが天文学的な数値になるため、問題文で「$10^9+7$ や $998244353$ で割った余りを求めよ」と指定されるのが通例です。
しかし、合同式の世界では足し算・引き算・掛け算はそのまま行えますが、割り算（除算）をそのまま実行することはできません。そこで除算を乗算に変換するために「モジュラ逆元（法の下での逆数）」を用います。ある数 $b$ で割る代わりに、$b \times x \equiv 1 \pmod p$ となる $x$（逆元 $b^{-1}$）を掛けるのです。
ここで法 $p$ が素数である場合、フェルマーの小定理より以下が導かれます。
$$b^{p-1} \equiv 1 \implies b \times b^{p-2} \equiv 1 \pmod p$$
つまり、$b$ の逆元は単に $b^{p-2}$ を計算するだけで得られるのです。繰り返し二乗法（バイナリ法）を用いれば、わずか $O(\log p)$ の計算量で除算の逆元が手に入ります。拡張ユークリッド互除法を書く手間に比べ、わずか数行の実装で正確な剰余演算が完了するため、競プロ界隈における必須の基本テクニックとして定着しています。
