Editing Prime number (section)

=== Unique factorization ===
{{Main|Fundamental theorem of arithmetic}}

Writing a number as a product of prime numbers is called a ''prime factorization'' of the number. For example:
: <math>\begin{align}
   50 &= 2\times 5\times 5\\
   &=2\times 5^2.
 \end{align}</math>
The terms in the product are called ''prime factors''. The same prime factor may occur more than once; this example has two copies of the prime factor <math>5.</math> When a prime occurs multiple times, [[exponentiation]] can be used to group together multiple copies of the same prime number: for example, in the second way of writing the product above, <math>5^2</math> denotes the [[Square (algebra)|square]] or second power of {{tmath|>5}}.

The central importance of prime numbers to number theory and mathematics in general stems from the ''fundamental theorem of arithmetic''.<ref>{{cite book|title=The Nature of Mathematics
|first=Karl J.|last=Smith|edition=12th|publisher=Cengage Learning|year=2011|isbn=978-0-538-73758-6|page=188|url=https://books.google.com/books?id=Di0HyCgDYq8C&pg=PA188}}</ref> This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ.<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA16 Section 2, Theorem 2, p. 16]; {{cite book|title=Closing the Gap: The Quest to Understand Prime Numbers|title-link= Closing the Gap: The Quest to Understand Prime Numbers |first=Vicky|last=Neale|author-link=Vicky Neale|publisher=Oxford University Press|year=2017|isbn=978-0-19-109243-5|at=[https://books.google.com/books?id=T7Q1DwAAQBAJ&pg=PA107 p. 107]}}</ref> So, although there are many different ways of finding a factorization using an [[integer factorization]] algorithm, they all must produce the same result. Primes can thus be considered the "basic building blocks" of the natural numbers.<ref>{{cite book|title=The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics|first=Marcus|last=du Sautoy|author-link=Marcus du Sautoy|publisher=Harper Collins|year=2003|isbn=978-0-06-093558-0|page=[https://archive.org/details/musicofprimessea00dusa/page/23 23]|url=https://archive.org/details/musicofprimessea00dusa|url-access=registration}}</ref>

Some proofs of the uniqueness of prime factorizations are based on [[Euclid's lemma]]: If {{tmath|p}} is a prime number and {{tmath|p}} divides a product <math>ab</math> of integers {{tmath|a}} and <math>b,</math> then {{tmath|p}} divides {{tmath|a}} or {{tmath|p}} divides {{tmath|b}} (or both).<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA15 Section 2, Lemma 5, p. 15]; {{cite book|title=Mathematics for the Curious|first=Peter M.|last=Higgins|publisher=Oxford University Press |year=1998 |isbn=978-0-19-150050-3 |pages=77–78|url=https://books.google.com/books?id=LeYH8P8S9oQC&pg=PA77}}</ref> Conversely, if a number {{tmath|p}} has the property that when it divides a product it always divides at least one factor of the product, then {{tmath|p}} must be prime.<ref>{{cite book|title=A First Course in Abstract Algebra|first=Joseph J.|last=Rotman|edition=2nd|publisher=Prentice Hall|year=2000|isbn=978-0-13-011584-3|at=Problem 1.40, p. 56}}</ref>