На дощечке написано число 8 в 99 ступени. У него рассчитывается

Определим функцию D(n), где n - естественное чисел и

D(n) = суммы цифр числа n.

Лемма:

Остатки от деления D(n) на 9 и n на 9 одинаковы, т.е. D(n) и n сравнимы по модулю 9.

Подтверждение:

Рассмотрим, к примеру, случай, когда n - трехзначное число. Для любого n подтверждение будет подобным. Достаточно увидеть, что 10^k = 9 * p + 1, где p = 1...1 (k единиц).

Если n = abc, n = 100 * a + 10 * b + c = 99 * a + 9 * b + (a + b + c) =

=9 * (11 * a + b) + (a + b + c) =9 * (11 * a + b) + D(n),

т.е. n = 9 * (11 * a + b) + D(n), что и требовалось доказать.

Явно, что применяя функцию D(n) поочередно к ее результату, мы получим:

d = D(D(D(.....D(n)))) остатки от дробленья d на 9 и n на 9 равны.

Осмотрим степени числа 8 и вычислим поочередно значения функции D:

8^1 := 8

8^2 := 64 := 6 + 4 := 10 := 1 + 0 := 1

8^3 := 512 := 5 + 1 + 2 := 8

8^4 := 4096 := 4 + 0 + 9 + 6 := 19 := 1 + 9 := 10 := 1 + 0 := 1.

Заметим, что при нечетных степенях получаем 8, а при четных 1.

Можно представить, что при четных степенях 8^(2*k) последовательное применение функции D дает 1, а при нечетных ступенях 8^(2*k + 1) последовательное применение функции D дает 8.

Докажем это свойство по индукции.

Пусть утверждение верно для 8^2k. Значит по лемме 8^2k и 1 дают схожи остатки при делении на 9. Значит 8^2k можно представить:

8^2k = 9 * m + 1. Умножим обе доли на 8. 8^(2k + 1) = 9 * 8 * m + 8. Остаток 8.

Также пусть утверждение правильно для 8^(2k + 1). Значит по лемме 8^(2k + 1) и 8 дают схожи остатки при разделении на 9. Означает 8^(2k + 1) можно представить:

8^(2k + 1) = 9 * m + 8. Умножим обе части на 8. 8^(2(k + 1)) = 9 * 8 * m + 64 =

=9 * (8 * m + 7)  + 1. Остаток 1.

Как следует, в нашем случае 8^99 число 99 - нечетное и разыскиваемое число равно 8.

Ответ: 8.