Divisors of a Number
Let
\[n=p_1^{k_1}...p_r^{k_r}\]
.All divisors of
\[n\]
are of the form \[p_1^{s_1}...p_r^{s_r}\]
where \[0 \le s_i \le k_i, \; i=1,2,...,r\]
.Proof
Every integer of the above form certainly does divide
\[n\]
because \[n=(p_1^{s_1}...p_r^{s_r})(p_1^{k_1-s_1}...p_r^{k_r-s_r})\]
, where each \[s_i, \; k_i-s_i \ge 0\]
, so both of \[p_1^{s_1}...p_r^{s_r}, \; p_1^{k_1-s_1}...p_r^{k_r-s_r} \]
divide \[n\]
.Divisors of
\[n\]
with distinct sets of powers are distinct integers. Let \[d \gt 1\]
be any divisor of \[n\]
and let \[p\]
be a prime divisor of \[d\]
. \[p\]
divides \[d\]
and \[d\]
divides \[n\]
so \[p\]
divides \[n\]
. Hence \[p=p_i, \; 1 \e i \le r\]
. It follows that the only primes dividing \[d\]
are \[p_i, \; 1 \le i \le r\]
and we can write \[d=p_1^{s_1}...p_r^{s_r}\]
.In addition
\[d=p_1^{s_1}...p_r^{s_r}\]
divides \[n=p_1^{k_1}...p_r^{k_r}\]
. \[p_1\]
does not divide \[p_2^{k_2}...p_r^{k_r}\]
. The greatest common divisor of \[p_1, \; p_2^{k_2}...p_r^{k_r}\]
is 1. \[p_1^{s_1}\]
divides \[n=p_1^{k_1}...p_r^{k_r}\]
so by Euclid's Lemma for Prime Numbers, \[p_1^{s_1}\]
divides \[p_1^{k_1}\]
. Ditto for \[p_2, \; p_3,..., \; p_k\]
proves the theorem.
