【数の構成】合同式で遊ぼう〜100乗問題を解く�T

それではここから実際に、これまでみてきた合同式の機能を使って「××の100乗の余りを求めよ」というタイプの例題をやってみましょう。これは別に10乗でも1000乗でもかまわないのですが、100乗くらいが手頃のようなので、仮にこういう呼び名にしておきます。

それはたとえばこういう問題です。いくら合同式の考え方と公式を覚えたといっても、いきなりこれを渡されて解け、と言われたらどうしていいか困ってしまいますね。この設問は、次の2つのポイントをとっかかりにして取り組みます。

それは、（1）累乗される元の数と「法」の関係に着目する／（2）差分の「1」を探す、という2点です。この問題では、累乗される「9」と法の「8」との差がちょうど1ですので、まず次の合同関係が設定できます。

次にこの両辺累乗の公式を使って100乗すると以下のようになり、余りが出ます。余りは1です。1はいくら累乗しても1のままなので、1を探すというのはこういう意味です。

どうでしょうか。合同式の公式があるのであっさり答えが出ていますが、もともとの問題を考えると、まるで孫悟空の「きんと雲」で空のはしからはしまでをひとッ飛びしたような、ものすごい計算です。同じ要領で次の問題をやってみましょう。

この問題では、累乗される数と法との差分は1ですが、法の方が大きくなっています。そこで、負の値の合同式を使って、「7≡0」をマイナス1だけスライドさせて以下の合同式を得、これを100乗してやはり余りは「1」となります。

このようにマイナスの側にずらすことで「−1」も使えるようになり、便利な「1」の使いでが2倍に増えるところが、負の値の合同式の威力です。この「−1」の意味については、追って以下で検証します。その前にもう一問やってみましょう。

この問題では、累乗元の数と法の「6」との差は「7」ですが、6を法とした余りは「6×2+1＝13」で「1」となります。従って、以下のようになり、100乗の余りも「1」となります。

「＋1」と「−1」の意味

上に見るように、100乗問題を解くには差分の「1」と「−1」をうまく使いこなすのがコツです。そこでこのタイプの合同式の性質を調べておきましょう。下記は、適当に幅をとった法の間で、法自身の値をもつ合同式を、＋1側と−1側にそれぞれ1づつスライドさせたものです。

このうち、右側の「＋1」側については、右辺が1ですから、何乗しようが法に対する左辺の余りは1ということになります。いくつかみてみましょう。横の値は実際の計算値で、カッコ内は法に対する余りです（電卓で検算してみてください）。

一方、左側の「−1」側については、同じように考えると、「−1」ですから偶数乗のときは余りが「1」ですが、奇数乗のときは「−1」となります。「−1」ということは、法の数から1引いた値（元の合同式の左辺の値）が余りになるということです。

このように、「＋1」側は、偶数乗・奇数乗にかかわりなく何乗しようが常に余りは1ですが、「−1」のときには、乗数を上げていくと、「1」と「法−1」の余りがかわるがわる現れることになります。上の例題の場合には、たまたま100乗で偶数乗だったので「1」だった、というわけです。面白いですね。

100乗問題、もう少し続けます。ここまではまだ肩慣らしで、余りが1のときしか解けない、というわけではありません。