Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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