Maths Olympiad Prep

Library / /56 of 57

, 2008

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it JBMO

Problem:
Let n2n \geq 2 be a fixed positive integer. An integer will be called "nn-free" if it is not a multiple of an nn-th power of a prime. Let MM be an infinite set of rational numbers, such that the product of every nn elements of MM is an nn-free integer. Prove that MM contains only integers.

Solution

Solution:
We first prove that MM can contain only a finite number of non-integers. Suppose that there are infinitely many of them: p1q1,p2q2,,pkqk,\frac{p_{1}}{q_{1}}, \frac{p_{2}}{q_{2}}, \ldots, \frac{p_{k}}{q_{k}}, \ldots, with (pk,qk)=1(p_{k}, q_{k})=1 and qk>1q_{k}>1 for each kk. Let pq=p1p2pn1q1q2qn1\frac{p}{q}=\frac{p_{1} p_{2} \ldots p_{n-1}}{q_{1} q_{2} \ldots q_{n-1}}, where (p,q)=1(p, q)=1. For each ini \geq n, the number pqpiqi\frac{p}{q} \cdot \frac{p_{i}}{q_{i}} is an integer, so qiq_{i} is a divisor of pp (as qiq_{i} and pip_{i} are coprime). But pp has a finite set of divisors, so there are nn numbers of MM with equal denominators. Their product cannot be an integer, a contradiction.

Now suppose that MM contains a fraction ab\frac{a}{b} in lowest terms with b>1b>1. Take a prime divisor pp of bb. If we take any n1n-1 integers from MM, their product with ab\frac{a}{b} is an integer, so some of them is a multiple of pp. Therefore there are infinitely many multiples of pp in MM, and the product of nn of them is not nn-free, a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.