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

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

この節を最初から読む
この節の目次にもどる

フェルマーの小定理

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

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

二項係数と素数

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

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

フェルマーの小定理を二項定理と数学的帰納法で証明する

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

フェルマーの小定理を二項定理と数学的帰納法で証明する

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

フェルマーの小定理を二項定理と数学的帰納法で証明する

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

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

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

合同式の除法

ちなみに、変形式から元の式に割り算で戻れる(互いに素である)ときと、戻れないとき(互いに素でない)ときを、具体的な数値の例で確認しておきましょう。

フェルマーの小定理を二項定理と数学的帰納法で証明する

フェルマーの小定理の証明は、この、二項定理と数学的帰納法を合わせ技に使った方法がもっともオーソドックスなものとされているようです。上記のようにちょっとした注意点はありますが、証明の本体部分の簡単さをみると、数学的帰納法が強力で便利な方法であることが、あらためて実感できる例になっています。


posted by oto-suu 13/05/18 | TrackBack(0) | 二項定理 | このブログの読者になる | 更新情報をチェックする
<< 前のページ | TOP | 次のページ >>

この記事へのトラックバック