数学ガールの秘密ノート/整数で遊ぼう

先日、以下のようなツイートをしたところ、

#素数夜曲「孫子剰余定理」面白いですね。
— Ⓜⓐⓢⓐⓗⓘⓓⓔ Ⓜⓐⓔⓗⓐⓡⓐ (@maehrm) 2020年7月28日

結城浩さんより以下のようなツイートをいただきました。

「ぐるぐるワンの作り方」と関係ありです😊https://t.co/yfyvTuuKSo
— 結城浩 (@hyuki) 2020年7月28日

『数学ガールの秘密ノート』シリーズは全て読んでいて、読み終えるたびに感想を拙ブログに書いていたつもりだったので、読み終えた当時の自分はどんな感想を残していたのか調べてみると本書だけ書き忘れていたようです。

「ぐるぐるワンの作り方」は本書の第5章ですが、今回、読み返してみて中国剰余定理(孫子剰余定理)を見事に、簡単に、数式を使うことなく説明されているなと、今更ながら感動してしまいました。

中国剰余定理については、以前プログラムを作って学習したことがあるのですが、理解を定着させるために、以下の問4を「ぐるぐるワン」方式で解いてみたいと思います。

上式は、「第5章ぐるぐるワンの作り方」の問題に置き換えると、

7の時計、9の時計、11の時計があります。カウントボタンを何回押せばパターン321になりますか。

という問題と同じになります。

まず、7の時計の針だけを1進めることを考えます。カウントボタンを9x11=99回押すと、9と11の時計の針を進めずに(実際はクルクル回っているのですが)、7の時計の針だけを1進めることができます。

次に、9の時計だけを1進めるためには、7x11の77回を考えますが、これだと9の時計が5進むことになりますので、77x2の154回カウントボタンを押すと、9の時計の針を1だけ進めることができます。

最後に、11の時計の針だけを1進めることを考えるのですが、7x9の63回を7セット、つまり63x7=441回押すと11の時計だけを1進めることができます。

以上により、パターン321を作るためには、

99x3+154x2+441x1 = 1046

となり、1046回押せばいいことになります。しかし、この時計は、7x9x11=693で3つの針が再び000を指すことになりますので、

1046 ÷ 693 = 1 ... 353

となり、353回カウントボタンを押せばいいことになりますね。当たり前ですが、「中国剰余定理 - Mae向きなブログ」で求めた答えと同じになりました。それぞれの時計の針をイメージすることで中国剰余定理の理解がより深まったような気がします。