大きな素数をもとめて

第1話 素数指数表現

暗い闇の中。私ことルーチンは思い悩んでいた。

なぜだ・・・。なぜかけ算はこんなにも難しいのだ。

和の王とまで呼ばれた私が、こんなにもかけ算に苦しめられるとは？

10年にわたる苦悩のすえ、ついにルーチンは掛け算をしないかけ算を思いついたのであった。

たとえば、84×100はいかにも難しい。

84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84+84と書いてくれればまだわかりやすいものの、いかに和の王と呼ばれた私でもこの計算には少し時間がかかる。だが、まず素因数分解をしよう。

84=2^2×3×7

100=2^2×5^2

そして、積の値は8400である。和の王たる私が時間をかけて計算した自慢の値だ。

これを素因数分解しよう。

8400=2^4×3×5^2×7

よく確認すると、次の法則が見て取れる。

(2^2×3×7)×(2^2×5^2)=2^(2+2)×3×5^2×7

指数の和だけでかけ算ができているではないか！

では、2^2×3×7と書くのは面倒なので、次のように書こう。

(2,1,0,1)

これは、

2^2

3^1

5^0

7^1

を全てかけたもの、という意味だ。ああ、素因数分解さえできればもうかけ算はしなくて済むのだ！なら自然数の表を作ろう。この表が完成すれば、もうかけ算に悩まされることはない。

1=()

2=(1)

3=(0,1)

4=(2)

5=(0,0,1)

6=(1,1)

7=(0,0,0,1)

8=(3)

9=(0,2)

10=(1,0,1)

11=(0,0,0,0,1)

12=(2,1)

13=(0,0,0,0,0,1)

14=(1,0,0,1)

15=(0,1,1)

16=(4)

17=(0,0,0,0,0,0,1)

18=(1,2)

19=(0,0,0,0,0,0,0,1)

20=(2,0,1)

21=(0,1,0,1)

22=(1,0,0,0,1)

23=(0,0,0,0,0,0,0,0,1)

24=(3,1)

25=(0,0,2)

26=(1,0,0,0,0,1)

27=(0,3)

28=(2,0,0,1)

29=(0,0,0,0,0,0,0,0,0,1)

30=(1,1,1)

31=(0,0,0,0,0,0,0,0,0,0,1)

32=(5)

33=(0,1,0,0,1)

34=(1,0,0,0,0,0,1)

35=(0,0,1,1)

36=(2,2)

...