1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

素数が無限にあることの証明(背理法)

Posted at

素数が無限にあることを次のように背理法で証明します。

証明

素数が有限で$n$個であるとする。その$n$個を$$p_1,,p_2,,\cdots,,p_n$$とする。
このとき,次の自然数$K$を考える。$$K=p_1\times p_2\times \cdots\times p_n+1$$
この$K$はどの素数でも割り切ることができないので,素数となり,素数の個数が$n$個であることに矛盾します。故に素数は無限あります。

証明を振り返って

こう書くと,$K$という自然数は素数であるように思えます。素数になるかどうはか調べてみないとわからないので,Jupyter notebookとWolfram Language 12を使って調べてみました。

Mathematicaの数学関数

コマンドの確認です。

PrimeQ[expr]
expr が素数の場合にはTrueを,その他の場合にはFalseを与える

Prime[n]
第 n 番目の素数を与える.

FactorInteger[n]
整数 n の素因数をこれらの指数とともにリストとして返す.

コード

$K$を計算してみます。とりあえず10個計算して,結果を調べてみました。

In [1]: Table[Product[Prime[i],{i,1,n}]+1,{n,1,10}]
Out[1]: {3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231}

In [2]: PrimeQ[%]
Out[2]: {True, True, True, True, True, False, False, False, False, False}

となり,6個目からは素数でないことがわかります。一応,6個目を確認して,因数分解してみます。

In [3]: 2*3*5*7*11*13+1
Out[3]: 30031

In [4]: FactorInteger[30031]
Out[4]: {{59, 1}, {509, 1}}

ということで,$$2\times3\times5\times 7\times 11\times13+1=30031=59\times509$$でした。今回のケースで言えば,14より大きいところに因数59と509があるわけです。

考察

まあ,数が大きくなるとあまり素数にならないんだろうなあと思っているのですが,とりあえず1000個くらい調べてみると,

In [5]: list1=Table[Product[Prime[i],{i,1,n}]+1,{n,1,1000}];
        list2=PrimeQ[list1];
        Position[list2,True]

Out[5]: {{1}, {2}, {3}, {4}, {5}, {11}, {75}, {171}, {172}, {384}, {457}, 
         {616}, {643}}

13個でした。このような素数は無限にあるとは思いますが,どうなんでしょうか?

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?