3
$\begingroup$

$1717^{1717} \mod 100$

Since $\phi(100) = 40$ , we can transform this into:

$17^{37}101^{37} \mod 100 = 17^{37} \mod 100$

How do I proceed further?

$\endgroup$
2
  • 1
    $\begingroup$ You can split the exponent, like $17^{37}=(17^2)^{18}\cdot 17$ for example. $\endgroup$
    – Sil
    Jul 6, 2018 at 7:58
  • 2
    $\begingroup$ You can look at a similar problem: math.stackexchange.com/questions/2315617/… $\endgroup$
    – Matti P.
    Jul 6, 2018 at 8:01

5 Answers 5

4
$\begingroup$

Since $17^3\equiv13\pmod{100}$, $17^{37}\pmod{100}$ is the inverse of $13$ in $\mathbb{Z}_{100}^*$, which turns out to be $77$.

$\endgroup$
2
$\begingroup$

Use the Chinese remainder theorem: $$\mathbf Z/100\mathbf Z\simeq\mathbf Z/4\mathbf Z\times\mathbf Z/25\mathbf Z$$

$17\equiv 1\mod 4$, so $17^{37}\equiv \color{red}1\mod 4$. On the other hand, $\varphi(25)=20$, so $\;17^{37}\equiv 17^{-3}=(17^{-1})^3\mod 25$. As a Bézout's relation between $17$ and $25$ is $$3\cdot 17-2\cdot25=1,$$ we have $17^{-1}\equiv 3\mod 25$ and we finally get $$17^{37}\equiv 3^3\equiv \color{red}2\mod 25.$$ Now use the inverse isomorphism: from the Bézout's relation between $4$ and $25$: $\;25-6\cdot4=1$, we deduce $$17^{37}\equiv \color{red}1\cdot 25-\color{red}2\cdot6\cdot 4=-23\equiv 77\mod 100.$$

$\endgroup$
1
$\begingroup$

Like What are the last two digits of $77^{17}$?,

using Carmichael Function, $\lambda(100)=20\implies**17^{**17}\equiv17^{17}\pmod{100}$

Now $17^2=290-1, 17^{17}=17(290-1)^8$

Again, $\displaystyle(290-1)^8=(1-290)^8\equiv1-\binom81290\pmod{100}\equiv1-90\cdot8\equiv-19$

Now $-19\cdot17=-323\equiv77\pmod{100}$

See also:

Find the last two digits of $ 7^{81} ?$

The last two digits of $13^{1010}$.

Find the last two digits of $3^{45}$

what are the last two digits of $2016^{2017}$?

$\endgroup$
1
1
$\begingroup$

Note that $$17^{37}\equiv(17^3)^{12}\cdot17\equiv(13^{3})^4\cdot17\equiv(-3)^4\cdot17\equiv1377\equiv77\pmod{100}.$$

or

$$17^{37}\equiv(17^4)^9\cdot17\equiv21^5\cdot21^4\cdot17\equiv1\cdot81\cdot17\equiv77\pmod{100}.$$

$\endgroup$
1
$\begingroup$

$1717 \equiv 17$ (mod 100), since $1700 \equiv 0$ (mod 100).

Therefore, $1717^{1717} \equiv 17^{1717}$ (mod 100).

Now you have to compute the powers $17^n$ (mod 100). This gives what is sometimes called a cycle.

$17\equiv 17$ (mod 100)

$17^2\equiv 289 \equiv 89$ (mod 100)

$17^3 \equiv 4913 \equiv 13$, (mod 100)

$17^4 \equiv 83521 \equiv 21$ (mod 100)

and so on. You will finally obtain that $17^{21}\equiv 17$ (mod 100) again. Since $1717\equiv 17$ (mod 20), the last two digits of $1717^{1717}$ (mod 100) are the same as the last two digits of $17^{17}$ (mod 100) which are $77$.

$\endgroup$

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