Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory intermediate

Problem

What is the remainder when is divided by ?
Solution
We begin by computing the remainder of some small powers of . As and , then leaves a remainder of after division by , and leaves the remainder that does after division by , namely . The sequence of powers thus repeat modulo again. In particular, the remainder that the powers of leave after division by is periodic with period . Then, leaves the same remainder as does after division by , which is .
Final answer
49