Maths Olympiad Prep

Library / /16 of 22

Number theory Difficulty 8.8 Shortlist Prove it Germany

Problem:

We call a natural number nn balanced if n=1n=1 holds or if nn can be written as a product of an even number of (not necessarily distinct) prime factors. For each pair (a,b)(a, b) of positive integers let P(x)=(x+a)(x+b)P(x) = (x+a)(x+b).

a) Do there exist two distinct positive integers aa and bb for which all the numbers P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) are balanced?

b) Prove: If P(m)P(m) is balanced for all positive integers mm, then a=ba = b.

Solution

Solution:

a) The answer is "Yes". For P(x)P(x) to be balanced, x+ax+a and x+bx+b must either both have an even or both have an odd number of prime factors. With respect to this property, however, there are only 2502^{50}, hence finitely many, different patterns among 50 consecutive natural numbers. Therefore there exist two natural numbers mm and nn that are starting numbers of two identical such patterns. With a=m1a = m-1 and b=n1b = n-1, the balancedness of P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) follows.

b) We assume that under the given hypothesis there exist two distinct natural numbers aa and bb; without loss of generality let b>ab > a. Then for every natural number m>am > a we have that P(ma)=m(m+ba)P(m-a) = m(m + b - a) is balanced. The evenness or oddness of the number of prime factors thus occurs periodically for natural numbers greater than aa, with period length bab-a. In particular, all multiples of bab-a are also of the same type, as soon as they are greater than aa. However, such a multiple k(ba)k(b-a) has one fewer prime factor than 2k(ba)2k(b-a), a contradiction to the assumption. Hence a=ba = b.

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 de; metadata (topic, difficulty) added by this project.