# Set of Divisors of Integer

## Theorem

Let $n \in \Z_{>1}$.

Let $n$ be expressed in its prime decomposition:

$n = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$

where $p_1 < p_2 < \dotsb < p_r$ are distinct primes and $k_1, k_2, \ldots, k_r$ are positive integers.

The set of divisors of $n$ is:

$\set {p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r}: 0 \le h_i \le k_i, i = 1, 2, \ldots, r}$

## Proof

Each integer in the given set is a divisor of $n$ because:

$(1): \quad \forall i: k_i - h_i \ge 0$
$(2): \quad n = \paren {p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r} } p_1^{k_1 - h_1} p_2^{k_2 - h_2} \ldots p_r^{k_r - h_r}$

By the Fundamental Theorem of Arithmetic, these integers are distinct.

It is necessary to show that the integers in this set are the only divisors of $n$.

Let $d > 1$ and let $p \in \mathbb P: p \divides d$.

 $\displaystyle$  $\displaystyle p \divides d \land d \divides n$ $\displaystyle$ $\leadsto$ $\displaystyle p \divides n$ Divisor Relation on Positive Integers is Partial Ordering $\displaystyle$ $\leadsto$ $\displaystyle \exists i: p = p_i, 1 \le i \le r$ $\displaystyle$ $\leadsto$ $\displaystyle p \in \set {p_i: 1 \le i \le r}$ $\displaystyle$ $\leadsto$ $\displaystyle d = p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r}: 0 \le h_i$

It remains to be shown that:

$\forall i: h_1 \le k_i$

First note that:

$d \divides n \implies \forall i: p_i^{k_i} \divides n$

From above, all the primes $p_i$ are distinct.

Therefore by Prime not Divisor implies Coprime:

$p_1 \nmid p_2^{k_2} p_3^{k_3} \dotsm p_r^{k_r} \implies \gcd \set {p_1, p_2^{k_2} p_3^{k_3} \ldots p_r^{k_r} } = 1$

So:

$p_1^{h_1} \divides n \implies n = p_1^{k_1} \paren {p_2^{k_2} p_3^{k_3} \dotsm p_r^{k_r} }$
$p_1^{h_1} \divides p_1^{k_1} \implies h_1 \le k_1$

and the same argument applies to each of the other prime factors of $n$.

The result follows.

$\blacksquare$