【数の構成】「ウィルソンの定理」とその証明

前回のフェルマーの小定理の証明では、階乗の計算は助っ人で来てもらって、用が済んだら最後は両辺から払って帰ってもらいましたが、この素数の余りから作った階乗の数自身が、除数の法に対してどういう関係にあるのかも、ついでに調べておきましょう。

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

例として、前回使用した、素数の 5 を法/除数とした場合のケースで考えます。余りはいくつでしょうか?

ウィルソンの定理

これを考える際に、左辺の階乗の計算を、次のように並べ替えることが参考になります。

ウィルソンの定理

こうすると、「4×1」は 4 で、法の 5 に対しては剰余「-1 (5-1)」です。また同様に、「3×2」は 6 で剰余「1 (5+1)」です。すなわち、全体の余りは「-1×1」で「-1」となります。

実は、法/除数が素数のときには、この並べ替えは常に行うことができます。頭のあたりでいくつかみてみましょう。

ウィルソンの定理

つまり、このパターンでは余りは常に「-1」になるということです。文章で書けば、法の素数に対して、それがとりうる余りで作った階乗は、余りが「-1」になる、となります。また、言い方を変えれば、この階乗の値は「+1」すると、法の素数で必ず割り切れる、とも言えます。この階乗と素数の剰余の関係を表す法則を「ウィルソンの定理」といいます。一般化した形で書くとこうです。

ウィルソンの定理

ウィルソンの定理は、フェルマーの小定理ほど有名ではなく、なんの役に立つのかもちょっとよく分からない内容ですが、小定理に劣らず美しい形ですし、素数階乗というそれぞれ特殊な数ふたつを、剰余を仲立ちにつないでいる点で、純粋に数の性質や不思議さを楽しむうえでとても面白い性質といえます。素数は自分自身と1以外の約数を持たない数であり、階乗は逆に自分以下のすべての数を約数に持つ数です。このうち、階乗の側については、(P-1)より大きくしてしまうと、法の素数自身が入ってしまって割り切れてしまいますから、「自分の余りで作った」というところがミソです。



ウィルソンの定理が成り立つ原理

階乗と素数の間でこの性質が成り立つのは、上記のように、素数が法の場合には、階乗の中身を剰余が「-1×1」になる組み合わせに必ず並べ替えられることが前提になっています。なぜこれが成り立つのかは、前回のフェルマーの小定理の証明を応用することで理解できます。

フェルマーの小定理の証明では、素数の余りに「互いに素」の数をかけて作った合同式のセットは、余りがバラバラに1回づつ入る、という指摘が核になっていました。前回は、5 と 7 という数の組みでこれを確認しましたが、これは法より小さい数でもまったく同様に当てはまります。法/素数を「7」として、いくつかみてみましょう。

ウィルソンの定理の証明

このケースでもたしかにそうなっていますね。これを仮に「ルール1」とすると、この合同式のセットには、他に次のいくつかの規則性が指摘できます。まずそのひとつは、この階乗のそれぞれの要素は、同じ余りの範囲の中で、掛け合わせると剰余が「1」になるペアーを必ず見つけることができる、というものです。これは「ルール1」を剰余の側からみて言い換えただけです。これを「ルール2」とします。また、(a)を変えながら、同じ行についてみると、剰余の「1」は必ず1度だけ出る(2度は出ない)、ということもいえます。これも「ルール1」を言い換えたもので、もし2度以上出るのであれば、フェルマーの小定理の証明でみたように、同じ因数を持つ合同式の間で割り算ができることになってしまいますので、矛盾が生じるからです。これを「ルール3」とします。

次に上図で、いちばん上の行と最後の行の「1」と「6」に注目します。この行では「ルール2」「ルール3」から、1度だけでる「1」の剰余は、それぞれ自分自身を掛け合わせたとき、すなわち「1×1」と「6×6」のとき、で決まっています。なぜかというと、「1」「6」はそれぞれ自分自身が既に剰余「1」と「-1 (P-1)」なので、剰余「1」を作る組み合わせはそれしかないからです。

ウィルソンの定理の証明

これを残りの「2〜5」についてみると、最上行と最終行については、既に「×1」と「×6」で「1」の目を使ってしまっていますので、(a)に「2〜5」をいれたときに剰余が「1」になることはない、ということになります。これは裏返せば、真ん中の「2〜5」の行において、剰余の「1」を作る相手側の候補に最初の「1」と最後の「6」が来ることはない、という意味です。これを「ルール4」とします。

さらに、この真ん中の「2〜5」の行において、「1」「6」の行のときと同様に、自分自身と同じ数が来た場合のケースを考えます。実はこのパターンでは(「1×1」と「6×6」のときとは反対に)剰余に「1」の目が来ることは絶対にありません。なぜかといえば、もしこの場合に剰余が「1」であれば、以下の合同式が成り立つことになりますが、

ウィルソンの定理の証明

これは変形して上のようになります。これはすなわち、「2〜5」の行において、「+1」「-1」にずらした数を掛け合わせた数が素数「P」で割り切れることを意味しています。しかし、上記の階乗から作った合同式のセットで、最上行と最下行をカットした「2〜5」の候補が「+1」「-1」にずらした範囲で(「2−1=1」以外に)法の素数の因数になることはありえませんから、これはおかしい、ということになります(たとえば「mod 7」で「4×4」をそれぞれ「+1」「-1」にずらした「5×3」や、「2×2」をずらした「3×1」が「7」で割り切れることはない、ということです)。結局、この範囲で一度きり出る「1」の目は、同じ数が掛け合わさったパターンからははじかれることになります。これを最後の「ルール5」とします。

この「ルール1」から「ルール5」までを全部足し合わせると、この合同式のセットで、いちばん上といちばん下を取り除いた「2〜5」の行は、剰余が「1」になるペアーを、それぞれが相手側も「2〜5」の範囲で、自分自身以外に必ず見つけることができる、となります。残った最上行と最終行は互いに組み合わせれば必ず剰余「-1」ですので、これでウィルソンの定理が成立する前提がめでたく確保された、というワケです。

まるで参加した者はひとりも「壁の花」になどならずに、全員無事きれいにペアーに分かれるよう、素数という主催者があらかじめ仕組んでおいた心憎いダンスパーティーのようですね。


<参考にさせていただいた資料>
  Wilson's theorem ( Wikipedia )
  Wilson's theorem ( Numericana )


posted by oto-suu 11/10/11 | TrackBack(0) | 数の構成 | このブログの読者になる | 更新情報をチェックする
<< 前のページ | TOP | 次のページ >>
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/291353426
※ブログオーナーが承認したトラックバックのみ表示されます。

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