Let $ m_1$, $ m_2$, $ \cdots$, $ m_r$ (may not distinct) and $ n_1$, $ n_2$ $ \cdots$, $ n_s$ (may not distinct) be two groups of positive integers such that for any positive integer $ d$ larger than $ 1$, the numbers of which can be divided by $ d$ in group $ m_1$, $ m_2$, $ \cdots$, $ m_r$ (including repeated numbers) are no less than that in group $ n_1$, $ n_2$ $ \cdots$, $ n_s$ (including repeated numbers). Prove that $ \displaystyle \frac{m_1 \cdot m_2 \cdots m_r}{n_1 \cdot n_2 \cdots n_s}$ is integer.
Problem
Source: China TST 2004 Quiz
Tags: number theory, prime factorization, number theory unsolved
pythag011
02.02.2009 05:30
By taking d = 1, we get $ r \ge s.$ Let $ a_i, b_i$ be the exponent of the greatest power of an arbitrary prime p that divides $ m_i,n_i,$ respectively. We order these numbers, so $ a_1 \ge a_2 \ge \ldots \ge a_r$ and $ b_1 \ge b_2 \ge \ldots \ge b_s.$ Then, we prove that if $ 1 \le i \le s,$ then $ a_i \ge b_i.$ Assume that $ a_i < b_i.$ Let $ d = p^b_i.$ Then, we get a contradiction, because since the $ a_i,b_i$ are ordered, at least i $ n_k$s are divisible by d, but at most i-1 $ m_k$s are divisible by d, a contradiction, so the power of p in $ m_1m_2\ldots m_r$ is clearly greater than or equal to the power of p in $ n_1n_2\ldots n_s.$ This is true for every prime p, so QED.
tobash_co
16.12.2011 11:09
pythag011 wrote: By taking d = 1, we get $ r \ge s.$ Just to point out that this isn't valid, since $d>1$, but pythag didn't use it anyways. Let $v_p(a)$ be the exponent of p in prime factorization of a. For each integer d let $M_d, N_d$ be the number of $m_i, n_i$ divisible by d respectively. Then clearly $v_p(m_1m_2...m_r)=M_p+M_{p^2}+...+M_{p^n}+...$ and $v_p(n_1n_2...n_s)=N_p+N_{p^2}+...+N_{p^n}+...$. But since $M_d\ge N_d$ for all d, $v_p(m_1m_2...m_r)\ge v_p(m_1m_2...m_r)$ and we're done.