Integer factorization

The prime factorization is the representation of a natural number as a product of prime numbers, which are then referred to as the prime factors of. This representation is (up to the order of the factors ) and clearly one of the most basic and classic tools of number theory. It is the subject of the fundamental theorem of arithmetic. It is so far no known efficient factorization in order to maintain the prime factors of any number.

• 5.1 Examples

• 6.1 cryptography

Definitions

Let be a natural number. A number is called prime factor of,

The prime factorization is the representation of the number as a product of its prime factors. Since multiplication is commutative and associative, the order of the prime factors from the viewpoint of number theory is unimportant. The prime factorization of the fuel can be considered as an empty product. If itself is a prime number, it is even their only prime factor. Is there more than one prime factor, so composite number is called. The zero is never part of the multiplicative group and will be excluded from such considerations.

Other words, multiple prime factors can be summarized by means of exponent notation. Are the prime factors in ascending order, one also speaks of the canonical prime factorization:

The exponent of a prime factor is the multiplicity of in and is also referred to as a rating of. It specifies how often is divisible by.

Examples of prime factorizations

Fundamental Theorem of Arithmetic

The statements for existence of the prime factorization for each natural number and its uniqueness in the canonical representation are called the fundamental theorem of arithmetic, and fundamental theorem of elementary number theory. Both statements are stated and proved separately. The proofs are elementary, are classically formulated as a proof by contradiction and use the well-ordering of the natural numbers. Proved completely and correctly the first time we find the fundamental theorem of arithmetic in the Disquisitiones Arithmeticae of Carl Friedrich Gauss. But he was already - albeit in a slightly modified form - known Euclid.

Proof of the existence

The submitter is assigned the empty product and every prime number is even out its prime factorization It remains to show that all the remaining natural numbers are actually composed of prime factors.

Suppose that there are numbers that can not be represented as a product of prime numbers, then there is a smallest such number ( called ), due to the well-ordering of. Since then the fuel is still not a prime number, it has a divider so that there are two natural numbers, and both are greater than one and smaller than. Since the smallest number that is not a product of prime factors, and so must have prime factorizations, and about. Then, however, is also a prime factorization of, contradicting the assumption.

Proof of the uniqueness

Suppose that there are natural numbers, each with a plurality of different partitions, then again a smallest known. This can not be a prime and two decompositions can contain no common prime factor, then there would also have two different decompositions and smaller than would be in contradiction to the assumption that is minimal. It applies, for example, where and are primes, and it is. The final argument is the lemma of Euclid: Does a prime number the product, as well as one of the factors. There is divisible by one of the factors of the other cutting through must be divisible and that is because is prime. So any prime factor appeared always in both decompositions, and thus they are identical.

Properties

• And can have no common prime factors.
• To calculate the prime factorization of a number, there are several factorization is available, calculate the non-trivial divisor of integers. This task is known as factoring integers and can not be computed efficiently, whereupon security concepts are based worldwide, especially in modern cryptography with the previously known methods. See also primality test.
• Hardy proved more amazing statistical findings on the subject, among other things, that the average number of prime factors nascent for larger grows very slowly and as though, so the double- applied natural logarithm. The set of Erdős - Kac also stipulates that the number of prime factors is asymptotically normally distributed with mean and standard deviation. (For the notation see Landau symbols. )
• The function that maps each natural number to the number of its pairwise distinct prime factors, is an example of an arithmetic function that is additive but not strictly additive. They must be distinguished from the divider number function, which counts all divisors of a number, not only the prime divisors. For example, because the prime factorization contains two different prime numbers: 2 and 5 shall apply with the above definition.
• The asymptotic arithmetic mean of the maximum exponents of the prime factorizations of the numbers 1, 2, 3, ... is the Niven constant ( around 1.7 ), the asymptotic arithmetic mean of the minimum exponent is exactly 1

Generalization

There are several ways to generalize primes. The best known application are the integers, prime numbers can also have a negative sign there. On the other hand, this is already a specific example, since there the prime factorization (up to sign and order) is unique.

A general approach requires at least a notion of divisibility within the mathematical structure. David Hilbert proved that for the desired uniqueness of an additive structure is imperative. Usually it is assumed that a commutative ring with unity, there primes can be defined as: An element is prime if Euclid's lemma holds for it. This does not guarantee that it is for all elements of the ring decompositions into primes, but if there are any, then they are unique. To ensure the existence, another property is needed: indecomposability. To be able to define, one restricts the structure further and considered divisors of zero rings ( ie rings integrity ), there can also be defined irreducible elements, but can not be called prime. They are irreducible and contain the prime elements as a subset.

Decompositions into irreducible elements in an integral domain are not necessarily unique. In order to obtain a structure in which the product decompositions are unique, you have to explicitly ask for this uniqueness, leading to the definition of factorial rings. With this demand, it is then but there already deduce the equivalence of irreducible and prime: Factorial rings are ZPE -rings. A slightly different approach is taken by prime ideals.

Examples

• In the integrity of the ring elements are not primes but irreducible, and no two are associated with each other. The rule is:. One can not speak of a prime factorization.
• An irreducible polynomial is called prime polynomial if the leading coefficient is equal. In the polynomial ring over a field every non-constant polynomial is essentially uniquely representable as a product of prime polynomials.
• Both always exists a factorization in the Gaussian numbers as well as the Eisenstein numbers. (except for 0)

Practical Application

From the prime factorization can be seen whether a number is divisible by another. The least common multiple (LCM ) and the greatest common divisor (gcd ) can be easily determined from the prime factorization. In the break statement breaks through the gcd of the numerator and denominator can be reduced. When adding and subtracting two fractions to the lowest common denominator to be expanded.

Cryptography

Play an important role primes in cryptography. Encryption systems such as RSA based on the fact that no efficient factorization is known. So it is easily possible within seconds to find two 500 - digit prime numbers and multiply each other. With today's methods, the recovery of the two prime factors of 999 that would - or 1000 - digit product, however, take a very long time.