I am trying to proof the following result:
For a number $n$ whose prime number decomposition is $p_1^{\alpha _1} ... p_m^{\alpha _m}$. Every divisor of $n$ has the form $p_1^{\beta _1} ... p_m^{\beta _m}$ with $0 \leq \beta _i \leq \alpha_i$, for all $1 \leq i \leq m$.
Proving that every number of the form $p_1^{\beta _1} ... p_m^{\beta _m}$ is a divisor of $n$ is quite easy.
For the converse part, I have a sort of algorithm (which stands as a proof I guess) but I have some trouble in the formulation.
Let $d$ be a divisor of $n$. We write $n$ in the following alternating form: $n=p_1 ...p_{r}$ (where $r=\Omega (n)$ is the number of prime factors with multiplicity).
- if $d= 1$, we're done with $\beta _i = 0$ for all $1 \leq i \leq m$
- if not, $d$ has a unique prime number decomposition. In particular, there exists a prime number $p$ dividing $d$. So, $p\mid n$ and we conclude that $\exists {j_1}, 1\leq {j_1} \leq r$ such as $p = p_{j_1}$
Then, we consider the number $\frac{d}{p_{j_1}}$, there are two cases:
- either $\frac{d}{p_{j_1}} = 1$, in that case, the algorithm is finished and we have $d=p_{j_1}$ with $p_{j_1}$ being one of the prime numbers appearing in the decomposition of $n=p_1 ...p_{r}$
- either $\frac{d}{p_{j_1}} > 1$, in which case $\frac{d}{p_{j_1}}$ has a unique prime number decomposition. In particular there exists a prime number $p$ (not necessarily distrinct from $p_{j_1}$) dividing $\frac{d}{p_{j_1}}$. So, $p$ divides $\frac{n}{p_{j_1}}$ and hence, $\exists j_2 , 1\leq j_2 \leq r, j_2\neq j_1$ such as $p=p_{j_2}$
Then, we consider the number $\frac{d}{p_{j_1}p_{j_2}}$, there are two cases:
- either $\frac{d}{p_{j_1}p_{j_2}} = 1$, in that case, the algorithm is finished and we have $d=p_{j_1}p_{j_2}$ with $p_{j_1}p_{j_2}$ being two of the prime numbers appearing in the decomposition of $n=p_1 ...p_{r}$
- either $\frac{d}{p_{j_1}p_{j_2}} > 1$, in which case $\frac{d}{p_{j_1}p_{j_2}}$ has a unique prime number decomposition. In particular there exists a prime number $p$ dividing $\frac{d}{p_{j_1}p_{j_2}}$. So, $p$ divides $\frac{n}{p_{j_1}p_{j_2}}$ and hence, $\exists j_3 , 1\leq j_3 \leq r, j_3 \neq j_2\neq j_1 $ such as $p=p_{j_3}$
The algorithm may stop at any $j_s$ with $s\leq r$.
The farthest the algorithm can go is at the point where we reach $p_{j_r}$, the last prime number in the permutation defined by $(j_1,...,j_r)$. In that case, since we are out of prime numbers in the list $(p_1, ...,p_r)$ we have that $\frac{d}{p_{j_1}... p_{j_r}} \mid 1$ (since all the prime numbers of $n=p_1 ...p_{r}$ are present in the denominator). Whence, $d = p_1 ... p_r$
I wonder if my proof is Ok. Specifically, I wonder whether it could be shortened by considering in the decomposition of $d$ his smallest prime divisor.
Thank you in advance.