This site is supported by donations to The OEIS Foundation.

Prime factorization

From OeisWiki
(Redirected from Canonical prime factorization)
Jump to: navigation, search


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 ).
where
pi
is the
i
th prime number and
piαin
(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
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?[1]

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)

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: 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


Notes

External links