Maths Olympiad Prep

Library / /3 of 18

Number theory Difficulty 5.9 AIME, harder Prove it Vietnam

Let AA be the set of positive integers that can be written in the form 2x2+3y22x^2 + 3y^2 where x,yx, y are integers with x2+y20x^2 + y^2 \neq 0. Prove that:

a) All numbers from AA are not perfect square.

b) The product of an odd number of numbers from AA is not a perfect square.

Solution

a) Without loss of generality, we can consider this problem for nonnegative integers. We know that a perfect square gives the remainder 00 or 11 when divided by 33, so all numbers from AA when divided by 33 give the remainder 33 or 22.

Assume that there exists a pair (x0,y0)(x_0, y_0) such that 2x02+3y02A2x_0^2 + 3y_0^2 \in A is a perfect square and such that x0+y0x_0 + y_0 is minimal. Then this number should be divisible by 33, so x0x_0 is divisible by 33. Put x0=3x1x_0 = 3x_1 where x1Zx_1 \in \mathbb{Z}.

Thus 18x12+3y02=3(6x12+y02)18x_1^2 + 3y_0^2 = 3(6x_1^2 + y_0^2) is a perfect square. This number is divisible by 33, so it should be divisible by 99. So 6x12+y026x_1^2 + y_0^2 is divisible by 33. From which we have y0y_0 is divisible by 33. Put y0=3y1y_0 = 3y_1 where y1y_1 is an integer.

Putting back in original expression 2x02+3y022x_0^2 + 3y_0^2, we have 18x12+27y12=9(2x12+3y12)18x_1^2 + 27y_1^2 = 9(2x_1^2 + 3y_1^2) is a perfect square. From which follows that 2x12+3y122x_1^2 + 3y_1^2 is a perfect square.

However this contradicts the definition of the pair (x0,y0)(x_0, y_0) due to x1+y1<x0+y0x_1 + y_1 < x_0 + y_0 (the equality does not hold because at least one of two numbers is positive). Thus, in AA does not exist a perfect square.

b.
Firstly we will prove that the product of any three numbers from AA also belongs to AA. (*)

Indeed, consider numbers 2a2+3b22a^2 + 3b^2, 2c2+3d22c^2 + 3d^2, 2e2+3f22e^2 + 3f^2 from AA. We have
(2a2+3b2)(2c2+3d2)(2e2+3f2)=((2ac3bd)2+6(ad+bc)2)(2e2+3f2). (2a^2 + 3b^2)(2c^2 + 3d^2)(2e^2 + 3f^2) = ((2ac - 3bd)^2 + 6(ad + bc)^2)(2e^2 + 3f^2).
Putting m=2ac3bdm = 2ac - 3bd, n=ad+bcn = ad + bc, we have
(m2+6n2)(2e2+3f2)=2(me+3nf)2+3(mf2ne)2A. (m^2 + 6n^2)(2e^2 + 3f^2) = 2(me + 3nf)^2 + 3(mf - 2ne)^2 \in A.

Next, we will prove the statement of the problem by induction.
- For n=1,3n = 1, 3, from (*) the statement is true.
- Assume that the statement is true for n=2k13n = 2k-1 \ge 3, i.e., the product of any 2k12k-1 numbers from AA also belongs to AA.

Consider any 2k+12k+1 numbers from AA. Choose from them 2k12k-1 numbers. Then, by induction hypothesis, the product of these numbers belongs to AA. Then this product together with two remaining numbers forms a triple of numbers from AA. By (*) their product belongs to AA, which means the product of any 2k+12k+1 numbers from AA belongs to AA. Thus, the statement holds for n=2k+1n = 2k+1.

By induction principle, we have the required statement.

Now, apply result of part a for the product, we have done.

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.