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}$
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 \divides d$.
| \(\ds \) | \(\) | \(\ds p \divides d \land d \divides n\) | ||||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds p \divides n\) | Divisor Relation on Positive Integers is Partial Ordering | |||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds \exists i: p = p_i, 1 \le i \le r\) | ||||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds p \in \set {p_i: 1 \le i \le r}\) | ||||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds 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} }$
By Euclid's Lemma:
- $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$