Definition:Prime Decomposition

From ProofWiki
Jump to: navigation, search


Let $n > 1 \in \Z$.

From the Fundamental Theorem of Arithmetic, $n$ has a unique factorization of the form:

\(\displaystyle n\) \(=\) \(\displaystyle \prod_{p_i \mathop \divides n} {p_i}^{k_i}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle {p_1}^{k_1} {p_2}^{k_2} \cdots {p_r}^{k_r}\) $\quad$ $\quad$


$p_1 < p_2 < \cdots < p_r$ are distinct primes
$k_1, k_2, \ldots, k_r$ are (strictly) positive integers.

This unique expression is known as the prime decomposition of $n$.


For each $p_j \in \left\{ {p_1, p_2, \ldots, p_r}\right\}$, its power $k_j$ is known as the multiplicity of $p_j$.

Also known as

The prime decomposition of $n$ is also known as the prime factorization of $n$.


The prime decompositions for the first few integers are as follows:

$n$ Prime Decomposition of $n$
$1$ $1$
$2$ $2$
$3$ $3$
$4$ $2^2$
$5$ $5$
$6$ $2 \times 3$
$7$ $7$
$8$ $2^3$
$9$ $3^2$
$10$ $2 \times 5$
$11$ $11$
$12$ $2^2 \times 3$

Also see

  • Results about prime decompositions can be found here.

Linguistic Note

The UK English spelling of prime factorization is prime factorisation.