Let n have prime factorization n = p^s1 · p^s2 · · · p^sk
and let m have prime factorization m = q^t1 · q^t2 · · · q^tl
If n|m, what must be true about the corresponding lists of primes and the powers in these two prime factorizations?
I'm reviewing for my final and don't know what is true...help is appreciated!
On
Every prime $p_i$ in $n$ appears once as a $q_i$ in $m$, and furthermore, every corresponding power of these is less than or equal to the powers of the former. That is, for each of these $p_i$ its power is $s_i$ and for $q_i$ its power is $t_i$, for $p_i=q_i$ then $s_i \le t_i$.
Proof by example:
Say $m=2^35^77^4$ and $n=2^35^27^4$, then $$\frac{m}{n}=\frac{2^35^77^4}{2^35^27^4}=2^{3-3}5^{7-2}6^{4-4}=2^05^56^0=5^5.$$ On the other hand if instead $n=2^45^77^4$
$$\frac{m}{n}=\frac{2^35^77^4}{2^45^27^4}=2^{3-4}5^{7-2}6^{4-4}=2^{-1}5^56^0=2^{-1}5^5=\frac{5^5}{2}.$$
It may be helpful to write the factorizations more precisely, so that we can say more about them:
$$n=p_1^{s_1}\cdot p_2^{s_2} \cdots p_k^{s_k}$$
$$m=q_1^{t_1}\cdot q_2^{t_2} \cdots q_k^{t_h}$$
I replaced your $l$ with $h$ because it is slightly easier to read in the subscript of the exponent. In any case, we can choose the $p_i$ and the $q_j$ so that $$p_1 < p_2 \cdots < p_k$$ $$q_1 < q_2 \cdots < q_h$$
If $n\,|\,m$, by definition we have $$\exists\, x \in \mathbb{Z} \,\,\,\,\text{ s.t. }\,\,\, m=nx$$
Suppose a prime $r \in \mathbb{Z}$ divides $n$. Then there exists a $y \in \mathbb{Z}$ such that $n=ry$. So we can substitute to get $m=rxy$, which means the prime $r$ divides $m$.
In other words, if any prime divides $n$, it must divide $m$ as well.
This means that the set of primes in the prime factorization of $n$ is a subset of the set of primes in the prime factorization of $m$. This allows us to say $$k \leq h$$
Further, if $p_i=q_j$, then the exponents must satisfy $$s_i \leq t_j$$