Prime factorization

This article needs more work.

Please help by expanding it!

The prime factorization of a positive integer

n

is the unique list of prime numbers (with repetition) whose product give that integer. For example, the prime factorization of 147 is 3, 7, 7 (or the prime power [components] factorization of 147 is 3 and 7 2 ).

${\begin{array}{l}\displaystyle {n=\prod _{\stackrel {i=1}{{p_{i}}^{\alpha _{i}}\parallel n,\,\alpha _{i}\geq 0}}^{\infty }{p_{i}}^{\alpha _{i}},}\end{array}}$

where

pi

is the

i

 th prime number and

pi α i ∥ n

(i.e.

pi αi

exactly divides

n

) means the highest power

αi

of

pi

that divides

n

.

For the unit, 1, there are no primes with nonzero exponents and we get the empty product, defined as the multiplicative identity, i.e. 1. For prime powers, exactly one prime exponent is nonzero (the exponent being 1 for primes). Per the fundamental theorem of arithmetic, the positive integers form a unique factorization domain.

Considering only the primes with positive exponents, a positive integer

n

has a unique (up to ordering) prime factorization

${\begin{array}{l}\displaystyle {n=\prod _{\stackrel {i=1}{{p_{i}}^{\alpha _{i}}\parallel n,\,\alpha _{i}\geq 1}}^{\omega (n)}{p_{i}}^{\alpha _{i}},}\end{array}}$

where

ω (n)

is the number of distinct prime factors of

n

and

pi > pi   − 1

are the distinct prime factors of

n

. Since the set DPF(1) of distinct prime factors of 1 is the empty set and the number of distinct prime factors

ω (n)

is the cardinality of the set of distinct prime factors of

n

ω (n) = | DPF(n) | ,

we get the cardinality of the empty set, i.e. 0, for

n = 1

.

Computational complexity class of prime factorization

Unsolved problem in computer science: Can integer factorization be done in polynomial time?

Number of distinct prime factors

The number of distinct prime factors of

n

is (tautologically) given by

ω (n) =   ω (n) ∑   i   = 1    αi 0,

where we get the empty sum, defined as the additive identity, i.e. 0 (the final value of the index being lower than the initial value) for

n = 1

.

Number of prime factors (with repetition)

The number of prime factors (with repetition) of

n

is given by

Ω (n) =   ω (n) ∑   i   = 1    αi 1,

where we get the empty sum, defined as the additive identity, i.e. 0 (the final value of the index being lower than the initial value) for

n = 1

.

Prime power decomposition of rational numbers

Allowing negative exponents gives us a way to express the unique “prime power decomposition” of any positive rational number (in reduced form)

${\begin{array}{l}\displaystyle {r=\prod _{\stackrel {i=1}{{p_{i}}^{\alpha _{i}}\parallel r,\,\alpha _{i}\in \mathbb {Z} }}^{\infty }{p_{i}}^{\alpha _{i}}.}\end{array}}$

E.g.

912

145

= 2 4 ⋅  3 1 ⋅  5  − 1 ⋅  7 0 ⋅  11 0 ⋅  13 0 ⋅  17 0 ⋅  19 1 ⋅  23 0 ⋅  29  − 1 ⋅  31 0 ⋅  ⋯.

Unique prime signature

We may consider this sequence of nonnegative exponents as forming an infinite exponents tuple in an infinite dimensional space where each dimension corresponds to a prime number, e.g. for 912 = 2 4 ⋅  3 1 ⋅  5 0 ⋅  7 0 ⋅  11 0 ⋅  13 0 ⋅  17 0 ⋅  19 1 ⋅  23 0 ⋅  ⋯, we get the infinite exponents tuple

(4, 1, 0, 0, 0, 0, 0, 1, 0, ...)

for which, after truncating the (0, ...) tail, we obtain an finite exponents tuple, which we may consider as the unique prime signature for that integer

(4, 1, 0, 0, 0, 0, 0, 1)

and for 1 = 2 0 ⋅  ⋯ we get the infinite exponents tuple

(0, ...)

for which, after truncating the (0, ...) tail, we obtain the empty exponents tuple, which we may consider as the unique prime signature for 1

( ).

Unique prime signature for rational numbers

For

912

145

= 2 4 ⋅  3 1 ⋅  5  − 1 ⋅  7 0 ⋅  11 0 ⋅  13 0 ⋅  17 0 ⋅  19 1 ⋅  23 0 ⋅  29  − 1 ⋅  31 0 ⋅  ⋯, we get the infinite exponents tuple

(4, 1,  −1, 0, 0, 0, 0, 1, 0,  −1, 0, ...)

for which, after truncating the (0, ...) tail, we obtain an finite exponents tuple, which we may consider as the unique prime signature for that rational number

(4, 1,  −1, 0, 0, 0, 0, 1, 0,  −1).

Canonical prime factorization

The canonical prime factorization of an integer

n

is the preferred format for writing the prime factors that constitute a multiplicative partition of

n

. The following rules essentially codify notational practice of the last half millennium or so:

• The distinct prime factors (i.e. without repetition) are given in ascending order;
• Exponents are used to indicate the multiplicity of the distinct prime factors.

For example, the canonical prime factorization of 44100 is 2 2 ⋅  3 2 ⋅  5 2 ⋅  7 2. Per the fundamental theorem of arithmetic,

ℤ

is a unique factorization domain and reorderings of the factors do not constitute different factorizations (

ℤ

being a commutative ring). While we can give the prime factorization of 44100 as 2 ⋅  5 2 ⋅  3 2 ⋅  7 ⋅  2 ⋅  7 (as one of many different possibilities), using the canonical prime factorization reduces the possibility of errors of transcription.

Note that these rules do not specify a preference for one multiplication operator over another. Either the multiplication cross ( × ) or the multiplication dot ( ⋅  ) are acceptable, as long as the two are not used in the same formula.

Note also that these rules do not specify what to do with negative integers (we may just prepend the unit  − 1, e.g.  − 44100 is ( − 1) ⋅  2 2 ⋅  3 2 ⋅  5 2 ⋅  7 2 ).

Computer Algebra Systems

The factorization is available in PARI/GP via “factor(n)” and “FactorInteger[n]” in Mathematica.

See also

• Tables of prime factorization

• {{Prime factors (with multiplicity)}} (or {{mpf}} or {{factorization}}) arithmetic function template (prime factorization template)

External links

• http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/
• http://factordb.com/
• Yuval Filmus, Factorization Methods: Very Quick Overview.