素数の例。謎の素数

古代ギリシャ人の時代から、素数は数学者にとって非常に魅力的なものでした。彼らは常に探していますさまざまな方法見つけることですが、最も効果的な方法は「捕まえる」ことです。素数、アレクサンドリアの天文学者で数学者エラトステネスによって発見された方法であると考えられています。この方法はすでに約2000年前から存在しています。

どの数字が素数ですか

素数を決定するにはどうすればよいですか? 多くの数値は、余りを残さずに他の数値で割り切れます。整数を割る数を「除数」といいます。

この場合、剰余なしの割り算について話しています。たとえば、数字 36 は、1、2、3、4、6、9、12、18 で割ることも、それ自体、つまり 36 で割ることもできます。これは、36 には 9 つの約数があることを意味します。数字 23 はそれ自体と 1 でのみ割り切れます。つまり、この数字には約数が 2 つあり、この数字は素数です。

約数が 2 つだけの数を素数と呼びます。つまり、余りなしでそれ自身と1だけで割り切れる数を素数といいます。

数学者にとって、仮説を立てるために使用できる一連の数値のパターンを発見することは、非常にやりがいのある経験です。しかし、素数はいかなるパターンにも従うことを拒否します。しかし、素数を決定する方法はあります。この方法はエラトステネスによって発見され、「エラトステネスの篩」と呼ばれています。最大 48 までの数字の表の形式で表示されるそのような「ふるい」のバージョンを見て、それがどのように編集されるかを理解しましょう。

この表では、48 未満のすべての素数がマークされています。オレンジ。それらは次のように見つかりました。

1 – 約数が 1 つあるため、素数ではありません。
2 は最小の素数で唯一の偶数です。他のすべての偶数は 2 で割り切れます。つまり、少なくとも 3 つの約数があるため、これらの数は次のように減ります。紫色の柱;
3 は素数で、約数が 2 つあり、3 で割り切れる他のすべての数値は除外されます。これらの数値は黄色の列にまとめられています。紫と黄色の両方でマークされた列には、2 と 3 の両方で割り切れる数字が含まれています。
5 は素数であり、5 で割り切れる数字はすべて除外されます。これらの数字は緑色の楕円で囲まれています。
7 は素数です。7 で割り切れるすべての数は赤い楕円で囲まれています。これらは素数ではありません。

素数ではないすべての数値は青色でマークされます。次に、この表を画像と似たもので自分で編集できます。

1 つを除くすべての自然数は、素数と合成数に分けられます。 素数とは、自然数、約数は 2 つだけです: 1 とそれ自体です。。他のすべては複合と呼ばれます。素数の性質の研究は、数学の特別な分野である整数論によって行われます。環理論では、素数は既約元に関係します。

これは、2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73 から始まる一連の素数です。、79、83、89、97、101、103、107、109、113、...など

算術の基本定理によれば、1 より大きいすべての自然数は素数の積として表すことができます。同時に、これは自然数を因数の次数まで表現する唯一の方法です。このことから、素数は自然数の基本部分であると言えます。

この自然数の表現は、自然数の素数への分解、または数値の因数分解と呼ばれます。

最も古く、効果的な方法素数の計算は「エラストフェネスの篩」です。

実際には、エラストフェネスの篩を使用して素数を計算した後、次のことを確認する必要があることがわかっています。指定された番号単純。この目的のために、特別なテスト、いわゆる単純性テストが開発されました。これらのテストのアルゴリズムは確率的です。これらは暗号化で最もよく使用されます。

ちなみに、数値の一部のクラスには、特殊な効果的な素数性テストがあります。たとえば、メルセンヌ数の素数性を確認するにはリュック・レーマーテストが使用され、フェルマー数の素数性を確認するにはペピンテストが使用されます。

私たちは皆、無限に多くの数があることを知っています。では、素数はいくつあるのでしょうか?という疑問が当然生じます。素数も無限に存在します。この命題の最も古い証明は、『要素』に記載されているユークリッドの証明です。ユークリッドの証明は次のようになります。

素数の数が有限であると想像してみましょう。それらを掛け合わせて 1 を加えてみましょう。結果として得られる数値は、素数の有限集合のいずれかで除算することはできません。なぜなら、それらのいずれかで除算した余りは 1 になるからです。したがって、この数値は、このセットに含まれていない素数で割り切れる必要があります。

素数分布定理は、π(n) で示される n 未満の素数の数が n / ln(n) に応じて増加すると述べています。

何千年も素数を研究してきた結果、既知の最大の素数は 243112609 − 1 です。この数値は 12,978,189 桁の 10 進数を持ち、メルセンヌ素数 (M43112609) です。この発見は、メルセンヌ素数プロジェクト GIMPS の分散探索の一環として、2008 年 8 月 23 日に uCLA 大学の数学学部で行われました。

家特徴的な機能メルセンヌ数は、非常に有効なリュック・ルメール素数検定の存在です。その助けにより、メルセンヌ素数は、長期間にわたって既知の最大の素数になります。

しかし、今日に至るまで、素数に関する多くの質問には正確な答えが得られていません。第 5 回国際数学会議で、エドモンド・ランドーは素数分野の主な問題を定式化しました。

ゴールドバッハの問題またはランダウの最初の問題は、2 より大きいすべての偶数は 2 つの素数の合計として表現できること、およびすべての偶数が表現できることを証明または反証する必要があるということです。奇数 5 より大きい場合は、合計として表すことができます。 3つのシンプルな数字。
ランダウの 2 番目の問題では、「素数双生児」 (差が 2 である素数) のセットは無限ですか? という質問に対する答えを見つける必要があります。
ルジャンドル予想またはランダウの 3 番目の問題は、n2 と (n + 1)2 の間に常に素数が存在するというのは本当ですか?
ランダウの 4 番目の問題: n2 + 1 の形式の素数の集合は無限ですか?
上記の問題に加えて、フィボナッチ数やフェルマー数などの多くの整数列における無限個の素数を求める問題もあります。

約数の列挙。定義上、数値 nが素数であるのは、2 および 1 とそれ自体を除く他の整数で割り切れない場合のみです。上記の式により、不要な手順が削除され、時間が節約されます。たとえば、数値が 3 で割り切れるかどうかを確認した後、9 で割り切れるかどうかを確認する必要はありません。

Floor(x) 関数は、x を x 以下の最も近い整数に丸めます。

剰余算術について学びます。「x mod y」（mod はラテン語の「modulo」、つまり「モジュール」の略語）という演算は、「x を y で割って余りを求める」という意味です。言い換えれば、剰余算術では、と呼ばれる特定の値に達すると、 モジュール、数字は再びゼロに「変わります」。たとえば、時計は 12 の係数で時間を刻みます。つまり、10 時、11 時、12 時を表示し、その後 1 に戻ります。

多くの電卓には mod キーがあります。このセクションの最後では、大きな数に対してこの関数を手動で評価する方法を示します。

フェルマーの小定理の落とし穴について学びましょう。テスト条件を満たさない数値はすべて合成されますが、残りの数値は おそらく単純なものに分類されます。不正確な結果を避けたい場合は、次の点を探してください。 n「カーマイケル数」（以下を満たす合成数）のリストにあるこのテスト) および「疑似素数フェルマー数」(これらの数は一部の値についてのみテスト条件に対応します) ある).

都合がよければ、ミラー・ラビン検定を使用してください。この方法は手動で計算するのが非常に面倒ですが、次のような場合によく使用されます。コンピュータプログラム。許容可能な速度が得られ、フェルマーの方法よりもエラーが少なくなります。合成数は、値の 1/4 を超える計算が行われた場合、素数として受け入れられません。ある。ランダムに選ぶとさまざまな意味あるそしてそれらすべてについて、テストは肯定的な結果をもたらすため、かなり高い自信を持って次のように仮定できます。 nは素数です。

大きな数値の場合は、モジュラー演算を使用します。 MOD を備えた電卓が手元にない場合、または電卓がそのような大きな数値を処理できるように設計されていない場合は、べき乗とモジュラー演算のプロパティを使用して計算を簡単にします。以下は例です 3 50 (\displaystyle 3^(50)) mod 50:

式をさらに書き換えます便利な形: mod 50。手動計算の場合は、さらに簡略化する必要がある場合があります。
(3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50。ここでは剰余乗算の性質を考慮しました。
3 25 (\displaystyle 3^(25)) mod 50 = 43。
(3 25 (\displaystyle (3^(25))モッド50 ∗ 3 25 (\displaystyle *3^(25))モッド 50) モッド 50 = (43 ∗ 43) (\displaystyle (43*43))モッド50。
= 1849 (\displaystyle =1849)モッド50。
= 49 (\displaystyle =49).

この記事では、 素数と合成数。まず、素数と合成数の定義と例を示します。この後、素数が無限に存在することを証明します。次に素数表を書き出し、特にエラトステネスの篩と呼ばれる方法に注目して素数表の作成方法を考えていきます。結論として、特定の数が素数または合成数であることを証明する際に考慮する必要がある主要な点を強調します。

ページナビゲーション。

素数と合成数 - 定義と例

素数と合成数の概念は、1 より大きい数を指します。このような整数は、正の約数の数に応じて素数と合成数に分けられます。だから理解するには 素数と合成数の定義、約数と倍数とは何かをよく理解する必要があります。

意味。

素数は、正の約数が 2 つだけ、つまりそれ自身と 1 だけを持つ整数、大きな単位です。

意味。

合成数少なくとも 3 つの正の約数を持つ大きな整数です。

これとは別に、数値 1 は素数にも合成数にも適用されないことに注意してください。ユニットには正の約数が 1 つだけあり、それは数字の 1 そのものです。これにより、数値 1 が、少なくとも 2 つの正の約数を持つ他のすべての正の整数と区別されます。

正の整数はであり、正の約数は 1 つだけであることを考慮すると、素数と合成数の前述の定義を他の定式化することができます。

意味。

素数は、正の約数を 2 つだけ持つ自然数です。

意味。

合成数は、2 つ以上の正の約数を持つ自然数です。

1 より大きいすべての正の整数は素数または合成数であることに注意してください。言い換えれば、素数でも合成でもない単一の整数は存在しません。これは、数値 1 と a が常に任意の整数 a の約数であるという割り算の性質から導き出されます。

前の段落の情報に基づいて、次のことができます。次の定義合成数。

意味。

素数ではない自然数をこう呼ぶ複合.

あげましょう 素数と合成数の例.

合成数の例には、6、63、121、6,697 などがあります。この声明にも説明が必要です。数字 6 には、正の約数 1 と 6 に加えて、約数 2 と 3 もあります。6 = 2 3 であるため、6 は真の合成数です。 63 の正の因数は、1、3、7、9、21、63 です。数値 121 は積 11・11 に等しいため、その正の約数は 1、11、121 になります。そして、6,697 という数字は、その正の約数が 1 と 6,697 に加えて、37 と 181 という数字でもあるため、合成です。

この点の結論として、素数と共素数は全く同じものではないという事実にも注意を喚起したいと思います。

素数表

素数は、さらなる使用の便宜のために、素数テーブルと呼ばれるテーブルに記録されます。以下は 素数表最大1,000まで。

「なぜ素数の表を 1,000 までしか埋めなかったのに、存在するすべての素数の表を作成することは可能ではないのですか?」という論理的な疑問が生じます。

まずはこの質問の最初の部分に答えてみましょう。素数の使用が必要なほとんどの問題では、1,000 以内の素数で十分です。他の場合には、おそらく、特別な解決策に頼らなければならないでしょう。もちろん、任意の大きな有限整数までの素数のテーブルを作成することはできますが、正数 10,000 であろうと 1,000,000,000 であろうと、次の段落では素数のテーブルを作成する方法について説明します。特に、と呼ばれるメソッドを分析します。

ここで、既存のすべての素数のテーブルを作成する可能性 (またはむしろ不可能) を見てみましょう。素数は無限に存在するため、すべての素数の表を作成することはできません。最後のステートメントは、次の補助定理の後に証明する定理です。

定理。

1 より大きい自然数の 1 以外の最小の正の約数は素数です。

証拠。

させて a は 1 より大きい自然数、b は 1 とは異なる a の最小の正の約数です。 b が素数であることを矛盾によって証明しましょう。

b が合成数であると仮定します。次に、数 b (b 1 とします) の約数があり、これは 1 とも b とも異なります。除数の絶対値が被除数の絶対値を超えないことも考慮すると (これは割り算の性質からわかります)、条件 1 が満たされる必要があります。

数 a は条件に従って b で割り切れます。また、b は b 1 で割り切れると言いました。割り切れるという概念により、a=b q および b=b となる整数 q および q 1 の存在について話すことができます。 1 q 1 、ここから a= b 1 ·(q 1 ·q) 。 2 つの整数の積は整数であるということになり、等式 a=b 1 ·(q 1 ·q) は、b 1 が数値 a の約数であることを示します。上記の不等式を考慮すると 1

これで、素数が無限に存在することが証明できました。

定理。

素数は無限に存在します。

証拠。

そうでないと仮定しましょう。つまり、素数が n 個しかなく、これらの素数が p 1、p 2、...、p n であるとします。示されたものとは異なる素数を常に見つけることができることを示しましょう。

数値 p が p 1 ·p 2 ·… ·p n +1 に等しいと考えてください。この数が素数 p 1、p 2、...、p n のそれぞれとは異なることは明らかです。数値 p が素数であれば、定理は証明されます。この数が合成の場合、前の定理により、この数の素約数が存在します (これを p n+1 と表します)。この約数が数値 p 1、p 2、...、p n のいずれとも一致しないことを示します。

そうでない場合は、割り算の性質に従って、積 p 1 ·p 2 ·… ·p n は p n+1 で除算されます。しかし、数 p は p n+1 でも割り切れ、合計 p 1 ·p 2 ·… ·p n+1 に等しくなります。したがって、p n+1 はこの和の第 2 項 (1 に等しい) を除算しなければなりませんが、これは不可能です。

このように、予め定められた任意の数の素数に含まれない新たな素数を常に見つけることができることが証明された。したがって、素数は無限に存在します。

したがって、素数は無限にあるという事実のため、素数の表を作成するときは、常に上からある数値 (通常は 100、1,000、10,000 など) に制限します。

エラトステネスのふるい

次に、素数のテーブルを作成する方法について説明します。 100 までの素数の表を作成する必要があるとします。

この問題を解決する最も明白な方法は、2 から始まり 100 で終わる正の整数を順番にチェックし、1 より大きくテスト対象の数より小さい正の約数が存在するかどうかを確認することです (割り算の性質からわかっています)。除数の絶対値が被除数の絶対値 (ゼロ以外) を超えないこと。そのような約数が見つからない場合、テストされる数は素数であり、素数テーブルに入力されます。そのような約数が見つかった場合、テストされる数値は合成数値であり、素数の表には入力されません。この後、次の数値に移行し、同様に約数の存在がチェックされます。

最初のいくつかの手順を説明しましょう。

番号 2 から始めます。数字 2 には、1 と 2 以外に正の約数はありません。そこで、簡単なので素数表に記入してみます。ここで、2 が最小の素数であると言う必要があります。 3 番に移りましょう。 1 と 3 以外に考えられる正の約数は 2 です。しかし、3 は 2 で割り切れないので、3 は素数であり、素数の表にも含める必要があります。４番に移りましょう。 1 と 4 以外の正の約数は 2 と 3 になります。確認してみましょう。数字 4 は 2 で割り切れるため、4 は合成数であり、素数の表に含める必要はありません。 4 が最小の合成数であることに注意してください。５番に移りましょう。数値 2、3、4 の少なくとも 1 つがその約数であるかどうかを確認します。 5 は 2、3、または 4 で割り切れないので、素数であり、素数の表に書き留める必要があります。その後、6、7 というように 100 までの数字に移行します。

素数のテーブルを作成するこのアプローチは理想とは程遠いです。いずれにせよ、彼には存在する権利があります。整数のテーブルを作成するこの方法では、割り算基準を使用できるため、約数を見つけるプロセスがわずかに高速化されることに注意してください。

と呼ばれる素数のテーブルを作成するもっと便利な方法があります。名前にある「ふるい」という言葉は偶然ではありません。このメソッドの動作は、いわば整数や大きな単位をエラトステネスのふるいに通して「ふるいにかけ」、単純なものから複合的なものを分離するのに役立つからです。

50 までの素数の表を作成するときにエラトステネスのふるいが動作しているところを見てみましょう。

まず、2、3、4、…、50という数字を順番に書きます。

最初に書かれた数字 2 は素数です。次に、番号 2 から順に 2 つの番号を右に移動し、コンパイル中の番号の表の最後に到達するまで、これらの番号を取り消し線で消します。これにより、2 の倍数のすべての数値に取り消し線が引かれます。

2 の次に取り消し線が引かれていない最初の数字は 3 です。この数は素数です。ここで、番号 3 から、一貫して 3 つの番号分右に移動し (すでに取り消し線が引かれている番号を考慮して)、それらの番号を取り消し線で消します。これにより、3 の倍数のすべての数値に取り消し線が引かれます。

3 の次に取り消し線が引かれていない最初の数字は 5 です。この数は素数です。ここで、数字 5 から一貫して 5 数字ずつ右に移動し (先ほど取り消し線を引いた数字も考慮します)、それらを取り消し線で消します。これにより、5 の倍数のすべての数字に取り消し線が引かれます。

次に、7 の倍数、次に 11 の倍数、というように数字を消していきます。 ×印を付ける数字がなくなると、プロセスは終了します。以下は、エラトステネスのふるいを使用して得られた、50 までの素数の完成した表です。バツのない数字はすべて素数であり、バツ印のある数字はすべて合成です。

また、エラトステネスのふるいを使用して素数の表を作成するプロセスを高速化する定理を定式化して証明してみましょう。

定理。

1 とは異なる合成数 a の最小の正の約数はを超えません。ここで、は a からです。

証拠。

1 とは異なる合成数 a の最小の約数を文字 b で表しましょう (前の段落の最初で証明された定理からわかるように、数 b は素数です)。次に、a=b・q のような整数 q があり (ここで、q は整数の乗算規則に従う正の整数です)、(b>q の場合、b が a の最小約数であるという条件に違反します) 、 a=q・b の等価性により、q は数値 a の約数でもあるため)。不等式の両辺に正の値と 1 より大きい整数を掛けると (これを行うことは許可されています)、が得られ、そこからとが得られます。

証明された定理はエラトステネスのふるいに関して何を与えますか?

まず、素数 b の倍数である合成数は、次の値に等しい数値で始まる必要があります (これは不等式から得られます)。たとえば、2 の倍数の数字は 4 で始め、3 の倍数は 9 で、5 の倍数は 25 で始めるなどのようにします。

第二に、エラトステネスのふるいを使用して番号 n までの素数の表を作成することは、素数の倍数であるすべての合成数がを超えない場合に完了したと見なすことができます。この例では、n=50 (最大 50 までの素数のテーブルを作成しているため)、したがって、エラトステネスのふるいは、素数 2、3、5、7 の倍数であるすべての合成数を除去する必要があります。算術平方根 50 を超えてはなりません。つまり、素数 11、13、17、19、23 などの 47 までの倍数である数値は、より小さい素数 2 の倍数としてすでに取り消されているため、検索して取り消し線を引く必要がなくなりました。、３、５、７。

この数は素数ですか、それとも合成ですか?

一部のタスクでは、指定された数値が素数か合成数値かを調べる必要があります。一般に、このタスクは、特に多数の文字で構成される数値の場合、決して簡単ではありません。ほとんどの場合、それを解決するための特定の方法を探す必要があります。ただし、単純なケースについては、思考の流れに方向性を与えるように努めます。

もちろん、割り算テストを使用して、指定された数値が合成であることを証明することもできます。たとえば、割り算のテストで、指定された数が 1 より大きい正の整数で割り切れることが示された場合、元の数は合成数になります。

例。

898,989,898,989,898,989 が合成数であることを証明してください。

解決。

この数字の各桁の合計は 9・8+9・9=9・17 となります。 9・17 に等しい数は 9 で割り切れるので、9 で割り切れることにより、元の数も 9 で割り切れると言えます。したがって、それは複合です。

このアプローチの重大な欠点は、割り算基準では数値の素数を証明できないことです。したがって、数値をテストして素数か合成かを確認する場合は、別の手順を実行する必要があります。

最も論理的なアプローチは、指定された数値の考えられるすべての約数を試すことです。考えられる約数がいずれも指定された数値の真の約数ではない場合、この数値は素数になります。それ以外の場合、その数値は合成になります。前の段落で証明された定理から、与えられた数 a の約数は、を超えない素数の中から求めなければならないことがわかります。したがって、与えられた数 a を素数 (素数の表から都合よく取り出したもの) で順番に割り、数 a の約数を見つけることができます。約数が見つかった場合、数値 a は合成になります。を超えない素数の中に数 a の約数がない場合、数 a は素数です。

例。

番号 11 723 単純ですか、それとも複合ですか?

解決。

11,723 という数字の約数は素数まで何になるかを調べてみましょう。これを行うには、評価してみましょう。

それはかなり明白です、200 2 =40,000 以降、11,723<40 000 (при необходимости смотрите статью 数字の比較）。したがって、11,723 の可能な素因数は 200 未満になります。これにより、作業がすでにはるかに簡単になります。これを知らなかったら、200 までではなく 11,723 までのすべての素数を調べる必要があります。

必要に応じて、より正確に評価することができます。 108 2 =11,664、109 2 =11,881 なので、108 2<11 723<109 2 , следовательно, 。したがって、109 未満の素数はいずれも、指定された数値 11,723 の素因数である可能性があります。

ここで、数値 11,723 を素数 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71 に順番に分割します。、 73 、 79 、 83 、 89 、 97 、 101 、 103 、 107 。数値 11,723 を、書かれた素数の 1 つで割ると、合成になります。書かれた素数のどれでも割り切れない場合、元の数は素数になります。

この単調で単調な分割プロセス全体については説明しません。すぐに 11,723 としましょう

イリヤの答えは正しいですが、あまり詳しくありません。ちなみに、18世紀にはまだ1は素数とみなされていました。たとえば、オイラーやゴールドバッハなどの偉大な数学者です。ゴールドバッハは、2000 年代の 7 つの問題の 1 つであるゴールドバッハ仮説の著者です。元の公式では、すべての偶数は 2 つの素数の合計として表すことができると述べています。さらに、最初は 1 が素数として考慮されており、2 = 1+1 であることがわかります。これは、仮説の元の定式化を満たす最小の例です。その後修正され、この公式は「4 から始まるすべての偶数は 2 つの素数の合計として表すことができる」という現代的な形式になりました。
定義を思い出してみましょう。素数は、p 自体と 1 の 2 つの異なる自然約数のみを持つ自然数 p です。定義からの当然の結果: 素数 p には、p 自体という 1 つの素数しかありません。
ここで、1 が素数であると仮定します。定義上、素数には素数が 1 つだけあり、それ自体が素数になります。すると、1 より大きい素数は、それとは異なる素数 (1 で割り切れる) で割り切れることがわかります。しかし、2 つの異なる素数を互いに割り算することはできません。そうでない場合、それらは素数ではなく合成数となり、定義に矛盾します。このアプローチでは、素数は 1 つだけ、つまり単位自体であることがわかります。しかし、これは不合理です。したがって、1 は素数ではありません。
1 と 0 は、別の数のクラス、つまり代数分野のサブセットにおける n 項演算に関する中立要素のクラスを形成します。さらに、加算の演算に関しては、1 は整数の環の生成要素でもあります。
このように考慮すると、他の代数構造で素数の類似物を発見することは難しくありません。 1: 2、4、8、16、... などの 2 の累乗で構成される乗法グループがあるとします。ここでは 2 が形成要素として機能します。このグループの素数は、最小の要素より大きく、それ自体と最小の要素でのみ割り切れる数です。私たちのグループでは、そのような特性を持っているのは 4 つだけです。私たちのグループにはこれ以上素数はありません。
私たちのグループ内で 2 も素数である場合は、最初の段落を参照してください。やはり、2 だけが素数であることがわかります。