1
$\begingroup$

Question 1: What are the last two digits of $17^{198}$?

My Attempt: The pdf hinted to reduce it via mod $100$. So my work is as follows:

Since $17^2\equiv289\equiv-11\mod100$, we have$$17^{198}\equiv (-11)^{99}\equiv-11^{99}\mod100$$ However, I'm not sure how to compute $-11^{99}$ without too much of a hassle.

Questions:

  1. How do you complete this problem?
  2. Why use mod $100$? Why not mod $50$ or some other number?
$\endgroup$
  • $\begingroup$ You want to use $-1$ rather than $-11$. But working in mod 10 will only give you the last digit. A number mod 100 gives the last 2 digits. $\endgroup$ – Michael Jan 27 '17 at 15:02
  • 2
    $\begingroup$ The hint was to work mod 100 but you used mod 10 $\endgroup$ – RGS Jan 27 '17 at 15:04
  • $\begingroup$ @RSerrao That mod $10$ thing was just a stupid mistake made by me... It should be fixed now... $\endgroup$ – Crescendo Jan 27 '17 at 15:06
  • $\begingroup$ Try doing mod $100$ of a few arbitrary numbers with different number of digits. $\endgroup$ – kingW3 Jan 27 '17 at 15:10
1
$\begingroup$

Reducing an integer mod. $100$ consists exactly in taking its last two digits !

Indeed, if we consider $n\in\mathbb{N}$ and divide it by $100$, we get something like $n=100q+r$ with $0\le r<100$.

Now, for your example, you mean mod. 100 and not mod. 10 ...

$$17^{198}\equiv-11^{99}\,\,(mod.\,100)$$

But $11^{99}=(11^3)^{33}=(1331)^{33}\equiv31^{33}=(31^3)^{11}=29791^{11}\equiv91^{11}$

and $91^2=8281$, so $91^2\equiv81$. Then $91^{10}=(91^2)^5\equiv81^5=3486784401\equiv1$

Finally $11^{99}\equiv91\,\,(mod.\,100)$ and so $$\boxed{17^{198}\equiv9\,\,(mod.\,100)}$$

$\endgroup$
3
$\begingroup$

An alternative approach, exploiting the Chinese remainder theorem and the fact that $2$ is a generator in $\mathbb{Z}/(25\mathbb{Z})^*$:

$$ 17^{198}\equiv (-8)^{198} \equiv 2^{3\cdot 198} \equiv 2^{14} \equiv 16\cdot 1024\equiv -16\equiv 9\pmod{25} $$ $$ 17^{198}\equiv 1\pmod{4} $$ together imply $17^{198}\equiv \color{red}{9}\pmod{100}$.

$\endgroup$
1
$\begingroup$

Hint: First note that $-11 \equiv -1 \pmod {10}$. There's only two possible integer powers of $-1$.

For your second question, we use $\pmod{100}$ because the last two digits of any integer is exactly the remainder when divided by $100$.

$\endgroup$
  • $\begingroup$ So does that mean that mod $1000$ gives you the last three digits, mod $10000$ gives you the last four digits, and so on? $\endgroup$ – Crescendo Jan 27 '17 at 15:06
  • $\begingroup$ @Crescendo yepper $\endgroup$ – The Count Jan 27 '17 at 15:09
  • $\begingroup$ Okay, cool. And also, what about a number of the form $a^{b^c}\mod n$? How would you reduce? Is it the same as $a^b$ where you reduce $a$ and then simplify? Or is there a quicker way? $\endgroup$ – Crescendo Jan 27 '17 at 15:18
1
$\begingroup$

For the first question, you may want to refer to this Wikipedia page where you are presented with some different methods. My favorite one and the most pratical is under the title "Right-to-left binary method".

As for the second question, what is the remainder of $56$ when divided by $100$? And what about $543$? And $642058311$? Note that $56 = 0\cdot100 + 56, 543 = 5\cdot100 + 43, 642058311 = 6420583\cdot100 + 11$. If you take those equalities $\mod 100$, everything but the last two digits of each number is reduced to $0$.

$\endgroup$
1
$\begingroup$

Note $\, 17^{\large 2}\!= -1\!+\!10k\,\Rightarrow\, \color{#c00}{17^{\large 20}}\equiv \overbrace{(-1\!+\!10k)^{\large 10}\!\equiv (-1)^{\large 10}}^{\large\rm Binomial\ Theorem}\!\!\equiv \color{#c00}{\bf 1}\pmod{\!100}$

thus we conclude $\ 17^{\large 198}\equiv\dfrac{(\color{#c00}{17^{\large 20}})^{\large 10}}{17^{\large 2}}\equiv\dfrac{\color{#c00}{\bf 1}}{-11}\equiv \dfrac{9}{-99}\equiv 9\pmod{\!100}$

$\endgroup$
-1
$\begingroup$

Let $G=(\mathbb{Z}/100\mathbb{Z})^{*}$. Since $|G|$=40 and $17\in G$, we have $$ 17^{198} = 17^{40\cdot 5}\cdot 17^{-2}=1\cdot 17^{-2} \ mod\ 100$$ To find $17^{-2}\ mod\ 100$ we note first that $17\cdot 3 = 1 \ mod \ 10$. Then, we only have to solve $$ 17\cdot (10x+3) = 1 \ mod\ 100$$ for $x\in[0,9]\cap\mathbb{Z}$, in order to find the inverse. Doing some computations, we find $$ 70x=50 \ mod\ 100 $$ $x=5$ solves the equation and one can verify directly that $17\cdot 53=1 \ mod\ 100$. We deduce $17^{198}=53^2 = 9\ mod\ 100$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.