福西です。昨日は2進数の話の延長で、暗号を一つ紹介したいと思い、次のような問題を出しました。
問題
4294967297は、A=□□□で割り切れる。その数で割った商（7ケタ）を入力せよ。
X=□□□□□□□
この数はランダムではなくて、ある法則に基づいた数です。（次稿参照）
問題のヒントは、3ケタの数で割り切れるということなのですが…。
試しに、手計算で7で割ってみました。（以前の経験では7で割り切れることが多かったので）。でも残念、余りが出ました。次に、3でも割ってみましたが、やはりだめでした。
ということで、「本当に割り切れるのかなあ？」という感触からスタートしました。
「じゃあ、500までと、500以上とで手分けしよう」
と、探索を開始する、K君とY君。
二人には、私からは旅の黍団子として関数電卓と、49999までの素数表を渡しておきました。
さて、電卓に100を入力しようとした時、K君もY君もすぐに「あれ？偶数はないんとちゃうか？」と気付きました。
そうです。割ろうとしている数は、4294967297ですが、これは奇数です（1の位が7）。なので偶数で割り切ることはできません。
ということは、A=□□□の1の位は、
「2、4、6、8、0は考えなくてもいい。省ける」
ということが分かりました。逆にいうと、
□□1、□□3、□□5、□□7、□□9
が候補となります。
「じゃあ、1の位が1の場合とか、しらみつぶしに行こう」
ということで、これまた手分けが細分化されました。
「1の位が1の場合はなかった」
「9の場合もなかった」
「7の場合も・・・あれなかった。じゃあ、3か5？」
「そうか。じゃあそれで手分けしよう」
「あれ、でも待てよ。5って、ありえる…？」
と、電卓をたたき続けているうちに、それは「どうやらありえないぞ」という感触に気づきました。理由もすぐにわかりました。
「そっか。1の54294967297って、1の位が7だから、□□5だと割り切れへん数や」
そうです。これも一つの発見です。
補足すると、1の位が5ということは、それ自身が5の倍数となっています。たとえば395は、5×79です。もしそれで4294967297が割り切れるとすれば、5でも割りきていないとおかしいことになります：
4294967297
＝395×B
＝5×79×B。
しかし、4294967297は、1の位が7だから、5の倍数ではありません（5の倍数は、1の位が0か5になるはずです）。つまり4294967297は、□□5では割り切れないということが結論付けられます。
「ということは、残る可能性は、□□3しかない」
ということで、しらみつぶし続行です。
しかし、生徒たちの脳裏には、「これでもし見つからなかったら・・・」という心配もよぎっていました。
そして、
「あれ、だめだ。見つからない」
となりました。
「どこか調べ忘れたのかなあ」
ということで、不安が当たってしまいました。残念ながら、これが「人間のする、しらみつぶし」の弱点です。本当にしらみつぶしができていればいいのですが、それをチェックすることは、かなり難しいです。
ただ、やり直すにしても、
1の位が1、3、7、9に絞れていますので、どれかが正解となります。
そこで、ヒントを一つ出しました。
4294967297=A×X=□□□×□□□□□□7
と、商の方の1の位をオープンにしました。
すると、どう考えたらいいでしょうか。（パズル）
「7ということは、Aの1の位に3はありえない」
「どうして？」
Y君「だって、3の段で～7は、27÷3=9しかないから。だから4294967297=□□3×□□□□□□9になるはず。なので、A=□□3はありえない」
K君「A=□□9もない。9の段で～7になるのは、27÷9=3しかない、だから」
「他の数は？」
「1と7はありえる。つまり、4294967297=□□1×□□□□□□7か、4294967297=□□7×□□□□□□1かの、どっちかになるはず」
ここまでくると、かなり限定されてきました。
でも、これでもまだ、□□1は、9×10×1で、90個。□□7も90個。合計180回電卓を叩く苦労は残っています。
そこで、もう一つヒントというか、（私の失言という形で^^;）強調して、以下の言葉を述べました。
「4294967297は、A×Xの一通りにしか分解できない…あ、しまった」
と。
そこで反応したのが、Y君でした。
「え、一通りってことは…」
「ドキッ」
「Aは素数？」
「ドキドキッ」
「だって、そうやんな！ じゃないと、何かで分解できてしまうから！」
そうです。Y君の言いたかったのは、A=A’×Cとできるならば、
4294967297=A×X=A’×C×X
となり、
A’でも分解できてしまうことになります。でも、それでは今の「一通り」という言い方と矛盾してしまう、ということです。
「じゃあ、こうすればいいんや。素数だけ調べたら！」
と、勢いづくY君。
ということで、最初に渡しておいた素数表が、ここで、やっと日の目を見ることになりました。
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, ・・・（以下50000近くまで）
一見、「うわっ」となりますが…。
でも、Y君は動じず、
「101から997まででいいんや。その間にある、1の位が1と7のやつだけを調べたら。おお、これはめっちゃ限られてくるんちゃう？！」
というわけで、ちょうどいいところで、時間が来てしまいました。
この後の答え合わせは、ぜひ来週。K君とY君には手のひらに書いてもらって、「せーの！」をしてもらおうと思います。
（マニアックなたとえ方になりますが、『三国志』の「赤壁の戦い」にある逸話のように、「同じですな」と言えるのを楽しみにしています）（^^）
追伸
K君が、「4294967297を2進数で表したら、どうなるのかな」と言っていました。それが「鋭い！」と思いました。
これは後の稿で書きますが、4294967297は、実は「2」と、とても関係があります。なので、ぜひK君にはそのアイデアを深めて、何か発見があれば私にも教えてほしいと思います。
（ちなみにこれまでの2進数の勉強では、こんなことをしています。この内容については、またこちらの続きに書く予定です。）