Let $n{}$ be a positive integer. What is the smallest sum of digits that $5^n + 6^n + 2022^n$ can take?
Problem
Source: BMO Shortlist 2022, N1
Tags: number theory, AZE BMO TST, AZE EGMO TST
13.05.2023 21:10
When $n=1$, the sum of the digits is $2+0+3+3=8$. When $n=2$, its digits add up to $4+0+8+8+5+4+5>8$. If $n\geq3$, then $5^n+6^n+2022^n\equiv1\pmod4$ and $5^n+6^n+2022^n\equiv5^n\pmod9$. Then, if there exists $n$ such that the sum is smaller, then the last digit must be either $1$, $3$, or $5$. Taking mod $5$ gives that the last digit cannot be $1$, so the last digit is either $3$ or $5$, and the last two digits are either $13$, $33$, or $05$. If the last two digits are $05$ then $5\mid1+2^n$ so $n\equiv2\pmod4$. Therefore, $5^n+6^n+2022^n\equiv1\pmod3$, so the sum must equal $7$, which implies $n\equiv2\pmod6$. Taking mod $8$ gives $1$, so the last three digits are $105$. Taking mod $7$ gives $4+1+1=6$, so $2022^n+5^n+6^n=10^k+105$ where $k\equiv3\pmod6$. Taking modulo $13$ gives $5^n+6^n+7^n\equiv0\pmod{13}$, which is not true when $n\equiv2\pmod6$. If the last digit is $3$, then $n\equiv1\pmod4$, so taking mod $8$ gives that the last two digits are $13$. Taking modulo $3$ gives that the sum must be $5$. Therefore, $n\equiv1\pmod6$, and we have $2022^n+5^n+6^n=10^k+13$. Taking modulo $7$ gives $k\equiv4\pmod6$. Then, taking mod $13$ gives $5^n+6^n+7^n\equiv3\pmod{13}$, which is not true when $n\equiv1\pmod6$. Therefore, the smallest possible sum of the digits of $5^n+6^n+2022^n$ is $\boxed8$.
14.05.2023 09:35
We will prove that the minimal such sum of digits if $8$, achieved for example if $n=1$. Let $A=5^n+6^n+2022^n$, and assume there existed an $n>1$ such that $A$ has a smaller sum of digits. Let us consider the following 4 cases. Case 1: $n \equiv 0 \pmod 4$. Then, $5^n+6^n+2022^n \equiv 2^n+1 \equiv 2 \pmod 5,$ and since $A$ is odd, we conclude that it ends with a $7$. Obviously $A \neq 7$, and so $A$ has sum of digits at leadt $8$, a contradiction. Case 2: $n \equiv 1 \pmod 4$. Then, $5^n+6^n+2022^n \equiv 2^n+1 \equiv 3 \pmod 5,$ and since $A$ is odd, we conclude that it ends with a $3$. Now, we consider the following 3 subcases. Subcase 2.1: $n \equiv 0 \pmod 3$. Then, $n \equiv 9 \pmod {12}$ and so $5^n+6^n+2022^n \equiv 5^n \equiv 8 \pmod 9$, and so the sum of digits of $A$ is at least $8$, a contradiction. Subcase 2.2: $n \equiv 1 \pmod 3$. Then, $n \equiv 1 \pmod {12}$ and so $5^n+6^n+2022^n \equiv 5^n \equiv 5 \pmod 9$, and so the sum of digits of $A$ can only be equal to $5$. Since $A \equiv 1 \pmod 4,$ we conclude that its last two digits are $1$ and $3$. Therefore, $A$ is of the form $10 \ldots 0131=10^k+13$, for some positive integer $k$. However, this is a contradiction, since working $\pmod {16}$ we see that (note that $n>4$ since $n \equiv 1 \pmod {12}$ and $n>1$) $A=5^n+6^n+2022^n \equiv 5^n \equiv 5 \pmod {16},$ which contradicts $A=10^k+13 \equiv 13 \pmod {16}$. Subcase 2.3: $n \equiv 2 \pmod 3$. Then, $n \equiv 5 \pmod {12}$ and so $5^n+6^n+2022^n \equiv 2 \pmod 9,$ and so the sum of digits of $A$ can only be equal to $2$, which is a contradiction since the last digit is equal to $3$. Case 3: $n \equiv 2 \pmod 4$. Then, $5^n+6^n+2022^n \equiv 2^n+1 \equiv 0 \pmod 5,$ and since $A$ is odd, we conclude that it ends with a $5$. Now, we consider the following 3 subcases. Subcase 3.1: $n \equiv 0 \pmod 3$. Then, $n \equiv 6 \pmod {12}$ and so $5^n+6^n+2022^n \equiv 5^n \equiv 1 \pmod 9$, and so the sum of digits of $A$ can only be equal to $1$, which is a contradiction since it ends with a $5$. Subcase 3.2: $n \equiv 1 \pmod 3$. Then, $n \equiv 10 \pmod {12}$ and so $5^n+6^n+2022^n \equiv 5^n \equiv 4 \pmod 9$, and so the sum of digits of $A$ can only be equal to $4$, which is a contradiction since it ends with a $4$. Subcase 3.3: $n \equiv 2 \pmod 3$. Then, $n \equiv 2 \pmod 12$ and so $5^n+6^n+2022^n \equiv 5^n \equiv 7 \pmod 9$, and so the sum of digits of $A$ can only be equal to $7$. If $n=2$ we may easily check that the sum of digits of $A$ is not $7$, so assume that $n>2$. Since $A \equiv 5^n+6^n+2022^n \equiv 5^n \equiv 1 \pmod 8,$ we conclude that its last three digits can only equal $1,0$ and $5$. Hence, $A$ is of the form $10 \ldots 0105=10^k+105$, for some positive integer $k$. Now, notice that from Fermat's Little Theorem $5^n+6^n+2022^n \equiv 5^2+6^2+2022^2 \equiv 6 \pmod {13},$ and so $10^k+105 \equiv 6 \pmod {13},$ that is $10^k \equiv 5 \pmod {13},$ which is easily seen to not have any solutions by considering $k \pmod 6$. Case 4: $n \equiv 3 \pmod 4$. Then, $5^n+6^n+2022^n \equiv 2^n+1 \equiv 4 \pmod 5,$ and since $A$ is odd, we conclude that it ends with a $9$, and so we have a contradiction. To sum up, having considered all possible cases, we conclude that the minimal sum of digits of $A$ is $8$.
14.05.2023 11:42
The answer is $8$, achieved when $n=1$ as $5^{n} + 6^{n} + 2022^{n} = 2033$ in that case. A quick computation shows that $5^2+6^2+2022^2 = 4088545$ which has sum of digits larger than $8$, so we can work with $n\geq 3$ from hereon. FTSOC assume that $S(5^{n} + 6^{n} + 2022^{n})<8$ for some $n$. Denote $f_{n} = 5^{n} + 6^{n} + 2022^{n}$ and bash: $f_{n} \equiv 1\pmod 4$ $f_{n} \equiv 1+2^{n} \pmod{10}$. More specifically, the last digit of $f_{n}$ is odd and larger than $1$ as $5\nmid 2^{n}$. $f_{n} \equiv 5,7,8,4,2,1 \pmod 9$ As $S(f_{n})<8$ by our assumption, this implies that $S(f_{n})\in\{1,2,4,5,7\}$. The cases $S(f_{n}) = 1$ or $2$ fail immediately due to the second bullet and if $S(f_{n}) = 4$, then by the second bullet, we must have $f_{n} = 10^{k} + 3$ for some $k\in\mathbb{N}$. However, the first bullet forces $k = 1$ which is impossible as $f_{n} > f_{1} = 2033$. If $S(f_{n}) = 5$, then the last digit of $f_{n}$ must be $3$ and the first bullet forces the second last digit to be $1$. Hence $f_{n} = 10^{k} + 13$ for some $k\geq 2$. If $2022^{n} \equiv (-3)^{n} \equiv t\pmod{25}$, then $6^{n} \equiv t^2 \pmod{25}$ and \[t^2+t\equiv f_{n} \equiv 13\pmod{25}\Longrightarrow (2t+1)^2\equiv 3\pmod{25}\]However, $3$ is not a quadratic residues modulo $5$, contradiction. The only remaining option is $S(f_{n}) = 7$. In that case $n\equiv 2 \pmod 6$, so $n$ is even and therefore we can write \[f_{n} = 25^{n/2}+36^{n/2}+2022^{n}\equiv 1+4^{n/2} \equiv 5,7 \pmod{10}\]implying that the last digit can't be $3$, so the last digit must be $5$. On the other hand, though, we also have that $f_{n}\equiv 1\pmod 8$ because $n$ is even. This forces the last three digits (bearing in mind that the sum of digits is $7$) to either be $105$ or $025$. The second case requires $f_{n} = 25 < f_{1}$, impossible, and the first one is impossible modulo $11$. Indeed, $10^{k}+105\equiv \pm 1+6\pmod{11}$ and \[f_{n} \equiv 25^{n/2}+36^{n/2}+(2022^2)^{n/2} \equiv 2\cdot 3^{n}+4^{n} \pmod{11}\]A direct check shows that $2\cdot 3^{n}+4^{n}\equiv 0,1,3,8,10\pmod{11}$, so $f_{n}\not\equiv 5,7 \equiv 10^{k}+105\pmod{11}$, contradiction.
22.07.2023 12:34
DottedCaculator wrote: When $n=1$, the sum of the digits is $2+0+3+3=8$. When $n=2$, its digits add up to $4+0+8+8+5+4+5>8$. If $n\geq3$, then $5^n+6^n+2022^n\equiv1\pmod4$ and $5^n+6^n+2022^n\equiv5^n\pmod9$. Then, if there exists $n$ such that the sum is smaller, then the last digit must be either $1$, $3$, or $5$. Taking mod $5$ gives that the last digit cannot be $1$, so the last digit is either $3$ or $5$, and the last two digits are either $13$, $33$, or $05$. If the last two digits are $05$ then $5\mid1+2^n$ so $n\equiv2\pmod4$. Therefore, $5^n+6^n+2022^n\equiv1\pmod3$, so the sum must equal $7$, which implies $n\equiv2\pmod6$. Taking mod $8$ gives $1$, so the last three digits are $105$. Taking mod $7$ gives $4+1+1=6$, so $2022^n+5^n+6^n=10^k+105$ where $k\equiv3\pmod6$. Taking modulo $13$ gives $5^n+6^n+7^n\equiv0\pmod{13}$, which is not true when $n\equiv2\pmod6$. If the last digit is $3$, then $n\equiv1\pmod4$, so taking mod $8$ gives that the last two digits are $13$. Taking modulo $3$ gives that the sum must be $5$. Therefore, $n\equiv1\pmod6$, and we have $2022^n+5^n+6^n=10^k+13$. Taking modulo $7$ gives $k\equiv4\pmod6$. Then, taking mod $13$ gives $5^n+6^n+7^n\equiv3\pmod{13}$, which is not true when $n\equiv1\pmod6$. Therefore, the smallest possible sum of the digits of $5^n+6^n+2022^n$ is $\boxed8$. How did you get the last two digits ?
22.07.2023 14:11
By mod 4 and using the fact that the sum of the digits is less than $8$.
11.09.2023 19:03
DottedCaculator wrote: . Then, if there exists $n$ such that the sum is smaller, then the last digit must be either $1$, $3$, or $5$. Can you please show how you got that?
11.09.2023 20:11
the number is odd and a digit >=7 is impossible if the number is more than 7 and the sum of the digits is <=7
25.09.2023 10:58
Sol:- $n=1$ gives value $2033$ whose sum of digits is $8$. This gives bound of atmost $8$.It suffices to show that sum of digits $\notin \{1,2,3,4,5,6,7\}$. Let $S(r)$ denote the sum of digits of $r$.Let $n \geq 2$ since we have dealt with case $n=1$. $S(5^n+6^n+2022^n) \equiv 5^n+6^n+2022^n \equiv 5^n \not \equiv 0 \pmod {3}$. This eliminates values $3,6$. $5^n+6^n+2022^n \equiv 5+6+2^n \equiv 1+2^n \pmod {10} \implies$ unit digit is atleast $3$. This eliminates values $1,2$. It just suffices to eliminate values $4,5,7$. Case 1 $S(5^n+6^n+2022^n)=4$ Proof Since unit digit is atleast $3$ our no. will be of form $10..03$. $3 \equiv 10..03 \equiv 5^n+6^n+2022^n \equiv 5^n \equiv 1 \pmod 4$. Contradiction. So $4$ is eliminated. Case 2 $S(5^n+6^n+2022^n)=5$ Proof Since unit digit is atleast $3$ and odd so unit digit will be $3$. $5^n+6^n+2022^n \equiv 1 \pmod 4 \implies 5^n+6^n+2022^n \equiv 13 \pmod {100} \implies $ our no. is of form $10..0013$. $3 \equiv 5^n+6^n+2022^n \equiv 5+6+2^n \equiv 1+2^n \pmod {10} \implies n=4k+1$. $13 \equiv 10..0013 \equiv 5^{4k+1}+6^{4k+1}+2022^{4k+1} \equiv 5 \pmod {16}$. Contradiction. So $5$ is eliminated. Case 3 $S(5^n+6^n+2022^n)=7$ Proof Since unit digit is atleast $3$ and odd and $5^n+6^n+2022^n \not \equiv 0 \pmod 5 \implies $ unit digit is $3$. $3 \equiv 5^n+6^n+2022^n \equiv 5+6+2^n \equiv 1+2^n \pmod {10} \implies n=4k+1$. $7 \equiv S(5^n+6^n+2022^n) \equiv 5^n+6^n+2022^n \equiv 5^n \pmod 9 \implies n=6r+2$. $n$ is both odd and even. Contradiction. So we are done .
11.01.2025 21:06
$\boxed{ANSWER:s(5^n+6^n+2022^n)=8,n=1}$ Let $A=5^n+6^n+2022^n$ For $n=1\implies A=2033\implies s(A)=8$ now let's assume $n>1$ claim 1:$s(A)\equiv 3,5\pmod{10}$ no proof claim 2:$n\equiv 1,2\pmod{4}$ also no proof case 1:$s(A)=4$ $s(A)=4\implies 10^t+3=A,$ $n>1\implies A\equiv 1\pmod{4}$ and $LHS\equiv 3\pmod{4}$ contradiction case 2:$s(A)=5$ case 2.1:$A=2\cdot 10^t+3$ which fails $\pmod{4}$ case 2.2:$A=10^t+10^r+3$ if $r>1$ fails $\pmod{4}$ If $r=1\implies A=10\dots 013$ in this case $n\equiv 1\pmod{4}\implies A\equiv 5\pmod{16}$ and $RHS\equiv 13\pmod{16}$ contradiction case 3:$s(A)=6$ $s(A)\equiv A\nmid 0\pmod{3}$ contradiction case 4:$s(A)=7$ $n\equiv 1\pmod{4}\implies A\equiv 3\pmod{10}$ and every case fails with $\pmod{16}$(so tired at this point) Btw my $50th$ post