Prime factorization

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. ${\displaystyle n}$ ${\displaystyle n}$

number	Factors	number
2	${\displaystyle 2}$	1
3	${\displaystyle 3}$	1
4th	${\displaystyle 2^{2}}$	2
5	${\displaystyle 5}$	1
6th	${\displaystyle 2\cdot 3}$	2
7th	${\displaystyle 7}$	1
8th	${\displaystyle 2^{3}}$	3
9	${\displaystyle 3^{2}}$	2
10	${\displaystyle 2\cdot 5}$	2
11	${\displaystyle 11}$	1
12	${\displaystyle 2^{2}\cdot 3}$	3
13	${\displaystyle 13}$	1
14th	${\displaystyle 2\cdot 7}$	2
15th	${\displaystyle 3\cdot 5}$	2
16	${\displaystyle 2^{4}}$	4th
17th	${\displaystyle 17}$	1
18th	${\displaystyle 2\cdot 3^{2}}$	3
19th	${\displaystyle 19}$	1
20th	${\displaystyle 2^{2}\cdot 5}$	3

Definitions

Be a natural number. A number is called the prime factor of , ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$

if is a divisor of and ${\displaystyle p}$ ${\displaystyle n}$

${\displaystyle p}$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 : ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p}$

${\displaystyle n=p_{1}^{\;\;e_{1}}\cdot p_{2}^{\;\;e_{2}}\dotsm p_{M}^{\ \ e_{M}}=\prod _{k=1}^{M}p_{k}^{\;\;e_{k}}}$       Among the prime factors are several. ${\displaystyle N\left(=\sum _{k=1}^{M}e_{k}\right)}$ ${\displaystyle M}$

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 . ${\displaystyle e_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle n}$ ${\displaystyle p_{k}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p_{k}}$

Examples of prime factorization

${\displaystyle 30=2\cdot 3\cdot 5}$

${\displaystyle 37=37\ }$ (Prime number)

${\displaystyle 1001=7\cdot 11\cdot 13}$

${\displaystyle 1024=\underbrace {2\cdots 2} _{\text{10-mal}}=2^{10}}$( Power of two )

${\displaystyle 6936=2\cdot 2\cdot 2\cdot 3\cdot 17\cdot 17}$, with the canonical representation ${\displaystyle 2^{3}\cdot 3\cdot 17^{2}}$

${\displaystyle 10000=2^{4}\cdot 5^{4}}$( 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. ${\displaystyle 0\in \mathbb {N} }$ ${\displaystyle 1\in \mathbb {N} }$

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. ${\displaystyle \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle n>1}$ ${\displaystyle n}$ ${\displaystyle a,b\in \mathbb {N} }$ ${\displaystyle ab=n}$ ${\displaystyle 1<a,b<n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a=\Pi p_{i}}$ ${\displaystyle b=\Pi q_{j}}$ ${\displaystyle \Pi p_{i}\cdot \Pi q_{j}}$ ${\displaystyle n}$

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. ${\displaystyle 0\in \mathbb {N} }$ ${\displaystyle 1\in \mathbb {N} }$

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 ${\displaystyle \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \Pi _{i=1}^{r}p_{i}}$ ${\displaystyle \Pi _{j=1}^{s}q_{j}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle r,s\geq 2}$

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 . ${\displaystyle \{p_{1},\cdots ,p_{r}\}\cap \{q_{1},\cdots ,q_{s}\}=\emptyset }$ ${\displaystyle p_{1}=q_{1}}$ ${\displaystyle {\frac {n}{p_{1}}}<n}$ ${\displaystyle n}$ ${\displaystyle \{p_{2},\cdots ,p_{r}\}=\{q_{2},\cdots ,q_{s}\}}$ ${\displaystyle n}$

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. ${\displaystyle p_{1}}$ ${\displaystyle n=\Pi q_{j}}$ ${\displaystyle p_{1}}$ ${\displaystyle \{q_{1},\cdots ,q_{s}\}}$ ${\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}$ ${\displaystyle p_{1}}$ ${\displaystyle s-1}$ ${\displaystyle \{q_{1},\cdots ,q_{s}\}}$ ${\displaystyle p_{1}}$ ${\displaystyle s-2}$ ${\displaystyle \{q_{1},\cdots ,q_{s}\}}$ ${\displaystyle p_{1}}$ ${\displaystyle \{q_{1},\cdots ,q_{s}\}}$ ${\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}$

properties

• ${\displaystyle n}$and can not have prime factors in common . ${\displaystyle n+1}$
• To calculate the prime factorization of a number, several factorization methods are available that calculate nontrivial divisors of integers. This task is known as a factorization problem for whole numbers and cannot be calculated efficiently with the methods known up to now , on which security concepts worldwide are based, especially in modern cryptography . See also prime number test .
• Hardy proved several astonishing statistical findings on the subject, among other things that the average number of prime factors for increasing increases only very slowly, like the double applied natural logarithm . The set of Erdos Kac stating, moreover, that the number of prime factors asymptotically normally distributed , with an expected value and a standard deviation . (For notation see Landau symbols .) ${\displaystyle n}$ ${\displaystyle \ln(\ln(n))}$ ${\displaystyle \ln \ln n+{\mathcal {O}}(1)}$ ${\displaystyle {\mathcal {O}}({\sqrt {\ln \ln n}})}$
• The function that maps every natural number to the number of its pairwise different prime factors is an example of an arithmetic function that is additive but not strictly additive . It is to be distinguished from the divisor number function , which counts all the divisors of a number, not just the prime divisors. For example, is because the prime factorization contains two different prime numbers: 2 and 5. With the above definition applies: . ${\displaystyle \omega (n)}$ ${\displaystyle \omega (1000)=2}$ ${\displaystyle \omega (n)=M}$
• The asymptotic arithmetic mean of the maximum exponents of the prime factorization of the numbers 1, 2, 3, ... is the Niven constant (around 1.7), the asymptotic arithmetic mean of the minimum exponents is exactly 1.
• The asymptotic expectation of the relative number of digits of the largest prime factor of a number is given by the Golomb-Dickman constant . ${\displaystyle \gamma \approx 0{,}62433}$

generalization

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 .

Examples

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. ${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$ ${\displaystyle 2,3,1\pm {\sqrt {-5}}}$ ${\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\cdot \left(1-{\sqrt {-5}}\right)}$
• 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. ${\displaystyle 1}$ ${\displaystyle K[x]}$ ${\displaystyle K}$
• Both the Gaussian numbers and the Eisenstein numbers always have a prime factorization (except for the 0).

Practical use

Divider

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

${\displaystyle n=\prod _{k=1}^{M}p_{k}^{\;\;e_{k}}}$

the number of divisors of is obtained by increasing the exponents by one and then multiplying them together: ${\displaystyle T}$ ${\displaystyle n}$

${\displaystyle T=\prod _{k=1}^{M}{(e_{k}+1)}}$

Cryptography

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 ${\displaystyle p_{1},p_{2},\ldots }$

${\displaystyle (e_{1},e_{2},\ldots ,e_{M})\mapsto p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{M}^{e_{M}}}$

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 . ${\displaystyle e_{1},e_{2},\ldots ,e_{M-1}\geq 0,\ e_{M}>0}$

literature

• 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

• Factorization database by Markus Tervooren - fast processing, up to 200,000 decimal places
• The prime number page by Arndt Brünner - requires JavaScript , contains u. a. Prime factorization
• Factorization using the Elliptic Curve Method - Java applet , processes inputs up to 10,000 decimal places
• Video: prime factorization . Pedagogical University Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19878 .
• Video: The main theorem of elementary number theory (part 1) . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19874 .

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 .