Remainder when ${45^{17}}^{17}$ is divided by 204

Question

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

I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$.

$204=2^2\cdot 3\cdot 17$

Answer 1

Hint: By the Euler-Fermat theorem we know $45^{\varphi(4)} = 45^{2} \equiv 1 \mod 4$.

By the Euler-Fermat theorem we also know $45^{\varphi(17)} = 45^{16} \equiv 1 \mod 17$

It is clear that $45 \equiv 0 \mod 3$ .

The Chinese Remainder Theorem gives us now $45^{16} \equiv 69 \mod 204$. Hence $45^{17} \equiv 69 \cdot 45 = 3105 \equiv 45 \mod 204$.

Answer 2

HINT:

$45^{17}\equiv45\pmod{204}$

Answer 3

Hint:

$45\equiv1\pmod4\implies45^n\equiv1$

$45\equiv0\pmod3\implies45^m\equiv0$

$45\equiv11\pmod{17}$

and $17\equiv1\pmod{16}$ and $17^n\equiv1$

$\implies11^{17^{17}}\equiv11\pmod{17}$

Now apply CRT

Answer 4

As $(45,204)=3$

let us start with $45^{17^{17}-1}\pmod{\dfrac{204}3}$

Using Carmichael function, $\lambda(204)=16$ and $17\equiv1\pmod{16}\implies17^{17}\equiv1$

$\implies45^{17^{17}-1}\equiv1\pmod{68}$

More generally, $a^{17^n-1}\equiv1\pmod{68}$ if $(a,68)=1$ and $n$ is a positive integer

Now, $45^{17^{17}-1}\cdot45\equiv1\cdot45\pmod{68\cdot45}$

Now using the fact: $204\mid68\cdot45,$

$$45^{17^{17}}\equiv45\pmod{204}$$