Finding remainder when ${{45}^{17}}^{17}$ is divided by $204$

Question

Find the remainder when ${{45}^{17}}^{17}$ is divided by $204$

This question came in an examination yesterday and I couldn't solve it. The answer that was given in the solutions booklet stated this:

${{45}^{17}}^{17}$=$17k+11$= $3{k}^{'} +0=4{k}^{"}+1$ .Hence ,the remainder is 45.

I don't really understand anything stated here.

In general,is there anything I can learn for solving such types of problems based on remainders and divisibility?I would really like to learn new ways of solving such problems.

I tried searching the internet, but everything there is either too simple(elementary level) or too complex. I just learned something called the Euler's theorem, but the 2 numbers here are not coprime. :/ EDIT:Is their any way to solve this apart from sing modular arithmetic? Thank You.

Answer 1

$204 = 2^2 \times 3 \times 17$. We'll do it separately mod $4$, mod $3$, and mod $17$, and then put the results together using the Chinese remainder theorem.

1. $45 \equiv 1 \mod 4$, so $45^x \equiv 1 \mod 4$ for any $x$.
2. $45 \equiv 0 \mod 3$, so $45^x \equiv 0 \mod 3$ for any $x \ge 1$.
3. $45 \equiv 11 \mod 17$. Now by Fermat's theorem $11^{16} \equiv 1 \mod 17$. Thus if $17^{17} \equiv b \mod 16$, i.e. $17^{17} = b + 16 x$ for some integer $x$, that will mean $11^{17^{17}} = 11^{b + 16 x} \equiv 11^b \mod 17$. In this case, $17 \equiv 1 \mod 16$, so $b = 1$. Thus $45^{17^{17}} \equiv 11 \mod 17$.

Now to put it together: the answer $y$ is congruent to $1 \mod 4$, $0 \mod 3$ and $11 \mod 17$. Start with the $17$: $y = 11 + 17 s$ for some $s$. Thus $1 \equiv y \equiv 3 + s \mod 4$, so $s \equiv 1-3 \equiv 2 \mod 4$. Writing $s = 2 + 4 t$, we have $y = 11 + 34 + 68 t = 45 + 68 t$. Thus $0 \equiv y \equiv 0 + 2 t \mod 3$, so we can take $t = 0$. We conclude that $$ 45^{17^{17}} \equiv 45 \mod 204$$