4,781
edits
Changes
Jump to navigation
Jump to search
mLine 28:
Line 28: + + + + + + + Line 39:
Line 46: − − ==Unique Factorization== − According to the [[Fundamental Theorem of Arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique factorization into prime numbers. − − This means that every integer larger than 1, can be expressed as a product of one or more primes in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132. − − Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be [[NP-complete]].
moving more basic section up
Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):
Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):
<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>
<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>
==Unique Factorization==
According to the [[Fundamental Theorem of Arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique [[factorization]] into prime numbers.
This means that every integer larger than 1, can be expressed as a product of one or more primes in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.
Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be [[NP-complete]].
==Alternative Definition==
==Alternative Definition==
The preference for this alternate definition of "prime" is that this definition gives you unique [[factorization]] theorems analogous to the [[Fundamental Theorem of Arithmetic]]. For more information, consult the articles on [[Dedekind ring]]s and [[ring theory]], or an abstract algebra book<ref>'''Abstract Algebra: An Introduction''', Thomas Hungerford. Brooks Cole; 2 edition (1996)</ref>
The preference for this alternate definition of "prime" is that this definition gives you unique [[factorization]] theorems analogous to the [[Fundamental Theorem of Arithmetic]]. For more information, consult the articles on [[Dedekind ring]]s and [[ring theory]], or an abstract algebra book<ref>'''Abstract Algebra: An Introduction''', Thomas Hungerford. Brooks Cole; 2 edition (1996)</ref>
==Primality testing==
==Primality testing==