Maths Olympiad Prep

Library / /12 of 31

Number theory Difficulty 6.4 National Olympiad Prove it Italy

Problem:

(a) Prove that for every positive integer nn there exist two sequences of length nn, with no elements in common, a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and b1,b2,,bnb_{1}, b_{2}, \ldots, b_{n}, such that for every ii between 1 and nn the greatest common divisor of aia_{i} and bib_{i} is equal to 1.

(b) Prove that for every positive integer nn there exist two sequences of length nn, with no elements in common, a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and b1,b2,,bnb_{1}, b_{2}, \ldots, b_{n}, such that for every ii between 1 and nn the greatest common divisor of aia_{i} and bib_{i} is greater than 1.

Solution

Solution:

(a) Let us fix nn consecutive numbers a1,a2,,ana_{1}, a_{2}, \ldots, a_{n}. Now let dd be a number larger than nn that has no common factors with any of a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} (for instance, a prime number larger than ana_{n}), and set b1=a1+d,b2=a2+d,,bn=an+db_{1} = a_{1} + d, b_{2} = a_{2} + d, \ldots, b_{n} = a_{n} + d; then a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and b1,b2,,bnb_{1}, b_{2}, \ldots, b_{n} are two sequences of length nn that are disjoint from each other and such that, for every ii between 1 and nn, the greatest common divisor of aia_{i} and bib_{i} is equal to 1: indeed, if a common factor of aia_{i} and bib_{i} existed, it would also be a factor of biai=db_{i} - a_{i} = d, and this is impossible, because dd and aia_{i} have no common factors.

(b) Similarly as before, let us fix a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} consecutive, with a1>1a_{1} > 1; let us then take an integer d>nd > n that has factors in common with each of the elements a1,,ana_{1}, \ldots, a_{n} (for instance, the product a1a2ana_{1} a_{2} \cdots a_{n}), and set b1=a1+d,b2=a2+d,,bn=an+db_{1} = a_{1} + d, b_{2} = a_{2} + d, \ldots, b_{n} = a_{n} + d. Once again the sequences a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and b1,b2,,bnb_{1}, b_{2}, \ldots, b_{n} are disjoint from each other, but in this case aia_{i} and bib_{i} always have a common factor: indeed aia_{i} and dd always have a common factor, and hence the same is true for aia_{i} and d+ai=bid + a_{i} = b_{i}.

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 translated into English from it; metadata (topic, difficulty) added by this project.