Set of Divisors of an Integer

Theorem

Let $n \in \Z: n > 1$.

Let $n$ be expressed in its Prime Decomposition:

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

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

The set of divisors of this integer can be found to be:

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

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 = \left({p_1^{h_1} p_2^{h_2} \ldots p_r^{h_r}}\right) p_1^{k_1-h_1} p_2^{k_2-h_2} \ldots p_r^{k_r-h_r}$

from Prime Decomposition Divisor.

By the uniqueness of Prime Decomposition, these integers are distinct.

• Now we need to show that the integers in this set are the only divisors of $n$.

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

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle p \backslash d \land d \backslash n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle p \backslash n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Divides is Ordering on Positive Integers
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists i: p = p_i, 1 \le i \le r\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle p \in \left\{ {p_i: 1 \le i \le r}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle d = p_1^{h_1} p_2^{h_2} \ldots p_r^{h_r}: 0 \le h_i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Now we need to show that $\forall i: h_1 \le k_i$.

First note that:

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

Next, we know that all the primes $p_i$ are distinct, and therefore by Prime Not Divisor then Coprime:

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

So:

$p_1^{h_1} \backslash n \implies n = p_1^{k_1} \left({p_2^{k_2} p_3^{k_3} \ldots p_r^{k_r}}\right)$

By Euclid's Lemma:

$p_1^{h_1} \backslash 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$