Find all positive integers $n$ for which there exists an integer multiple of $2022$ such that the sum of the squares of its digits is equal to $n$.
Problem
Source: JBMO Shortlist 2022
Tags: number theory, Sum of Squares, Digits, Junior, Balkan, shortlist
27.06.2023 02:00
Notice that $2022 \cdot 5 = 10110$. The sum of the square of its digits is $3$. I claim that all $n=3k$ work. This is easy to see. Let $2022 \cdot 5 = a_0$. Construct recursively $a_{x+1} =1001a_x$ with $a_0 = 2022 \cdot 5$. It is easy to see that $a_{x}$ has sum of digits $3(x+1)$ for all $x \ge 0$ so we're done in this case. Now, I claim all $n = 3k+2$ work when $k \ge 1$. Notice that $2022 \cdot 55 = 111210$. Now analogously to above we can construct all $n = 3k+2$ to work. $n=2$ can't work because then $2022x = 10^a + 10^b$ with $a \neq b$ which contradicts $\pmod{3}$. $n=5$ can work though. We need $2022x = 10^a + 10^b + 10^c + 10^d + 10^e$ or $2022x = 10^a + 2 \cdot 10^b$. The first one can't work because $\pmod{3}$, the second one can work though. The only condition we need is that there exists a $y$ such that $2 \cdot 10^y \equiv -1 \pmod{337}$ or a $z$ such that $10^z \equiv -2 \pmod{337}$ (both cases follow when $a>b$ or $a<b$). Such a $y$ and $z$ will only exist if $y + z \equiv 0 \pmod{ord_{337}(10)}$ as $10^{y+z} \equiv 1 \pmod{337}$. Using wolframalpha I find that $y=200$ and $z=136$ works, so this proves that $n=5$ can be achieved. Now, we just need the $n=3k+1$ numbers. The smallest number of this form that has a chance to work, is $n=10$. This is because: $n=1$ doesn't work mod $3$, $n=4$ doesn't work mod $3$ ($2 \cdot 10^a$ or $10^a+10^b+10^c+10^d$), $n=7$ doesn't work mod $3$($2 \cdot 10^a + 10^b+10^c+10^d$ or $10^a + ... + 10^g$). If $n=10$ were to work, we need it to be of the form $2022x = 10^a + 10^b + 2 \cdot 10^c + 2 \cdot 10^d$. Using previous result that $2 \cdot 10^y \equiv -1 \pmod{337}$ has $y \equiv 200$ as a solution, we choose $d = 200$, $c = 200 + 336 (= \phi(337)$, and $a = 336$ with $b = 672$. This results in $10^a + 10^b + 2 \cdot 10^c + 2 \cdot 10^d \equiv 1 + 1 + (-1) + (-1) \equiv 0 \pmod{337}$. This proves that there exists an $x$ such that $2022x = 10^a + 10^b + 2 \cdot 10^c + 2 \cdot 10^d$ as $\frac{10^{672} + 10^{336} + 2 \cdot 10^{536} + 2 \cdot^{200}}{2022}$ is an integer. We can use this number to construct any $n \ge 10$ of the form $3k+1$ with $a_n = 1001 a_{n-1}$ with $a_0 = 2022x$ with the above $x$ and we're done. We conclude that all $n \neq 1,2,4,7$ work.
27.06.2023 02:04
See that $ord_{337}10=336$ and let $x,y$ be such that $10^x=-1(mod337)$ and $10^y=-2(mod337) $ then we use the numbers in the form: $10^{x+a_i}+10^{a_i}$ (style 1) and $10^{y+b_i}+10^{b_i}$ (style 2) with $a_i,b_i$ such that all the expoment to be different. Consider now $3z$ numbers of style 1 we get that if $6|n$ then $n$ is good. Consider $3z$ numbers of style 1 and one more of style 2 we get that if $n\equiv 5(mod6)$ then $n$ is good Consider $3z$ numbers of style 1 and two more of style 2 we get that if $n\equiv 10\equiv 4(mod6)$ then $n$ is good with $n\geqslant 10$ Consider $3z$ numbers of style 1 and 3 more of style 2 we get that if $n\equiv 15\equiv 3(mod6)$ then $n$ is good with $n\geqslant 15$ Consider $3z$ numbers of style 1 and 4 more of style 2 we get that if $n\equiv 20\equiv 2(mod6)$ then $n$ is good with $n\geqslant 20$ Consider $3z$ numbers of style 1 and 5 more of style 2 we get that if $n\equiv 25\equiv 1(mod6)$ then $n$ is good with $n\geqslant 25$ It left to consider if $4,3,9,2,8,14,1,7,13,19$ are good or not for $n=4$ is bad from $mod3$ $n=3,9$ works well just make a number on the form $\sum_{i=1}^{n}10^i$ which is multiple of $337$ $n=2$ is bad from $mod3$ $n=8,14$ is good make a number on the form $2*10^j\sum_{i=1}^{n-1}10^i$ which is multiple of $337$ $n=1,7$ is bad from $mod3$ $n=13,19$ are good make a number on the form $2*10^k+2*10^j\sum_{i=1}^{n-2}10^i$ which is multiple of $337$ So all $n\neq 1,2,4,7$ works
29.06.2023 19:06
This was our proposal, and here is the solution that accompanied it: Solution. We will show that $n\ne 1, 2, 4, 7$. For any other positive integer $n$, there exists an integer multiple of $2022$ such that the sum of the squares of its digits is equal to $n$. We first note that the prime factorization of $2022$ is $2022=2\cdot 3\cdot 337$. We have $n\ne1$. It is $1=1^2$. The sum of the squares of the digits of a positive integer $m$ is equal to $1$ if and only if $m$ is equal to a power of $10$. Then the sum of the digits of $m$ equals $1$, which means that $m$ is not a multiple of $3$. Hence $m$ cannot be a multiple of $2022$ either. * $n\ne 2$. It is $2=1^2+1^2$. The sum of the squares of the digits of a positive integer $m$ is equal to $2$ if and only if $m$ is equal to the sum of two distinct powers of $10$. Then the sum of the digits of $m$ equals $2$, which means that $m$ is not a multiple of $3$. Hence $m$ cannot be a multiple of $2022$ either. * $n=3$. This value is feasible since, for example, it is $5\cdot 2022=10110$. * $n\ne 4$. It is $4=1^2+1^2+1^2+1^2$ and $4=2^2$. The sum of the squares of the digits of a positive integer $m$ is equal to $4$ if and only if $m$ is equal to either the sum of four distinct powers of $10$ or twice a power of $10$. Then the sum of the digits of $m$ equals $4$ or $2$, respectively, which means that $m$ is not a multiple of $3$. Hence $m$ cannot be a multiple of $2022$ either. * $n=5$. This is the most interesting case. The only ways to express $5$ as a sum of the squares of positive integers (that are smaller than $10$) are $5=1^2+1^2+1^2+1^2+1^2$ and $5=2^2+1^2$. The sum of the squares of the digits of a positive integer $m$ is equal to $5$ if and only if $m$ is equal to either the sum of five distinct powers of $10$ or the sum of twice a power of $10$ with a distinct power of $10$. In the first case, as above, we cannot obtain a multiple of $3$. So, we examine the second case. For instance, we wish to obtain an integer multiple of $2022$ which is of the form $200\dots 01..0$ or of the form $100\dots 02..0$. Let's consider the latter one. Every integer of the form $100\dots 02..0$ is even and also a multiple of $3$. Thus it suffices to obtain a positive integer $k$ such that $10^k\equiv -2 \pmod{337}$. We find that $10^{8}\equiv -32\equiv-2^5 \pmod{337}$ and we observe that \[ 2^{21}=\left(2^{10}\right)^2\cdot 2 \equiv 13^2\cdot 2\equiv 1 \pmod{337}. \]We may proceed in two ways: (1st way) It is $10^{136}\equiv -2\pmod{337}$. Indeed, we have \[ 10^{136}=\left(10^8\right)^{17}\equiv \left(-2^{5}\right)^{17}\equiv -2^{85}\equiv -\left(2^{21}\right)^4\cdot 2\equiv -2\pmod{337}. \](2nd way) We have \begin{align}\notag 10^{48}=\left(10^8\right)^6&\equiv \left(-2^{5}\right)^6\equiv 2^{30}\equiv 2^9\equiv 175\pmod{337},\\\notag 10^{112}=\left(10^8\right)^{14}&\equiv \left(-2^5\right)^{14}\equiv 2^{70}\equiv 2^7 \equiv 128 \pmod{337}, \text{ and}\\\notag 10^{168}=\left(10^8\right)^{21}&\equiv \left(-2^5\right)^{21}\equiv -\left(2^{21}\right)^5\equiv -1 \pmod{337}.\notag \end{align} Since $\varphi (337)=336=2^4\cdot 3\cdot 7$, $10^{\varphi (337)/7}=10^{48}\not\equiv 1 \pmod{337}$, $10^{\varphi (337)/3}=10^{112}\not\equiv 1 \pmod{337}$ and $10^{\varphi (337)/2}=10^{168}\not\equiv 1 \pmod{337}$, it follows that $10$ is a primitive root of $337$. Hence there exists a positive integer $k$ such that $10^k\equiv -2 \pmod{337}$. Note that $10^{136}+2$ (or $10^k+2$ in our 2nd way) is a multiple of $2$, $3$, and $337$, and so, it is a multiple of $2022$. The sum of the squares of its digits is equal to $1^2+2^2=5$, as desired. * $n=6$. This value is feasible since, for example, we could start with $10110$ and append one more copy of it. It is ${\color{red}{10110}}{\color{blue}{10110}}=500005\cdot 2022$. * $n\ne 7$. The only ways to express $7$ as a sum of the squares of positive integers (that are smaller than $10$) are $7=1^2+1^2+1^2+1^2+1^2+1^2+1^2$ and $7=2^2+1^2+1^2+1^2$. The sum of the squares of the digits of a positive integer $m$ is equal to $7$ if and only if $m$ is equal to either the sum of seven distinct powers of $10$ or the sum of twice a power of $10$ with three distinct powers of $10$. Then the sum of the digits of $m$ equals $7$ or $5$, respectively, which means that $m$ is not a multiple of $3$. Hence $m$ cannot be a multiple of $2022$ either. * $n\geq 8$. We will imitate what we did with $n=6$. Every positive integer $n\geq 8$ can be written in the form $3x+5y$ for some non-negative integer $x$, and $y=0$ or $1$ or $2$, depending on whether $n\equiv 0\pmod{3}$ or $n\equiv 2\pmod{3}$ or $n\equiv 1\pmod{3}$, respectively. If we write the number $10110$ $x$ times next to each other, followed by $y$ times the number $10^{136}+2=1000...02$, then we obtain an integer multiple of $2002$ such that the sum of the squares of its digits equals $3x+5y=n$, as desired. The proof is complete. Comments: (a) For the case where $n=5$, one could show that there exists a positive integer $\mu$ such that $10^\mu\equiv -5\pmod{337}$. Indeed, it is \[ 10^{201}=\left(10^8\right)^{25}\cdot 10 \equiv \left(-2^{5}\right)^{25}\cdot 10 \equiv -2^{125}\cdot 10\equiv -\left(2^{21}\right)^6\cdot 5\equiv -5\pmod{337}. \]Otherwise, since $10$ is a primitive root of $337$, there exists a positive integer $\mu$ such that $10^\mu\equiv -5 \pmod{337}$. Since the sum of the digits of $10^\mu+5$ is $6$, it follows that $\dfrac{10^\mu+5}{3}$ is an integer multiple of $ 337$. Hence \[ 2\left(10^\mu+5\right)=6\frac{10^\mu+5}{3} \]is a multiple of $2022$, which is of the form $2000...010$. Moreover, the sum of the squares of its digits is equal to $2^2+1^2=5$. (b) The smallest multiple of $2022$ such that the sum of the squares of its digits is equal to $6$ is equal to $50005\cdot 2022=101110110$.