= Fundamental theorem of arithmetic
{title2=$n=\prod_{p\mid n}p^{v_p(n)}$}
{wiki}
= Prime factorization
{synonym}
= Unique prime factorization
{synonym}
= Prime factorisation
{synonym}
Every <integer> $n>1$ is a <product> of <prime numbers>, uniquely up to reordering the factors. More precisely, there are unique distinct <prime numbers> $p_1<\cdots<p_r$ and unique positive <integer> exponents $a_1,\ldots,a_r$ such that
$$
n=p_1^{a_1}\cdots p_r^{a_r}.
$$
In the header's displayed form, $v_p(n)$ is the <prime valuation>, the exponent of $p$ in this <prime factorization>; it is zero when $p$ does not divide $n$. Reordering or regrouping the <prime factors> does not give a different <prime factorization>.
For $360$, repeated <division> gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. Thus
$$
360=2\cdot2\cdot2\cdot3\cdot3\cdot5=2^3\cdot3^2\cdot5,
\qquad 2^3\cdot3^2\cdot5=8\cdot9\cdot5=360.
$$
Its nonzero <prime valuations> are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct <prime factors> $2,3,5$ would lose the difference between $30$ and $360$.
This turns <divisibility> into coordinatewise comparison of nonnegative exponents. A positive <divisor> of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot3\cdot2=24$ positive <divisors>. The <greatest common divisor> takes the smaller exponent at each <prime number>; the <least common multiple> takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large <integer> is computationally easy.
In general, for <positive integers> $d,n$, the exact <divisibility> criterion is
$$
d\mid n\quad\Longleftrightarrow\quad v_p(d)\leq v_p(n)\ \text{for every prime }p.
$$
For example, $72=2^3\cdot3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only <prime factors> of $360$, so membership in that list alone does not establish <divisibility>. Every positive <divisor> of $360$ is uniquely $2^a3^b5^c$ with $0\leq a\leq3$, $0\leq b\leq2$, $0\leq c\leq1$. Sorted, all 24 positive <divisors> are
$$
\begin{gathered}
1,2,3,4,5,6,8,9,10,12,15,18,\\
20,24,30,36,40,45,60,72,90,120,180,360.
\end{gathered}
$$
Thus the <divisor function> gives $\tau(360)=(3+1)(2+1)(1+1)=24$. These include <divisors> that are <composite numbers>, as well as the <prime factors> and one.
For another <positive integer> $m$, the <prime valuations> give exact formulas for the <greatest common divisor> and <least common multiple>:
$$
\begin{aligned}
v_p(\gcd(n,m))&=\min\{v_p(n),v_p(m)\},\\
v_p(\operatorname{lcm}(n,m))&=\max\{v_p(n),v_p(m)\}.
\end{aligned}
$$
With $n=360$ and $m=84=2^2\cdot3\cdot7$, their <prime valuations> at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, hence
$$
\gcd(360,84)=2^2\cdot3=12,\qquad
\operatorname{lcm}(360,84)=2^3\cdot3^2\cdot5\cdot7=2520.
$$
Indeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd(n,m)\operatorname{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot2520=360\cdot84=30240$.
\Image[/prime-factorization-exponents.png]
{title=<Prime valuations> compute the <greatest common divisor>, <least common multiple> and all 24 positive <divisors> of 360}
{description=The upper table compares exponents at the <prime numbers> $2,3,5,7$ for $360$ and $84$, then takes their columnwise minimum and maximum. The lower tables enumerate $2^a3^b5^c$ for $c=0$ and $c=1$; each cell gives one positive <divisor>.}
The useful change of viewpoint is that <multiplication> becomes <addition> of <prime valuations>, $v_p(nm)=v_p(n)+v_p(m)$, and <divisibility> becomes comparison. Many different-looking calculations therefore share one representation. The <prime valuations> are coordinates for <multiplication>, rather than digits in <positional notation>: they do not turn ordinary <addition> of <integers> into coordinatewise <addition>.
Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot10$ gives $36=6\cdot6$ and $10=2\cdot5$; starting with $360=8\cdot45$ gives $8=2\cdot4$ and $45=5\cdot9$. Continuing to split the <composite numbers> produces the same <multiset> of <prime factors>: three twos, two threes, and one five. The <factorization tree> records choices in the calculation, while the <prime factorization> records the invariant result.
\Image[/prime-factorization-trees.png]
{title=Two <factorization trees> for $360$ give the same <prime factorization> $2^3\cdot3^2\cdot5$}
The proof outline explains the uniqueness. Existence follows by splitting a <composite number> into smaller factors until only <prime numbers> remain. For uniqueness, <Euclid's lemma> says that a <prime factor> of one <product> must divide one factor of any other prime <product> equal to it. That factor must be the same <prime number>; cancel it and repeat. The crucial <divisibility> step appears in Book VII, Proposition 30 of <Euclid's Elements>. https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html[Euclid, Elements VII.30: a prime divisor of a product]{ref}
The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every <composite number> has a <prime factor>, and Book IX, Proposition 14 excludes any new <prime factor> from the <least common multiple> of given <prime numbers>. These are the propositions being cited, rather than the complete modern exponent formulation of the <fundamental theorem of arithmetic>. https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII31.html[Euclid, Elements VII.31: every composite number has a prime divisor]{ref} https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX14.html[Euclid, Elements IX.14: prime divisors of a least common multiple of primes]{ref}
Excluding one from the <prime numbers> keeps uniqueness meaningful: otherwise $360=2^3\cdot3^2\cdot5=1\cdot2^3\cdot3^2\cdot5=1\cdot1\cdot2^3\cdot3^2\cdot5$ would give different collections of supposed <prime factors>. For $n=1$, the natural convention is the <empty product>, equal to one, with no <prime factors> and all <prime valuations> zero.
Back to article page
