Set of Divisors of Integer

From ProofWiki
Jump to: navigation, search

Theorem

Let $n \in \Z_{>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 $n$ is:

$\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 Exponents of Primes in Prime Decomposition are Less iff Divisor.

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 \mathrel \backslash d$.

\(\displaystyle \) \(\) \(\displaystyle p \mathrel \backslash d \land d \mathrel \backslash n\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle p \mathrel \backslash 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 \left\{ {p_i: 1 \le i \le r}\right\}\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle d = p_1^{h_1} p_2^{h_2} \ldots 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 \mathrel \backslash n \implies \forall i: p_i^{k_i} \mathrel \backslash 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} \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} \mathrel \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} \mathrel \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$