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] 要么是素数,要么不是素数。如果它是素数,那么它就是列表中没有的一个新的素数。

The proof continues: if [latex]P[/latex] is not prime, it must be divisible by some prime, say [latex]q[/latex]. This prime [latex]q[/latex] must be on our assumed complete list of primes. However, if we divide [latex]P[/latex] by any of the primes [latex]p_i[/latex] from our list, the remainder is always 1. Therefore, none of the primes on our list can be the factor [latex]q[/latex]. This means [latex]q[/latex] must be a prime number that was not on our original list. In either case—whether [latex]P[/latex] is prime or composite—there exists at least one more prime than is contained in any finite list. This contradicts the initial assumption that the set of all primes is finite. Therefore, the set of prime numbers must be infinite. This elegant argument is considered a masterpiece of mathematical reasoning and is often one of the first examples of proof by contradiction taught to students. It appears in Book IX, Proposition 20 of Euclid’s *Elements*.

UNESCO Nomenclature: 1101
– 纯数学

类型

抽象系统

中断

基础

用法

广泛使用

前体

  • concept of prime and composite numbers (developed by earlier Greek mathematicians like the Pythagoreans)
  • 基本 算术定理 (隐含地表示:大于 1 的每个整数要么是质数,要么是质数的乘积)
  • 除法算法
  • 逻辑学和反证法(归谬法)

应用程序

  • 数论基础
  • 密码学 (例如,RSA算法利用了分解大数的难度,而这与素数的分布有关)
  • 现代代数和分析的发展
  • 用于素性检验的计算机科学算法和 因式分解

专利:

NA

潜在创新理念

  • 开发更高效的素数筛选算法
  • quantum algorithms for prime factorization (e.g., shor’s algorithm)
  • 用于模拟的基于素数的伪随机数生成器
  • 用于寻找大素数的分布式计算项目(例如,GIMPS)
  • 基于素数不同性质的新型密码系统
  • 用于可视化数论证明的教育软件
  • 利用人工智能驱动的定理证明器发现素数无穷大的新证明
  • 区块链 technologies using prime numbers for hash functions
  • secure communication protocols for internet of things (智能机器人设备
  • 利用素数分解的数据压缩算法
与以下概念相关:欧几里得定理、素数、无穷素数、反证法、数论、欧几里得几何原本、素数、数学、古希腊、算术基本定理。

历史背景

无限素数(欧几里得证明)

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

(如果日期未知或不相关,例如“流体力学”,则提供其显著出现的近似估计)

第十年 周年纪念日

只有注册会员才能免费获得 100% 的全尺寸图片和下载。.

> 登录 <