This article needs more work.
Please help by expanding it!
The
prime factorization of a
positive integer 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
is the
th prime number and
(i.e.
exactly divides
) means the highest power
of
that divides
.
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 has a unique (up to ordering)
prime factorization
-
where
is the
number of distinct prime factors of
and
are the
distinct prime factors of
.
Since the set
DPF(1) of
distinct prime factors of
1 is the
empty set and the
number of distinct prime factors is the
cardinality of the set of
distinct prime factors of
-
we get the cardinality of the
empty set, i.e.
0, for
.
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
is (tautologically) given by
-
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
.
Number of prime factors (with repetition)
The
number of prime factors (with repetition) of
is given by
-
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
.
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.
= 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
= 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
is the preferred format for writing the
prime factors that constitute a multiplicative partition of
. 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