# If $a,b >1$ prove that $a$ divides $b$ iff $m_i\leq n_i$ for $1\leq i\leq r$.

If $a,b >1$ prove that $a$ divides $b$ iff $m_i\leq n_i$ for $1\leq i\leq r$. (Exponents ${n_i}$ with $r+1 \leq i \leq s$, if there are any, are unrestricted)

where $a = \prod_{i=1}^{r}p_i^{m_i}$ and $b = \prod_{i=1}^{s}p_i^{n_i}$

$sp(a)$ = {$p_1,p_2,...,p_r$} and $sp(b)$ = {$p_1,p_2,...,p_s$} with $r \leq s$

I am really stuck at this one. If anyone knows how to prove this, please help me.

Thanks!

-
Have you tried some small examples? For example, check what it all means for $30|120$. – Berci Feb 24 '13 at 3:11
It follows pretty quickly from the definition of "$a$ divides $b$", so I'd recommend writing out that definition, and applying it. – Gerry Myerson Feb 24 '13 at 3:22

Until you are unfamiliar with the notation, use the one you already know, e.g. $a=p_1^{m_1}\cdot p_2^{m_2}\cdot \dots$ and $b=p_1^{n_1}\cdot p_2^{n_2}\cdot \dots$. We can also allow $0$ exponents ($p^0=1$).

For a proof, first consider the case when $m_i>n_i$ for some $i$. Then $p_i^{m_i}|a$ but $p_i^{m_i}\!\!\not| b$.

For the other direction (if all $m_i\le n_i$), conclude that $b/a$ is integer.

-
The proof must use the hypothesis that the $\,p_i\,$ are prime (or pair-coprime), since otherwise the statement is false. As such, it essential to explicitly mention where it used in the proof. – Math Gems Feb 24 '13 at 3:58
My answer is mainly a hint. $p_i$ being coprime to the rest $p_j$'s is used in the non written consequense that $a\!\!\not| b$ follows from ( $p_i^{m_i}|a$ but ${p_i}^{m_i}\!\!\not|b$). – Berci Feb 24 '13 at 12:11

Hint $\$ The $\,\rm\,p_i\,$ need not be primes - it suffices that they are $\,> 1$ and pairwise coprime. For the nontrivial direction, if $\rm\: j > k\:$ and $\rm\:p_1^j\mid p_1^k p_2^e\cdots p_n^f\:$ then $\rm\:p_1\mid p_1^{j-k}\mid p_2^e\cdots p_n^f,\:$ which contradicts Euclid's Lemma, i.e. that $\rm\,p_1\,$ coprime to $\rm\,p_2,\ldots,p_n\:\Rightarrow\: p\,$ coprime to any product of them (alternatively, it contradicts the uniqueness of (co-)prime factorizations).

-