1009はどんな数
松谷です。
土曜日に、振替をしている生徒の1人が授業内容を、終えてから１つプリントを見せてくれました。
広中杯とかいう算数オリンピックの中学生版です。
あまり時間がなかったので、2問くらいしか答えられなかったのですが、なかなか楽しげな問題が並んでました。
知識をあまり問うわけではなく、考えさせるって感じの問題でした。でも、制限時間も厳しいので、頭をフル回転させて考えなければならないといった感じでしょうか。
その中に2018を素因数分解することがキーになる整数問題がありました。
まずは、もちろん、2×1009までやります。
そこからです。
1009の素因数分解ですね。
さて、どうでしょうか。
2で割れない。
3で割れない。
5で割れない。
7で割れない。
11で割れない。
13で割れない。
むむむむ。。不穏な空気が。。。
32かける32で1024と既に1009を超えてますから、31までの素数で試しに割り算してみてやればいいですね。
もし、1009が大っきい素数どうしの積で表せていたとしたら1009=A×Bとなりますが、AとBのどちらかが31以下でないと、1009になりえませんからね。
そして、試していくと、、
17、19、23、29、31いずれもだめ。
そう、
1009は素数だったんですね。
めでたく問題が解けたというわけです。
さて、まあ、今回は、原始的な方法でやりましたが、高校以降の数学の世界でも素数は大きな興味の対象で、
様々な素数であるかを見極める判定法、アルゴリズムが考えられています。
それでも、結構大きな素数だとコンピュータを使っても判定に時間がかかったりするようです。
そんな素数の難しさは、素因数分解の難しさとリンクしてるわけで、それは暗号などでよく使われているそうです。
1282881263=13297×96479
こんな式の左側を与えておいて、右側を、導くのは結構大変そうですよね。
実際には、これはコンピュータにとっては一瞬らしいですが、100桁とかだとコンピュータでも大変だそうですよ。
素数が好きな人は素数Tシャツなんていうのも売られているそうですから、買ったらいいかもしれません。。たぶんモテないと思いますが。。