5
$\begingroup$

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$

$\endgroup$

4 Answers 4

Reset to default
7
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ So before I can understand your answer, I have to learn Euler Fermat theorem and Chinese remainder theorem. Is this problem high school level? $\endgroup$
    – Aditya Dev
    Feb 7, 2016 at 12:28
  • $\begingroup$ @AdityaDev These are theorems that are often learned in Mathematical Olympiad training, but not in high school. $\endgroup$
    – wythagoras
    Feb 7, 2016 at 12:33
  • $\begingroup$ Can you recommend a book for learning number theory? $\endgroup$
    – Aditya Dev
    Feb 7, 2016 at 16:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aritra Das
    Feb 8, 2016 at 18:10
  • 2
    $\begingroup$ @AritraDas Question was from Aits open test. None of them are in JEE syllabus. Fiitjee paper setters have gone mad. $\endgroup$
    – Aditya Dev
    Feb 9, 2016 at 1:02
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

HINT:

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

$\endgroup$
5
  • 4
    $\begingroup$ How did you get that? $\endgroup$
    – Aditya Dev
    Feb 7, 2016 at 11:16
  • $\begingroup$ @AdityaDev: Start --> Calc --> Enter --> View --> Scientific --> $45$ --> $x^y$ --> $17$ --> Mod --> $204$ --> $=$. $\endgroup$
    – barak manos
    Feb 7, 2016 at 11:20
  • 3
    $\begingroup$ Calculators are not allowed $\endgroup$
    – Aditya Dev
    Feb 7, 2016 at 11:20
  • $\begingroup$ @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. $\endgroup$
    – barak manos
    Feb 7, 2016 at 11:22
  • 1
    $\begingroup$ I am sorry to be asking this question, But what does 45 (mod 204) or in general a (mod b) mean? $\endgroup$
    – Win Vineeth
    Feb 7, 2016 at 11:23
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .