Maths Olympiad Prep

Library / /26 of 46

Number theory Difficulty 6.3 National olympiad Prove it Russia

A positive integer mm is chosen so that the sum of all the digits of 8m8^m (in its decimal representation) equals to 88. Determine if the last digit of 8m8^m can appear to be 66.

Solution

Первое решение. Предположим, что сумма цифр числа 8m8^m при некотором m>1m > 1 равна 88, и оно оканчивается на 66. Число 2m2^m не может оканчиваться на 0606 или на 2626, так как в этом случае оно не делится на 44. Следовательно, оно оканчивается на 1616 (иначе сумма цифр будет больше 88), и поэтому имеет десятичную запись 10000161000\ldots016. Тогда 8m=10k+168^m = 10^k + 16, то есть число 10k+1610^k + 16 -- степень двойки.

Но если k5k \ge 5, то 10k+16=24(2k45k+1)10^k + 16 = 2^4(2^{k-4} \cdot 5^k + 1), и в скобках получаем нечетный множитель, больший 11. Остается рассмотреть случаи k=2,k=3,k=4k = 2, k = 3, k = 4: 102+16=42910^2 + 16 = 4 \cdot 29; 103+16=812710^3 + 16 = 8 \cdot 127; 104+16=3231310^4 + 16 = 32 \cdot 313. Таким образом, 10k+1610^k + 16 не является степенью восьмерки ни при каком натуральном kk, что и требовалось доказать.

Второе решение. Предположим противное, и пусть 8m8^m оканчивается на 66 и имеет сумму цифр, равную 88. Заметим, что 818^1 оканчивается на 88, 828^2 оканчивается на 44, 838^3 оканчивается на 22, 848^4 оканчивается на 66, 858^5 оканчивается на 88. Далее последняя цифра степени восьмерки повторяется с периодом 44, поскольку последняя цифра числа 8m8^m определяется однозначно последней цифрой числа 8m18^{m-1}. Таким образом, 8m8^m оканчивается на 66 тогда и только тогда, когда mm делится на 44.

Сумма цифр числа имеет тот же остаток при делении на 33, что и само число, поэтому 8m8^m должно иметь остаток 22 при делении на 33. Заметим, что 818^1 имеет остаток 22 при делении на 33, 828^2 имеет остаток 11 при делении на 33, 838^3 имеет остаток 22 при делении на 33, и далее остатки степени восьмерки повторяются с периодом 22. Таким образом, 8m8^m имеет остаток 22 при делении на 33 тогда и только тогда, когда mm нечетно. Это противоречит тому, что mm должно делиться на 44.

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.