Weekend Mathematics／問題／問題31
３１．素数の問題
悩め！パスラ−(挑戦その１)
アンジェラ・フォックス・ダン編
啓学出版
（ペンネ−ム：さだやん）
一の位が偶数のものは2の倍数ですから素数ではありません。
残りのうち，一の位が5のものは5の倍数ですから素数ではありません。
その残りの下の位は
9，987，9876543，987654321，……
の繰り返しですが，いずれも，3の倍数で，上の位 987654321×（10の累乗）もまた
3の倍数です。
以上により，
あるものは，2や5の，他のものは3の倍数になり，素数はなし。
答え 解なし
感想
ぱっと見て，「これは私には無理」と思いました。
無限に続くとなると一般解になりそうで私の能力を超えると思ったのです。
それで,一番小さい素数を見つけて,「努力賞」をねらうというか誠意を見せよう？と
思いました。
ところが，繰り替えし部分は3の倍数になること，下の位は2か3か5の倍数になり0個
とわかりました。
「取りあえず，やろうとしてみる」のがよかったと思います。
実際，これで，もし，
一番小さい素数が見つかったとしたら，私には手に負えなかったでしょう。
（ペンネ−ム：Chee）
[解答]
まずは、２つばかり補題を
（当たり前で(？)補題というのもおこがましいので、証明は後で）。
補題１）
３つの連続する数（とりあえず１〜９に限定）から作られる数は３で割り切れる。
たとえば、９８７や６５４など。
補題２）
３で割り切れる数の後ろに、３で割り切れる数を続けて作った数は、
３で割り切れる。
たとえば、３の後ろに９を続けてつくった３９など。
まず、９（３で割れる）も９８（２で割れる）も素数でないので、
９８７以降の数列について考えます。
つまり、３桁以上を想定します。
ここで、与えられた数列のそれぞれの数を、
「上の桁から３桁ずつ区切り、あまった下の桁の数」で分類すると、
数列の規則（９〜１を繰り返し使う）より、次の６つのグループに分かれます：
最後の桁が、９，９８，６，６５，３，３２ ・・・これを「最後の桁」と呼
ぶことにします。
さて、補題１より、最初の３桁は、３で割れますし、
以降の３桁づつ区切った分もそれぞれ３で割れるので、
補題２より、結局「最後の桁」が３で割れるかどうかで、
その数が３で割れるかどうかが確定します。
最後の桁が３で割れるのは、９，６，３の３つのグループです。
また、最後の桁がないもの（３桁ずつ区切りきれたもの）は、補題１と補題２より、
３で割り切れます。
結局、最後の桁が９８，６５，３２のもの以外の（数列中の）
すべての数は３で割り切れてしまいます。
残った３つのグループは、下１桁が偶数と５なので、
いずれも２か５で割り切れてしまいます。
結果、この中に素数はありません。
＃ あれ？
[補題１の証明]
３桁の数を「ABC」と書いたとします。
｢ABC」 = A×100+B×10+C = A×99+B×9+(A+B+C) = 3×(A×33+B×3)+(A+B+C)
A,B,Cのうち最小の数をaとすると、のこりの２つはそれぞれ、
a+1,a+2 となり、
A+B+C = a+(a+1)+(a+2) = a×3+3 = 3×(a+1)
結局、「ABC」 = 3×(A×33+B×3)+3×(a+1) = 3×(A×33+B×3+a+1) となり、３で割り
切れる。
[補題２の証明]
くっつける前の数をAとし、くっつけた数をBとして、Bの桁数をｋとすると、
作った数は、
A×10k + B
AもBも３で割り切れるので、それぞれ 3×a, 3×b とおくと、
A×10k + B = 3×a×10k + 3×b = 3×(a×10k+b)となり、３でわりきれる。
＃ 小学校のころ、
（ペンネ−ム：浜田 明巳）
連続する３ｎ（ｎは自然数）個の整数の和は３の倍数である．
したがって素数の候補として，
これは１００００００桁以下の数列内に素数の候補
（＝奇数であり、３の倍数でなく、５の倍数でない数）
があるかどうかをチェックするプログラムです。
Sub sosuu()
Dim max, a(1000000) As Long: max = 1000000
Dim wa, kosuu, j, jj As Integer: wa = 0: kosuu = 0
For j = 1 To max
a(j) = 9 - ((j - 1) Mod 9): wa = (wa + a(j)) Mod 3
If wa > 0 And a(j) Mod 2 = 1 And a(j) <> 5 Then
kosuu = kosuu + 1
For jj = 1 To j: Selection.TypeText Text:=a(jj): Next
Selection.TypeParagraph
End If
Next
If kosuu = 0 Then
Selection.TypeText Text:=Str$(max) + "桁以下の数には，素数はありませんでした．"
Selection.TypeParagraph
End If
End Sub
実行した結果、
「 1000000桁以下の数には，素数はありませんでした．」が表示されました。
（ペンネ−ム：ちゃめ）
（答え） 素数は存在しない。
（T）２は数列のメンバーではない。
（U）１の位が２，４，６，８である、
数列のメンバーは２の倍数であることにより、
１の位が５であるメンバーは５の倍数であることにより、それぞれ素
数ではない。
（V）１の位が、１，３，７，９の場合を考える。
「ある自然数が３の倍数である必要十分条件は
その数の各位の数字の和が３の倍数である」ことは既知とする。
（ペンネ−ム：ものもの）
偶数および１の位が５の自然数は素数でないことは明らか、
よって、１の位が１、３、７、９の場合について考える。
| ９８７・・・１９８７・・・１・・・９８７６５４３２１ | |
| ＝ | ９８７６５４３１×１０a＋９８７６５４３２１×１０b＋・・・＋９８７６５４３２１ |
| ＝ | ９８７６５４３２１×（・・・） （各項、９８７６５４３２１が約数なので） |
| ９８７・・・１９８７・・・１・・・９８７６５４３ | |
| ＝ | ９８７６５４３２１×１０a＋９８７６５４３２１×１０b＋・・・＋９８７６５４３ |
| ＝ | ３×（・・・） （各項、３が約数なので） |
| ９８７・・・１９８７・・・１・・・９８７ | |
| ＝ | ９８７６５４３２１×１０a＋９８７６５４３２１×１０b＋・・・＋９８７ |
| ＝ | ３×（・・・） （各項、３が約数なので） |
| ９８７・・・１９８７・・・１・・・９ | |
| ＝ | ９８７６５４３２１×１０a＋９８７６５４３２１×１０b＋・・・＋９ |
| ＝ | ３×（・・・） （各項、３が約数なので） |
（ペンネ−ム：まめ）
このような無限数列中に素数はない。
【理由】まず、９〜９８７６５４３２１までで考えてみます。
下一桁が偶数と、５は素数ではないのでのぞきます。
残ったのは、９、９８７、９８７６５４３、９８７６５４３２１
これらの、各位の和をとってみると、９、２４、４２、４５
となり、いずれも３の倍数であることがわかります。
従って、９〜９８７６５４３２１は、偶数か、３の倍数か、５の倍数のい
ずれかで、結局この中に素数はありません。
さて、以上の結果、９８７６５４３２１は３の倍数ですから、
これに１０のｎ乗をかけたものも３の倍数です。
つまり、９８７６５４３２１以降の数列は、常に「○○＋３の倍数」
という形を持っていることになります。
これ以降も、下一桁が偶数と５の数字をのぞけば、下の桁は
９、９８７、９８７６５４３、９８７６５４３２１
のいずれかであり、これらはいずれも３の倍数です。
これに３の倍数を加えるわけなので、
できあがった数もやはり３の倍数であるはずです。
以上の考察より、この無限数列には素数は存在しません。
（ペンネ−ム：ふー）
まずは９〜９８７６５４３２１までの１巡について、
９（３の倍数）
９８（偶数）
９８７（３の倍数）
９８７６（偶数）
９８７６５（３の倍数）
９８７６５４（偶数）
９８７６５４３（３の倍数）
９８７６５４３２（偶数）
９８７６５４３２１（３の倍数）
２巡目以降は
・・・９＝３の倍数×ｎ＋９＝３の倍数
・・・９８＝偶数
・・・９８７＝３の倍数×ｎ＋３の倍数＝３の倍数
・・・９８７６＝偶数
・・・９８７６５＝３の倍数×ｎ＋３の倍数＝３の倍数
・・・９８７６５４＝偶数
・・・９８７６５４３＝３の倍数×ｎ＋３の倍数＝３の倍数
・・・９８７６５４３２＝偶数
・・・９８７６５４３２１＝３の倍数×ｎ＋３の倍数＝３の倍数
このように必ず２、または、３の倍数となるので素数は無い！！
３の倍数かどうかを判断するための考え方、
「各位の数の和が３の倍数であればよい」を知っていたのでわかりました。
（ペンネ−ム：Chee）
これは、「整数：a,b,cが等差数列になっていて、
a×b×cが素数になるもの」という意味で良いのでしょうか？
そう解釈して以下進みます。
[解答]
素数の約束から、因数（の絶対値）が１とただ一つの
素数しかあってはいけないので、
a,b,cのうち、一つだけが（絶対値が）素数で、
あとの二つは１もしくは−１（絶対値が１）。
絶対値が１のものが、どちらも１（または−１）だと、
等差数列の条件から３番目の整数も１（または−１）となり、
積の結果も１（または−１）で、素数にならない。
結局、a,b,cは、「−１、１、（絶対値が）ある素数」から選ぶことになる。
−１と１の間には素数がないことと、−１と１の差分が２であることに注意すると、
「（絶対値が）ある素数」となる整数は、−３。
結局求める数列は、「−３、−１、１」で、積は３。
＃ ところで、素数ってのは、２以上だとしていいんですよね。
（ペンネ−ム：さだやん）
解 -a,-1,1
とおくと，-1-（-a）=1-(-1)＝公差 a:素数
なので，a=3
答え -3，-1，1 （または1，-1，-3）
感想
ぱっと見て，「これは無理」というか，「解なし」と思いました。
気をとりなして考えてみました。
等差数列ということから， a-d, a, a+d
素数ということから， 1，1，a
ふうむ。 -1×0×1＝0 ?????
でもないし，…………
あっ，そうか。 a, -1, 1 とおくと 公差が2だから，a=-3
解けてみると，それほど難しくないような気になってしまうから不思議。
（ペンネ−ム：ちゃめ）
３整数のなす等差数列の公差をｋ（０でない整数）とし、
３つの整数を n-k, n ,n+k とする。
この３数が題意を満たせば、n+k, n, n-k も題意を満たすので、k>0
で考えれば十分。
s=(n-k)×n×(n+k)
ｓが素数となるためには、
「３つの数のうちいずれか２つの積の絶対値が１である」（＊）
ことが必要である。
｜(n-k)(n+k)｜=1
をk>0で解くと、(n,k)= (0,1)。
このときs=0となり不適。
よって、条件（＊）を満たすためには
|n(n-k)|=1または |n(n+k)|=1 であることが必要。
|n(n-k)|=1 をk>0で解くと (n,k)=(1,2)
このとき、 s=(-1)×1×3=-3 で不適。
|n(n+k)|=1をk>0で解くと、(n,k)=(-1,2)
このとき、 s=(-3)×(-1)×1=3 でｓは素数。
以上から、求める３つの整数は、{-3, -1, 1} ・・・ （答え）
（ 等差数列の公差を考慮すると (-3, -1, 1) と (1, -1, -3) ）
（ペンネ−ム：月の光）
初項−３、項差２の数列
-3 ,-1 ,1 三つかけると３（素数）になる。
項が整数の等差数列ではこれだけのように思います。
複素数で考えると、初項1-ai、項差aiの数列
1-ai , 1 , 1+ai は掛けると 1+a2になります。
この形の素数は無限にあるのではないでしょうか。
（ペンネ−ム：小春）
-3,-1,1のとき公差 ２の等差数列をなしています。
（ペンネ−ム：ZEN ＆ TUNAKI）
等差２の数列で、−３、−１、１が、三つの整数です。
（ペンネ−ム：数楽者）
−３、−１、１
説明
絶対値が２以上の数が２つあってはだめ。
当然０もだめ。
したがって、３つのうちの２つはー１と１である。
積が正になることを考慮すると、もう一つの数は−３である。
（ペンネ−ム：Y次郎）
-3 , -1 , 1
絶対値1以外の2整数をかけて正の整数になった場合
そのどちらの整数の絶対値でも割り切れるので、素数ではない。
また、0が混じるものは論外。
よって、絶対値1以外の整数は2つ以上あってはならない。
すると、必然的に -1、1が入る。
よって、積が正になるものは -3 , -1 , 1
（ペンネ−ム：ありさのお父さん）
(-3, -1, 1) 全部かけて 3 になります。
一瞬，「数をかけ合わせて素数になるはずがないでしょ！ 変な問題！」
と思いましたが，すぐに整数は自然数じゃないことに気づきました。
余談：
私のノートブックに入っている辞書（マイペディアという簡易型の百科事典です。）
によると，
そすう【素数】
一とその数自身との外には約数がない正の整数。＃一は除く。
やくすう【約数】
整数(整式)Ａが他の整数(整式)Ｂで割り切れる時の、Ａに対するＢのこと。
⇔倍数
せいすう【正数】【整数】
(1) 【正数】零より大きい数。⇔負数。＃positive numberの訳語。
(2) 【整数】零およびそれに次次に一を加えたり引いたりして得られる範囲の数。
＃integerの訳語。
この定義だと，約数は正の数という限定がありませんので，
1を除く全ての数 n に対して，
n = (-n)×(-1)
で，n が整数なら (-n) も整数で，(-n) は n でも 1 でもありませんから，
素数はこの世に存在しないことになってしまいます。
| kiyo | さだやん | ありさのお父さん | 数楽者 | 浜田 明巳 |
| 水の流れ | みや | Chee | ちゃめ | 月の光 |
| ものもの | 小春 | まめ | ZEN ＆ TUNAKI | ふー |
| Y次郎 |
問題１について
素数についての話は
５．カ−ドの問題でもしました。
次の数で割り切れるかどうかを判定する方法をもう１度示します。
２・・・下１桁が偶数なら割れる
３・・・各桁の数字を足してみてそれが３で割り切れれば、割れる。
４・・・下２桁が４で割り切れれば割れる
５・・・下１桁が５か０なら割れる
６・・・２で割れて、３で割れれば、割れる
７・・・下から３桁ごとに区切り、奇数番目のものの和と、偶数番目のものの和の差が７の倍数なら割れる。
８・・・下３桁が８で割り切れれば割れる
９・・・各桁の数字を足してみてそれが９で割り切れれば、割れる。
１０・・・下１桁が０なら割れる(我ながらつまらないことかいてるなあ・・・)
１１・・・奇数桁の和と偶数桁の和の差が、１１の倍数なら割れる
１２・・・４で割れて、３で割れれば、割れる
１３・・・下から３桁ごとに区切り、奇数番目のものの和と、偶数番目のものの和の差が１３の倍数なら割れる。
これについての詳しい証明
この問題の場合、「９８７６５４３２１」がどの位置にこようとも
(×１０ｎ、ｎは任意)、それ以下の桁が２，３，５の倍数なら、元の数も
２，３，５になるので、めでたくすべて合成数(素数でないもの)となります。
「さだやん」さんのおっしゃる通り、素数がみつかりだすと大変かもしれません。
大きな数になったときに、その数Ｎが素数か否か、判定するための方法はこれといってないからです。
仕方ないですから、２、３、５、７、１１、１３、１７・・・と素数で順番に割っていってＮの約数を探すしかないでしょう。
それを
まで繰り返して見つからなければＮは素数です。
なぜ、まで探せば充分なのでしょうか？
約数は必ずペアがいるからです。もし、を越えたところに約数がみつかったなら
実はそのパ−トナ−がより前にいたはずですよね。
だからまでで充分なのです。
問題２について
「かけて素数？」ということで、あれっ？ と思った方もいるかと思います。
私もその１人です。それがおもしろくて出題してみました。
「Chee」さんのコメントにある「１は素数か？」という点ですが、
「１は素数ではない」といのが結論です。
もしかしたら、「１も素数」とするという立場で論理を展開することもできるのかもしれませんが・・・。
ではなぜ１を素数としないのでしょうか？
それは１以外の正の整数(自然数)の素因数分解の一意性を保証するためです。
| 素因数分解の一意性 １でない正の整数は、素数の積として、一意的にかける。 |
というものです。
例えば、１２＝２×２×３と素因数分解されます。
これはかける順番を考慮しなければただ１通りの分解になります。
ところが、１も素数ということにしてしまうと、
１２＝１×２×２×３
１２＝１×１×２×２×３
・・・などいくらでも、分解の方法があることになってしまうからです。
「素数」という名称はよくつけたものだなあと思うのですが、数(自然数)の「素」になっている、
それらに必ず分解できる、そこには１を入れない方が自然、というわけですね。
また整数論に限らず、この素因数分解の一意性が定理の証明などに
重要な役割を果たしている場面があります。
ところで、素数にまつわる話をもう１つ。
合成数が連続５個続いているところを見つけられますか？
合成数が連続１００個続いているところを見つけられますか？
最初に現れる、合成数連続５個は、｛２４，２５，２６，２７，２８｝です。
これは比較的簡単に見つけることだできます。
では連続１００個はどうでしょう？
１０１！＋２、１０１！＋３、・・・、１０１！＋１０１という連続した１００個の整数を考えます。
最初にある１０１！＋２は２で割り切れますから２の倍数です。
２番目の１０１！＋３は３で割り切れますから３の倍数です。
・・・
最後に１０１！＋１０１は１０１で割り切れますから１０１の倍数です。
というわけで、これらは１００個の連続した合成数となります。
しかしながら、これが連続１００個の合成数として、最小のものかどうかはわかりません。
ただ、存在は示したというだけです。
同様に作ればいいわけですから、
実は任意のＮに対して、合成数連続Ｎ個というのを見いだすことができます。
ただしご想像の通り、それはとてつもなく大きい数になるでしょう。
素数というのは、まだまだわかっていないことも多く、本当に魅力的な存在です。
戻る