airheadの日記: memo: 101
(2008/11/12 00:30 Binary 2008より、鴨志田さんの出題とその答えを読んで / 関連エントリ)
...なるほど、そういうことか。確かに1010...1(4n+1桁、nは1以上の整数、「1」の個数は2n+1)は素数ではなく、全ての桁が「1」である2n+1桁の数を約数に持つ。
「p進数(pは2以上の整数)」が関係するのは、前出の2n+1桁の数で割って得られる約数。2進数の「1」、8進数の「7」、10進数の「9」、16進数の「F」などのような、p進数の表記に用いられる最大の数字を仮に「Z」とすると、
1 = 1 * ( 1)
10101 = 111 * ( Z0 + 1)
101010101 = 11111 * ( Z0Z0 + 1)
1010101010101 = 1111111 * (Z0Z0Z0 + 1)
:
となる(n=0の場合の1=1*1はもちろん素数ではないが、参考として最上段に併記した)。例として16進数 1111111 と F0F0F1 の乗算を見てみよう。
1111111
* F0F0F1
---------------
1111111
FFFFFFF
FFFFFFF
+ FFFFFFF
---------------
1010101
FFFFFFF
1
FFFFFFF
1
FFFFFFF
+ 1
---------------
1010101
10000000
10000000
+ 10000000
---------------
= 1010101010101
これは、何進数であろうとも、「1」が奇数個という条件においてなら何桁に増えようとも成り立つ。ここに素数はない。
また回答(a)にある通り、何進数であろうとも、「1」が偶数個なら「101」「101 0101」「101 01010 ... 0101」となるわけで、「101」で割り切れるのは明らかだ。
というわけで、素数の可能性はp進数101(=p2+1)にしかない(さらに言えば、pが奇数の場合にはp2+1が偶数になってしまうので、奇数進数の1010...1に素数はない)。