書記が数学やるだけ#74 フェルマーの小定理

前回は合同式の基本操作を扱った。今回はその応用例として，フェルマーの小定理を紹介する。

問題

過去に京大で誘導なしで問われたことがある。今回は，解説しやすいように丁寧な誘導がついているものを選んだ。

説明

色々と有名なフェルマーの最終定理と区別するため，にあえて「小」定理と称されている。なお，以下の2つの式は同義である。

これをのちにオイラーが一般化したものが，オイラーの定理である。

解法

まず，コンビネーションpCkについてpで割り切れることを示す。定義に則って確認すればよい。

これが証明の核心。二項定理により分解して，コンビネーションpCkを含む項は全てpで割り切れることより，残りが余りとわかる。

あとは数学的帰納法により定理を証明するだけ。

最後にフェルマーの小定理の応用。余りを求めるのに非常に強力な定理であることがわかる。

フェルマーの小定理の応用例として，RSA暗号が挙げられる。RSA暗号とは，桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つであり，1977年に発明され，発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれている。

暗号理論の世界は深遠なもので，機会があれば別に扱いたい。今回はその基礎を提供したということで十分だろう。

本記事のもくじはこちら：