# Unjustified assumption in proving that if $d\mid n$ then $d$ only contains primes that occur in $n$

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

• 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. – samlanader Mar 4 at 22:36
• 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) – Bill Dubuque Mar 4 at 22:37
• 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. – samlanader Mar 4 at 22:41
• What would need to hold if $\beta_i > \alpha_i$? – 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$$.