How do I justify that $\beta_i \leq \alpha_i$ in my attempt at proving the following theorem.

I can neither figure out how to justify the assumption nor how to complete the proof without it.

Theorem: Let $n$ have prime factorization $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. Then $d$ is a divisor of $n$ if and only if $d$ has prime factorization $p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$ with $0 \leq \beta_i \leq \alpha_i$ for all $1\leq i \leq k $.

Proof: The statement is trivial both ways for $d=1=p_1^{0}p_2^{0}\cdots p_k^{0}$ so throughout we assume that $d>1$.

($\Rightarrow$) Let $n$ have prime factorization $p^{\alpha_1}p^{\alpha_2}\cdots p^{\alpha_k}$ and suppose $d$ is a divisor of $n$. So $n=dd'$ for some $d'>1$. Consider the prime factorizations of $d$ and $d'$ into primes $\{q_i\}$ and $\{q'_i\}$ respectively ($\{q_i\}$ and $\{q'_i\}$ are not necessarily distinct or disjoint): $$d=q_1q_2\cdots q_m \quad d=q'_1q'_2\cdots q'_n $$ Since $n=dd'$ by expressing $n$ in terms of its prime fractorization we find that $$p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}=q_1q_2\cdots q_mq'_1q'_2\cdots q'_n.$$ So by uniqueness of prime factorization each $q_i=p_j$ (Note: there may be many different $q_i$ equal to the same $p_j$), thus collecting like primes together we get find that $d$ has prime factorization $$d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}.$$ with each $\beta_i \leq \alpha_i$ as else d would not be a divisor of $n$.

  • $\begingroup$ I'm not quite sure how to complete this. $c \mid d \mid n \Rightarrow c \mid n$. So if $q^{\beta}\mid d$ we must have $q^{beta} \mid n$. But how do we know that $q=p$ and $\beta \leq \alpha$. I assume something with prime factorization theorem but I do not see how. $\endgroup$
    – samlanader
    Mar 4, 2019 at 22:36
  • $\begingroup$ What precisely is your question? What is the "unjustified assumption"? Why is it a "bad proof"? Are you only interested in this type of proof? (this was written before your prior comment appeared) $\endgroup$ Mar 4, 2019 at 22:37
  • $\begingroup$ The unjustified assumption was me not knowing how to show that $\beta_i \leq \alpha_i$. The "bad proof" was me trying to make a simplified proof, assuming that $\beta_i \leq \alpha_i$ did not need justification. $\endgroup$
    – samlanader
    Mar 4, 2019 at 22:41
  • 1
    $\begingroup$ What would need to hold if $\beta_i > \alpha_i$? $\endgroup$
    – B.Swan
    Mar 4, 2019 at 22:53

2 Answers 2


Let $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

And $d = q_1^{\beta_1}q_2^{\beta_2}\cdots q_j^{\alpha_j}$ be unique prime factorizations.

$q_i|d$ so $q_i|n$ so by euclid's lemma $q_i =p_m$ for some $p_m$ and $\{q_j\}\subset \{p_i\}$.

So $d = p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$ if we allow some $\beta_i$ to be $0$.

===== important bit below =====

Suppose there is a $\beta_i > \alpha_i$.

Then Let $d'= \frac d{p_i^{\alpha_i}} =p_1^{\beta_1}p_2^{\beta_2}\cdots p_i^{\beta_k - \alpha_k}\cdots p_k^{\beta_k}$ and $n' = \frac n{\alpha_i} = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_i^0 \cdots p_k^{\alpha_k}$

We know: $d'|n'$ that $\beta_i - \alpha_i > 0$. And $p_i \not \mid n'$.

But if $\beta_i - \alpha_i > 0$ then $\beta_i - \alpha_i \ge 1$ and $p_i|d'$ and so $p_i|n'$ which is a contradiction.

So all $\beta_i \le \alpha_i$.


Let $d=\prod q_i^{\nu_i}$. As clearly $q_i \mid q_i^{\nu_i}$ and $q_i^{\nu_i} \mid \prod p_i^{a_i}$ we get that $q_i \mid \prod p_i^{a_i}$. Hence $q_i=p_j$ for some $j$. Then $p_j^{\nu_j} \mid \prod p_i^{a_i} = p_j^{a_j} \prod_{i\neq j} p_j^{\nu_j}$. Since $(p_i,p_j)=1$ for all $i\neq j$ we get that $p_j^{\nu_j} \mid p_j^{a_j}$. Hence $\nu_j \leq a_j$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .