フェルマーの小定理

フェルマーの小定理

合同式の「100乗問題」を扱った際に、「1」を探すのがコツという話がありました。このようなケースで、累乗しながら「1」を探していくと、ある規則性がみえてきます。それが「フェルマーの小定理（Fermat's little theorem）」 と呼ばれるもので、合同式の関連では最も有名な定理です。

 

フェルマーの小定理は上のような格好をしています。法の割り数が素数 （prime number）であり、累乗元の基数とも「互いに素」であれば、法より1小さい乗数のところで余りが必ず１になる、という内容です。値を入れ替えながらいくつか実際に見てみましょう（電卓の用意をどうぞ）。

確かにそうなっています。今度は累乗元の数を固定して、「法」の素数の方をずらしてみましょう。

成立していますね。100乗問題でみたテクニックとともに、この「1」は使えます。この定理を使うと、たとえば次のような問題が剛速球で解けます。

もういっちょういきましょう。

「フェルマーの小定理」の「フェルマー」は、あの有名な「フェルマーの最終定理」と同じ、スーパースター数学者のフェルマーさんです。没後にノートの書きつけが公表されて以来、300年以上誰にも解けず、もともと解けないのでは、と言われていたところ、1995年に証明法が解明されて大騒ぎになった「最終定理」と区別するために、こちらの合同式に関する定理は「小定理」と呼ばれています。「最終～」とちがって、こちらの方の証明はそれほど難しくないそうなので、この場所でものちほどチャレンジしてみます。

フェルマーの小定理と循環小数

ところで、この小定理で、累乗元の数の方を固定した上の検証において、基数を「10」にとってどうなるかをみてみます。

すると、左側の、余りを引いて割った「商」の部分に、なにやら見たことのある数が出てきました。そう、これは循環小数（純・循環小数）の循環節の数です。

「10の累乗に対して1余る数」というのは、「9999...」の数を割り切れる、ということと同じですから、フェルマーの小定理は、循環小数の組成と深くからみ合っています。

上の例でみると、「mod 7」ではナマの循環節そのものが現れていますが、他のケースでは循環節の繰り返しが出ています（「13」のケースでは「076923」が2回繰り返されています）。ここから、次のふたつのことを読みとることができます。

• フェルマーの小定理は余りが1になる乗数を指示するものではあっても、循環節を作るその「最短」の乗数を示すものではない
• 循環節を作る「最短」乗数はフェルマーの小定理が指定する乗数自身かその「約数」のどれかになる

上の例では、「mod 11」のときに10の2乗、「mod 13」では6乗で最短で1と合同となり、これが循環節になります。このカタマリをまるごとさらに累乗したものも余り1ですから、指数を整数倍したそのどこかが小定理の要求する乗数にヒットするという構造です。

純・循環小数の循環節の長さを順々に調べていくと、対応する分数の分母（割り数）の素数から1小さい数とその1/2などの約数が並ぶ様子が観察できます。この土台にはフェルマーの小定理があります。合同式の剰余演算と循環小数が底のところで深くつながっていることがよく分かりますね。