Product Design, Manufacturing & Innovation Resources
» 無限個の素数(ユークリッドの証明)

無限個の素数(ユークリッドの証明)

-300
  • Euclid of Alexandria
アレクサンドリアのユークリッド、古典研究の設定で無限素数を証明。.

(画像はイメージです)

ユークリッドの定理は、素数は無限に存在すると述べています。古典的な証明は背理法です。すべての素数の有限リスト [latex]p_1, p_2, dots, p_n[/latex] を仮定します。次に、数 [latex]P = p_1 p_2 cdots p_n + 1[/latex] を考えます。この数 [latex]P[/latex] は素数であるかそうでないかのどちらかです。素数であれば、リストにない新しい素数になります。

証明は続きます。[latex]P[/latex]が素数でない場合、何らかの素数、例えば[latex]q[/latex]で割り切れる必要があります。この素数[latex]q[/latex]は、私たちが想定した素数の完全なリストに含まれている必要があります。しかし、[latex]P[/latex]をリストにある素数[latex]p_i[/latex]のいずれかで割ると、余りは常に1になります。したがって、リストにある素数のいずれも[latex]q[/latex]の因数にはなり得ません。つまり、[latex]q[/latex]は、元のリストに含まれていなかった素数でなければなりません。いずれの場合も、つまり[latex]P[/latex]が素数であろうと合成数であろうと、有限のリストに含まれる素数よりも少なくとも1つ多い素数が存在します。これは、すべての素数の集合が有限であるという最初の仮定に矛盾します。したがって、素数の集合は無限でなければなりません。この洗練された議論は、数学的推論の傑作とみなされており、学生に教えられる背理法の最初の例の一つとしてよく挙げられる。ユークリッドの『原論』第9巻命題20に掲載されている。

UNESCO Nomenclature: 1101
純粋数学

タイプ

抽象システム

混乱

基礎

使用法

広く普及している

前駆物質

  • 素数と合成数の概念(ピタゴラス学派など、古代ギリシャの数学者によって発展させられた)
  • the fundamental theorem of arithmetic (implicitly used, stating every integer greater than 1 is either a prime or a product of primes)
  • 除算アルゴリズム
  • logic and the method of proof by contradiction (reductio ad absurdum)

アプリケーション

  • 数論の基礎
  • cryptography (e.g., RSA algorithm relies on the difficulty of factoring large numbers, which is related to the distribution of primes)
  • 現代代数学と解析学の発展
  • computer science algorithms for primality testing and factorization

特許:

NA

潜在的なイノベーションのアイデア

ボットによるトラフィック(現在1日あたり4万件以上)を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < (100%無料)でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。

関連: ユークリッドの定理、素数、無限素数、背理法、数論、ユークリッドの原論、原始、数学、古代ギリシャ、算術の基本定理。

歴史的背景

無限個の素数(ユークリッドの証明)

-300
-550
1750
1790
1800
1844
1874
-300
-450
1585
1779
1799
1801
1850
1875

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

関連する発明、革新、および技術原理

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。