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

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$

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$.

• So before I can understand your answer, I have to learn Euler Fermat theorem and Chinese remainder theorem. Is this problem high school level? Feb 7, 2016 at 12:28
• @AdityaDev These are theorems that are often learned in Mathematical Olympiad training, but not in high school. Feb 7, 2016 at 12:33
• Can you recommend a book for learning number theory? Feb 7, 2016 at 16:59
• @AdityaDev Fiitjee AIiTS right? You have to learn some basic things like congruence modulo, Fermat's theorem, Euler's Phi function and related theorems, Chinese Remainder Theorem and Hensel's lemma. This should be more than enough. Don't go in for any book now, it'll be unnecessary. Use online resources. Feb 8, 2016 at 18:10
• @AritraDas Question was from Aits open test. None of them are in JEE syllabus. Fiitjee paper setters have gone mad. Feb 9, 2016 at 1:02

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

HINT:

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

• How did you get that? Feb 7, 2016 at 11:16
• @AdityaDev: Start --> Calc --> Enter --> View --> Scientific --> $45$ --> $x^y$ --> $17$ --> Mod --> $204$ --> $=$. Feb 7, 2016 at 11:20
• Calculators are not allowed Feb 7, 2016 at 11:20
• @AdityaDev: IMO, they are not allowed when they (present time calculators) cannot be used. For $45^{17^{17}}$ they cannot be used, but for $45^{17}$ they can. So it is essentially the same as using a calculator for $45^3$, which you most likely wouldn't do by hand. You can easily do $45^{17}\bmod{204}$ by hand, if you really want to. I tried to save you some time by telling you the answer to that. Feb 7, 2016 at 11:22
• I am sorry to be asking this question, But what does 45 (mod 204) or in general a (mod b) mean? Feb 7, 2016 at 11:23

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}$$