Maths Olympiad Prep

Library / /9 of 13

Number theory Difficulty 6.4 National olympiad Prove it Bulgaria

We will call a natural number Yambolian if it can be represented in the form a2+6ab+b2a^2 + 6ab + b^2, where aa and bb are (not necessarily different) natural numbers. The number 36202436^{2024} is written as the sum of kk number of (not necessarily distinct) Yambol numbers. What is the smallest possible value of kk?
(Miroslav Marinov)

Solution

We will first show that k=1k = 1 is not possible, i.e. a2+6ab+b2=2404834048a^2 + 6ab + b^2 = 2^{4048} \cdot 3^{4048} has no solution in natural numbers. If such a,ba, b exist, then a2+b2a^2 + b^2 is divisible by 33 and therefore aa and bb are divisible by 33. Writing a=3a1a = 3a_1, b=3b1b = 3b_1 and dividing by 323^2, we get a12+6a1b1+b12=2404834046a_1^2 + 6a_1b_1 + b_1^2 = 2^{4048} \cdot 3^{4046}; repeating this argument another 20232023 times, we arrive at an equation of the form
u2+6νυ+υ2=24048 u^2 + 6\nu\upsilon + \upsilon^2 = 2^{4048}
where ν\nu and υ\upsilon are natural numbers.

If υ\upsilon is even, then ν\nu is even; writing ν=2u1\nu = 2u_1, υ=2v1\upsilon = 2v_1 and dividing by 44, we get u12+6u1v1+v12=24046u_1^2 + 6u_1v_1 + v_1^2 = 2^{4046}; repeating this several times, we arrive at an equation of the form
s2+6st+t2=22A, s^2 + 6st + t^2 = 2^{2A},
where s,t,As, t, A are natural numbers, tt is odd and Aq2A \geq q \geq 2 (since the left side is greater than or equal to 88). The latter is equivalent to (s+3t)28t2=22A(s+3t)^2 - 8t^2 = 2^{2A}. Now from modulo 88 we see that (s+3t)2(s+3t)^2 is divisible by 88, so s+3ts+3t is divisible by 44, i.e. (s+3t)2(s+3t)^2 is divisible by 1616. But then 8t28t^2 must be divisible by 1616, which is impossible for an odd tt, a contradiction. Therefore, k=1k=1 is not possible.

For an example with k=2k=2 let us first notice that
36=[12+611+12]+[32+631+12] 36 = [1^2 + 6 \cdot 1 \cdot 1 + 1^2] + [3^2 + 6 \cdot 3 \cdot 1 + 1^2]
and now multiplying by (62023)2(6^{2023})^2 leads to
362024=[(62023)2+66202362023+(62023)2]+[(362023)2+6(362023)62023+(62023)2] 36^{2024} = [(6^{2023})^2 + 6 \cdot 6^{2023} \cdot 6^{2023} + (6^{2023})^2] + [(3 \cdot 6^{2023})^2 + 6 \cdot (3 \cdot 6^{2023}) \cdot 6^{2023} + (6^{2023})^2]
i.e. 36202436^{2024} is the sum of the numbers a12+6a1b1+b12a_1^2 + 6a_1b_1 + b_1^2 and a22+6a2b2+b22a_2^2 + 6a_2b_2 + b_2^2, where a1=b1=b2=62023a_1 = b_1 = b_2 = 6^{2023} and a2=362023a_2 = 3 \cdot 6^{2023}.

\square

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 and solution reproduced as published; topic and difficulty added by this site.