И снова считаем в столбик!

Всем нам знакомы числа в других системах счисления. На уроках информатике в школе нам приходилось переводить числа из одной системы счисления в другую, складывать, вычитать, умножать… А вот на уроках алгебры мы изучали операцию возведения в степень и ее свойства. Тоже ничего сложного, не так ли? Однако эти темы встречаются и в олимпиадных задачах, причем не по отдельности, а вместе!

Нужно признать, что составители олимпиадных задач любят усложнять школьникам жизнь. Вот и в нашей задаче на сегодня мы столкнемся с числами в двух различных системах счисления, ни одна из которых не будет десятичной, да еще и возведением в четырехзначную степень! Впрочем, как говорится, лучше один раз увидеть: итак, нам с вами нужно найти последнюю цифру числа Х в шестнадцатеричной системе счисления:

Если вы считаете, что все, в общем-то, выглядит несложно: достаточно перевести все в десятичную систему счисления и посчитать на калькуляторе, то придется вас разочаровать – понадобится очень-очень мощный калькулятор. Получаемые значения будут слишком большими. 

Настоящие математики всегда найдут легкий путь! Обратите внимание на условие: нам нужна только последняя цифра, а значит, и при умножении можно следить только за последними цифрами. Однако есть нюанс: вычисления в таком случае придется проводить сразу в шестнадцатеричной системе счисления, ведь просто перевести в нее позже результат уже не получится.

Начнем с основания степени: обозначим его за у. Сейчас оно записано в восьмеричной системе счисления, и существует очень удобный алгоритм перевода восьмеричных чисел в шестнадцатеричные. Используем тот факт, что каждая цифра в восьмеричной записи числа отвечает трем разрядам его двоичной записи, а каждая цифра шестнадцатеричной записи – четырем. Получается, перевести у в шестнадцатеричную запись проще не через десятичную, а через двоичную запись: 

Напомним, что цифры больше 9 обозначаются в шестнадцатеричной записи заглавными латинскими буквами. Что ж, мы получили основание степени в нужной системе счисления. Попробуем возвести его в квадрат: да-да, доставайте карандаши и листочки, нам придется считать в столбик! Впрочем, нас интересует только последняя цифра, не так ли?

По всем правилам счета в столбик, ищем последнюю цифру:

Соответственно, в записи в столбик результат будет выглядеть так:

Продолжаем наши вычисления! Домножим на у еще раз – получим третью степень:

Здесь стоит заметить очень важную деталь: цифра F уже была последней, и, так как мы домножаем все время на одно и то же число, дальше последовательность последних цифр будет повторяться: в первой степени последней была F, во второй – 1, в третьей – F, значит, в четвертой будет опять 1, затем F в пятой, и т.д. Получается, последняя цифра для у в четной степени – 1, в нечетной – F. Осталось определить, с четной ли степенью мы имеем дело?

Вспомним условие: показатель степени в данной задаче равен 201416. Так как четным является основание степени счисления – 16, и последняя цифра числа – 4 – также четная, то все число также четное. Проверяем наши выводы выше – последней цифрой числа Х будет 1! Мы вышли на уровень олимпиадных задач – и, заметьте, никаких мощных вычислительных машин нам не понадобилось.