【二項定理】フェルマーの小定理を証明する

次の応用例はフェルマーの小定理です。フェルマーの小定理の証明は、先に階乗を直接使ったやり方をみましたが、ここでは二項定理を用いた方法を確認します。

フェルマーの小定理は、上記の式でした。「法の割り数が素数であり、累乗元の基数とも互いに素であれば、法より1小さい乗数のところで余りが必ず１になる」という内容でしたね。

二項定理を使った証明では、二項係数の性質から導いた以下の合同式を部品に使います。

このうち、下の方の式は「＋1」となっていますが、これは数学的帰納法を使って前後の値を確認するのにうってつけです。そこで、この式に数学的帰納法を適用して、フェルマーの小定理が示す剰余の関係を証明していきます。

はじめに、小定理の元式の両辺に「ａ」をもう一回掛けて、以下のように少し変形しておきます。

そのうえでこの式について数学的帰納法を定石どおりにベタに適用していきます。まず「ａ＝1」のときを確認すると、

次に「ａ＝ｋ」のとき、この式が成り立つと仮に仮定すると、「ａ＝ｋ＋1」では上の二項定理から作った合同式から、

となり、「ａ＝ｋ＋1」でも成り立ちます。よって、数学的帰納法の原理により、以上から元の式は、すべての自然数について成り立つことになります。

さらに、注意する点として、この式は上記の数学的帰納法の証明から、「ａ」と「ｐ」が「互いに素」でなくても成り立つ、ということです。これは証明の元ネタに使った合同式が、累乗の次数が素数であることのみを条件に、二項係数の性質から導いたところからきているもので、元の合同式についても同じです（「p」が素数でありさえすれば、すべてのａ、ｂについて成り立つ）。

それを確認したうえで、ここからフェルマーの小定理に戻るには、最初のステップをもう一度逆につたって、両辺を「ａ」で割らないといけませんが、このとき割り算で元に戻れるのは、合同式の割り算の性質から、「ａ」と「ｐ」が「互いに素」であるときだけです。ここから、上の（※）の式は、すべての自然数について成り立つが、フェルマーの小定理の元の式は、ａ、ｐが互いに素であることが必要という条件が出てきます。つまり掛け算の上りは自由だが、割り算の下りは制約がある、という合同式の特殊な性格がここに反映されているわけです。