【数の構成】合同式で遊ぼう〜掛けてもいいなら割ってもいい?

ここまで合同式のモジュラー演算について、足し算・引き算・掛け算については、あたかも等式であるかのように扱えることをみてきました。では「割り算」も同じようにやっていいでしょうか?ふつう一般の等式の場合は、掛け算と割り算は逆の演算で互いに逆戻りすることが保証されていました。ところが合同式では割り算はそのまま自由に行ってはいけません

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

なぜ合同式は割り算をしてはいけないか

その理由は、もともと合同式というものが、「包含除」の割り算をベースに、整数の倍数に余りというしっぽがついた数のセットを扱うものだからです。足し算、掛け算のように、「増える」タイプの計算のときには、このセット一式が形を保ったまま、増殖したり、しっぽが延びたりします。引き算の場合は「減らす」操作ですが、減り方が両辺でスライドして同じなので、合同関係も維持されるということでした。

ところが、ここで言う合同式に対する割り算というのは、両辺の数を全体としてみたときに、たまたま共通の約数が含まれているので、それを「等分除」の考え方で分数の約分のように均等割りして数を小さくする、ということです。それは数を構成する「倍数+しっぽの余り」というセット一式を無視して行う操作なので、(ふつうは)そのセットは包丁が入って壊れてしまいます。ですから掛け算はできても割り算はできないのです。

たとえを用いていえば、ちょうど列車の車両を思い浮かべるといいかもしれません。鉄道の車両は一両だけでもいちおうは鉄道車両に変わりはなく、増やす分には同じものを何台かつなげても機能は同じです。ですが、そうやって増やしていいからといって、一台の車両を内側に分解しても機能が残るか、というとそうではありません。機能を保つために必要な最低限の単位があるのです。

実際の例でみてみましょう。次のサンプルでは両辺は合同であるのとともに、共通の約数も持っています。が、だからといって公約数で割っても合同関係が維持されるかというと、明らかにそうは問屋が卸しません。

合同式の演算公式

共通の約数で割るという操作が、合同式のベースにある包含除の余り付き割り算とはまったく異なる仕方で数を整地するものだ、ということがよく分かる例です。


石橋を叩いてから渡る

ふつうの等式の場合には、掛け算ができることで自動的に逆側の割り算も保証されるので、行くのはいいが戻るのは好きにできない、という合同式のこの特殊な性質は、いまひとつ感覚がつかみにくいところがあります。また、先に書いたように、合同式の例題ではとてつもなく大きな数の余りを出しなさい、というものがよく出されますが、このとき割り算を駆使して数を自由に小さくできないというのは正直不便を感じます。

合同式の演算公式

では、どうしたらいいでしょうか?掛け算の向きはOKですから、いちど掛け算の石を投げて自分自身に戻って来れることを確認してからその道をつたって渡る、というやり方をとります。ちょうど、先に斥候(せっこう)を派遣して安全に渡れることを確認してから本隊が進むようなものです。合同式の解説では、いきなり計算式の遷移が並べられていて、ここのところがはっきり書かれていないものが多いですが、注意深くみると、必ずこの手順を踏んでいることが確認できます。


両辺を割ってもいい場合

このように合同式では割り算については機械的に常に保証されるわけではありませんが、割ってもいい場合もあります。それが以下のケースで、これが合同式の割り算の公式になります。

合同式の演算公式

上式で、gはcとnの最大公約数(greatest common divisor/GCD)を指しています。従って、この式は以下のふたつの意味を持ちます。

  • 両辺の約数cと法nが「互いに素(最大公約数が1)」ならば、cで割ってもよい
  • 両辺の約数cと法nが約数を持つときは、法nがn/gに変わってもよければcで割ってもよい

実際の値を入れてみてみましょう。以下の例は、両辺の公約数と法が互いに素の場合です。この場合は、約数で割っても合同関係が維持されているのが分かります。

合同式の演算公式

次は、両辺の公約数と法がGCDを持つ場合です。この場合は、そのままcで割ると合同関係が壊れてしまいますが、法をGCDで割った新しい法については、合同関係があります。

合同式の演算公式

なぜ、このような関係が成り立つのか、式で証明してみましょう。

合同式の演算公式


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

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