На доске написано число 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.