Olympiad Maths Prep

Library / /3 of 9

, 2010

Number theory Difficulty 5.3 AIME, harder Prove it Ukraine

Natural numbers a,ba, b are chosen in such a way, that the number m=a+b+2ab+1m = a + b + 2\sqrt{ab+1} is natural. Prove that mm is composite.

Solutions — 2

Solution 1

Let us suppose that we can find such numbers a,ba, b, that p=a+b+2ab+1p = a + b + 2\sqrt{ab+1} is prime. Then ab+1ab+1 is complete square, aa and bb are distinct. By Cauchy-Schwartz inequality a+b2aba + b \ge 2\sqrt{ab}. Besides this, we have 2ab+1>2ab+1a+b2ab+12\sqrt{ab} + 1 > 2\sqrt{ab+1} \Rightarrow a + b \ge 2\sqrt{ab} + 1. pp is an odd number, because it is greater than 22, thus a+b2ab+1a + b - 2\sqrt{ab} + 1 is natural. From the equality (a+b+2ab+1)(a+b2ab+1)=(ab+2)(ab2)0(a + b + 2\sqrt{ab} + 1)(a + b - 2\sqrt{ab} + 1) = (a - b + 2)(a - b - 2) \ne 0 it follows, that either ab2a - b - 2 or ab+2a - b + 2 is divisible by pp, but absolute value of each of these two numbers does not exceed a+b+2a + b + 2, which is less than pp. This contradiction finishes the proof.

Solution 2

From the condition of the problem, it follows that 2ab+12\sqrt{ab+1} is a natural number, which immediately gives us that z=ab+1z = \sqrt{ab+1} is also a natural number. Therefore, b=z21a=(z1)(z+1)ab = \frac{z^2 - 1}{a} = \frac{(z - 1)(z + 1)}{a}. This implies that aa can be factored a=a1a2a = a_1 a_2 in such a way that z1z - 1 is divisible by a1a_1, and z+1z + 1 is divisible by a2a_2.

m=a+(z1)(z+1)a+2z=(a+z)21a=(a+z1)(a+z+1)a=a+z1a1+a+z+1a2m = a + \frac{(z - 1)(z + 1)}{a} + 2z = \frac{(a + z)^2 - 1}{a} = \frac{(a + z - 1)(a + z + 1)}{a} = \frac{a + z - 1}{a_1} + \frac{a + z + 1}{a_2}. Both factors a+z1a1\frac{a + z - 1}{a_1} and a+z+1a2\frac{a + z + 1}{a_2} are natural and greater than one, thus, mm is composite.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.