Maths Olympiad Prep

Library / /2 of 41

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Slovenia

Let kk be a positive integer greater than 11. Prove: for every non-negative integer mm there exist kk positive integers n1,n2,,nkn_1, n_2, \dots, n_k, such that
n12+n22++nk2=5m+k. n_1^2 + n_2^2 + \dots + n_k^2 = 5^{m+k}.

Solutions — 2

Solution 1

Let k=2k = 2. If n1=5ln_1 = 5^l and n2=25ln_2 = 2 \cdot 5^l, then n12+n22=52l+1n_1^2 + n_2^2 = 5^{2l+1}. If n1=35ln_1 = 3 \cdot 5^l and n2=45ln_2 = 4 \cdot 5^l, then n12+n22=52l+2n_1^2 + n_2^2 = 5^{2l+2}. In both cases, ll is an arbitrary non-negative integer. Hence, the equation n12+n22=5ln_1^2 + n_2^2 = 5^l has solutions for all positive integers tt.

Next, we consider the case k=3k = 3. Let n1=3a1n_1 = 3a_1, n2=4a1n_2 = 4a_1 and n3=52a2n_3 = 5^2 a_2. Then n12+n22+n32=52(a12+a22)n_1^2 + n_2^2 + n_3^2 = 5^2(a_1^2 + a_2^2). For every non-negative integer mm there exists a solution to the equation a12+a22=51+ma_1^2 + a_2^2 = 5^{1+m}. so we have shown that the equation n12+n22+n32=53+mn_1^2 + n_2^2 + n_3^2 = 5^{3+m} has solutions for all non-negative integers mm.

For k3k \ge 3 we proceed by induction. Assume that the equation a12+a22++al2=5l+ma_1^2 + a_2^2 + \dots + a_l^2 = 5^{l+m} has positive integer solutions for all non-negative integers mm and for all positive integers ll such that 2lk2 \le l \le k. We wish to show that in this case the equation n12+n22++nk2+nk+12=5k+1+mn_1^2 + n_2^2 + \dots + n_k^2 + n_{k+1}^2 = 5^{k+1+m} also has positive integer solutions for all non-negative integers mm.

Since 5k+1+m=5k+m+45k+m5^{k+1+m} = 5^{k+m} + 4 \cdot 5^{k+m} and k>k12k > k-1 \ge 2, the induction hypothesis implies that for all non-negative integers ii there exist positive integers a1,a2,,ak1a_1, a_2, \dots, a_{k-1}, such that
a12+a22++ak12=5k1+i a_1^2 + a_2^2 + \dots + a_{k-1}^2 = 5^{k-1+i}
In particular, this is true for i=m+1i = m + 1. so there exist positive integers a1,a2,,ak1a_1, a_2, \dots, a_{k-1}, such that
a12+a22++ak12=5k+m a_1^2 + a_2^2 + \dots + a_{k-1}^2 = 5^{k+m}

Solution 2

Since 32+42=523^2 + 4^2 = 5^2 and 52+102=535^2 + 10^2 = 5^3, such numbers n1n_1 and n2n_2 exist for k=2k=2, m=0m=0 and for k=2k=2, m=1m=1. Using induction on mm we show that the solutions exist for any mm. Let m3m \ge 3. Assume that there exist positive integers a1,a2a_1, a_2, such that a12+a22=5ma_1^2 + a_2^2 = 5^m. Then
5m+2=525m=52(a12+a22)=(5a1)2+(5a2)2. 5^{m+2} = 5^2 \cdot 5^m = 5^2(a_1^2 + a_2^2) = (5a_1)^2 + (5a_2)^2.
so 5m+25^{m+2} is the sum of the squares of two positive integers. We have considered the cases m=0m=0 and m=1m=1 separately, so by induction the claim for k=2k=2 follows for all non-negative integers mm.

Since 53=32+42+1025^3 = 3^2 + 4^2 + 10^2 and 54=92+122+2025^4 = 9^2 + 12^2 + 20^2, we can use a similar argument for k=3k=3 and show that the equation n12+n22+n32=53+mn_1^2 + n_2^2 + n_3^2 = 5^{3+m} also has positive integer solutions for all non-negative integers mm.

Let k3k \ge 3. We will use induction on kk. Assume that for all non-negative integers mm there exist positive integers a1,a2,,aka_1, a_2, \dots, a_k, such that
a12+a22++ak2=5k+m a_1^2 + a_2^2 + \dots + a_k^2 = 5^{k+m}
and, since k12k-1 \ge 2, positive integers b1,b2,,bk1b_1, b_2, \dots, b_{k-1}, such that
b12+b22++bk12=5k1+m b_1^2 + b_2^2 + \dots + b_{k-1}^2 = 5^{k-1+m}
If k+mk+m is even, then 5k+m+1=5k+m+45k+m=a12+a22++ak2+45k+m=a12+a22++ak2+(25k+m2)25^{k+m+1} = 5^{k+m} + 4 \cdot 5^{k+m} = a_1^2 + a_2^2 + \dots + a_k^2 + 4 \cdot 5^{k+m} = a_1^2 + a_2^2 + \dots + a_k^2 + (2 \cdot 5^{\frac{k+m}{2}})^2. So 5k+m+15^{k+m+1} is a sum of k+1k+1 squares of positive integers.

Let k+mk+m be odd. Since k+m30k+m-3 \ge 0, we can find two positive integers c1,c2c_1, c_2, such that c12+c22=52+(k+m3)c_1^2 + c_2^2 = 5^{2+(k+m-3)}. Then
5k+m+1=525k+m1=(9+16)5k+m1=95k1+m+1652+k+m3=9(b12+b22++bk12)+16(c12+c22)=(3b1)2+(3b2)2++(3bk1)2+(4c1)2+(4c2)2. \begin{aligned} 5^{k+m+1} &= 5^2 \cdot 5^{k+m-1} = (9+16)5^{k+m-1} \\ &= 9 \cdot 5^{k-1+m} + 16 \cdot 5^{2+k+m-3} \\ &= 9(b_1^2 + b_2^2 + \dots + b_{k-1}^2) + 16(c_1^2 + c_2^2) \\ &= (3b_1)^2 + (3b_2)^2 + \dots + (3b_{k-1})^2 + (4c_1)^2 + (4c_2)^2. \end{aligned}

Since mm was an arbitrary non-negative integer, this concludes the induction.

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.