Prime factorization

from Wikipedia, the free encyclopedia

The prime factorization is the representation of a natural number as a product of prime numbers , which then as prime factors of are called. This representation is clear (except for the order of the factors; it is a multi-set ) and is one of the basic and classic tools of number theory . It is the subject of the fundamental theorem of arithmetic . No efficient factorization method is known to date to obtain the prime factorization of any number.

number Factors number
2 1
3 1
4th 2
5 1
6th 2
7th 1
8th 3
9 2
10 2
11 1
12 3
13 1
14th 2
15th 2
16 4th
17th 1
18th 3
19th 1
20th 3


Be a natural number. A number is called the prime factor of ,

if is a divisor of and
is a prime number .

Prime factorization is the representation of the number as the product of its prime factors. Since multiplication is commutative and associative , the order of the prime factors is not important from the point of view of number theory. The prime factorization of one can be viewed as an empty product . If itself is a prime number, it is itself its only prime factor. If there is more than one prime factor, it is called a “ composite number ”. The zero is never part of the multiplicative group and is excluded from such considerations. A prime factor can occur more than once; Multiple occurring prime factors can be summarized using the exponent notation . If the prime factors are ordered in ascending order (p k <p k + 1 ), one also speaks of the canonical prime factorization :

       Among the prime factors are several.

The exponent of a prime factor is the multiple of in and is also referred to as the - weighting of . It indicates how often is divisible by .

Examples of prime factorization

(Prime number)
( Power of two )
, with the canonical representation
( Power of ten )

Fundamental theorem of arithmetic

The statements for the existence of the prime factorization for every natural number and their uniqueness in the canonical representation are the fundamental theorem of arithmetic , also called the main theorem of elementary number theory . Both statements are formulated and proven separately. The proofs are elementary, are classically formulated as evidence of contradiction and use the well-order of the natural numbers. For the first time fully and correctly proven, the fundamental theorem of arithmetic can be found in the Disquisitiones Arithmeticae by Carl Friedrich Gauß . But it was already known to Euclid - albeit in a slightly modified form .

Proof of existence

There is nothing to show for and (see divisibility ). Every prime number is itself its prime factorization. It remains to be shown that a prime factorization exists for the remaining natural numbers.

Assume the existence of such residual numbers for which no prime factorization exists. Because of the well-ordering of, there is a smallest such number . Since it is not a prime number, it has nontrivial factors with , where . Since is the smallest number for which there is no prime factorization, there is a prime factorization for (or ) (or ). Then a prime factorization of , is contrary to the assumption.

Proof of uniqueness

There is nothing to show for , and prime numbers. It remains to be shown that there is at most one prime factorization for the remaining natural numbers.

The existence of such remaining numbers is assumed, for each of which several different prime factorizations coexist. Because of the well-ordering of, there is a smallest such number . Several different prime factorizations of coexist at most (without contradiction) if two different prime factorizations of and of coexist. Besides, is not prime, so

Besides, one can assume. Because if there were a common factor, after re-sorting, for example , it would be . Since the minimum number is with two different factors, would be , and thus the above prime factorization would be identical. A contradiction to choosing .

Since the product divides, according to Euclid's lemma , a suitably chosen factor of this product also divides . However, this cannot be a prime factor , otherwise it would be . So hand out a product from just different elements . This argument can be repeated, that is, divides a product of different elements and so on. After all, an item must be part of it . Since these are prime numbers, it is . This is a contradiction.



There are several ways to generalize prime numbers. The best-known application is the whole numbers , where prime numbers can also have a negative sign . On the other hand, this is a special example because the prime factorization is also unique there (apart from the sign and sequence).

A general approach requires at least one notion of divisibility within the mathematical structure. David Hilbert proved that an additive structure is absolutely necessary for the desired clarity . Usually a commutative ring with one is assumed, there prime elements can be defined: An element is prime if Euclid's lemma applies to it. This does not guarantee that all elements of the ring have prime primes, but if there are any, then they are unique. In order to secure the existence, another property is necessary: ​​indivisibility. In order to be able to define them, one restricts the structure further and considers zero divisor-free rings (i.e. integrity rings ). There, irreducible elements can also be defined, but they cannot be called prime. They cannot be decomposed and contain the prime elements as a subset.

Decompositions into irreducible elements in an integrity ring are not necessarily unique. In order to obtain a structure in which the product decompositions are unambiguous, one must explicitly demand this uniqueness, which leads to the definition of factorial rings . With this requirement, however, the equivalence of irreducible and prime can be deduced there: Factorial rings are ZPE rings . A slightly different approach is pursued with prime ideals .


Also on the triangular grid of the Eisenstein numbers there is a prime factorization for each grid point
  • In the integrity ring , the elements are not prime elements but are irreducible and no two are associated with each other . The following applies: . So one cannot speak of a prime factorization.
  • An irreducible polynomial is called a prime polynomial if the leading coefficient is the same . In the polynomial ring over a body , every non-constant polynomial can essentially be represented uniquely as a product of prime polynomials.
  • Both the Gaussian numbers and the Eisenstein numbers always have a prime factorization (except for the 0).

Practical use


From the prime factorization of two numbers it can be seen whether one number is divisible by the other. The least common multiple ( lcm ) and the greatest common divisor ( gcd ) can easily be determined from the prime factorization. In the calculation of fractions , fractions can be reduced by the GCF of the numerator and denominator. When adding and subtracting, two fractions are expanded to the LCM of the denominator.

From the canonical prime factorization

the number of divisors of is obtained by increasing the exponents by one and then multiplying them together:


Prime numbers play an important role in cryptography . Encryption systems like RSA are based on the fact that no efficient factoring method is known. In this way, it is possible to find two 500-digit prime numbers and multiply them with one another within seconds. With today's methods, the recovery of the two prime factors from this 999- or 1000-digit product would take a very long time.

God numbers

For every enumeration of prime numbers without repetition, the is through

Defined mapping of all tuples of whole numbers injectively and calculable, the inverse function can also be calculated through prime factorization. The figure is therefore suitable for defining Godel numbers .


  • Jürgen Wolfart: Introduction to algebra and number theory . Vieweg, Braunschweig / Wiesbaden 1996, ISBN 3-528-07286-5 .

Web links

Wiktionary: prime factorization  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. ^ Franz Lemmermeyer: On the number theory of the Greeks
  2. Thomas Kantke: Cheap and expensive numbers . In: Spectrum of Science - SPECIAL: Omega . No. 4/2003 . Spectrum of Science, Heidelberg 2003, p. 68-74 .
  3. Jürgen Wolfart: Introduction to Algebra and Number Theory . Vieweg, Braunschweig / Wiesbaden 1996, ISBN 3-528-07286-5 , pp. 72, 37 .