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 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$ – Bill Dubuque Mar 4 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 at 22:41
  • 1
    $\begingroup$ What would need to hold if $\beta_i > \alpha_i$? $\endgroup$ – B.Swan Mar 4 at 22:53

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.