# Proof help involving prime factorization, exponents

Let $a,b\in\mathbb{N}$. Moreover, let $p_1,p_2,...,p_k$ be the collection of all primes which divide $a$ or $b$ or both. We'll write $a=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ and $b=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$ by the unique factorization theorem. Notably, some $\alpha_i$'s and some $\beta_i$'s might be $0$.

I am asked to prove that $a|b$ if and only if $\alpha_i \leq \beta_i$ for each $i$.

My thoughts so far (forward direction):

Since $a|b$, $\exists k \in \mathbb{Z}$ such that $ak=b$. By the unique factorization theorem, $k$ can be broken up into the same $p_1^{\gamma_1}p_2^{\gamma_2}...p_k^{\gamma_k}$ format for $\gamma_i \geq 0$.Thus, $ak=b$ can be rewritten as $p_1^{\alpha_1 + \gamma_1}p_2^{\alpha_2 + \gamma_2}...p_k^{\alpha_k + \gamma_k}=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$. How can I rigorously say that since $\alpha_i+\gamma_i=\beta_i$, $\alpha_i \leq \beta_i$?

And then there's the backward direction...

• $\gamma_i$ is always positive or null !
– user354674
Sep 7, 2016 at 1:26

By the unique factorization theorem, $\alpha_i+\gamma_i=\beta_i$. Since $\gamma_i\geq 0$ then $\alpha_i\leq\alpha_i+\gamma_i=\beta_i$.