section_path: Elementary properties/Unique factorization
section_name: Unique factorization
paragraph_text: Unique factorization
  
  Writing a number as a product of prime numbers is called a prime factorization of the number. For example:
  
  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 5. {\displaystyle 5.} 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, 5 2 {\displaystyle 5^{2}} denotes the square or second power of 5. {\displaystyle 5.}
  
  The central importance of prime numbers to number theory and mathematics in general stems from the fundamental theorem of arithmetic. 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. 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.
  
  Some proofs of the uniqueness of prime factorizations are based on Euclid's lemma: If p {\displaystyle p} is a prime number and p {\displaystyle p} divides a product a b {\displaystyle ab} of integers a {\displaystyle a} and b, {\displaystyle b,} then p {\displaystyle p} divides a {\displaystyle a} or p {\displaystyle p} divides b {\displaystyle b} (or both). Conversely, if a number p {\displaystyle p} has the property that when it divides a product it always divides at least one factor of the product, then p {\displaystyle p} must be prime.