# Remainder when $20^{15} + 16^{18}$ is divided by 17

What is the reminder, when $20^{15} + 16^{18}$ is divided by 17. I'm asking the similar question because I have little confusions in MOD. If you use mod then please elaborate that for beginner. Thanks in advance.

-

The key thing to remember about the operation "mod" is that it behaves "well" with respect to product (hence powers), and of course addition. This means that if you can simplify your life a lot distributing the calculation into many steps and taking "mod" at each stage.

To compute $20^{15}$, you can first notice that $20 \pmod{17} = 3$. Then $20^{15} \pmod{17} = 3^{15} \pmod{17}$. The power $15$ is quite large, but you can for instance take: $3^3 \pmod{17} = 27 \pmod{17} = 10$, hence $3^{15} \pmod{17} = 10^5 \pmod{17} = 10 \cdot 100^2 \pmod{17} = 10 \cdot (-2)^2 \pmod{17} = 40 \pmod{17} = 6 \pmod{17}$.

The term $16^{18}$ is much easier: $16^{18} \pmod{17} = (-1)^{18} \pmod{17} = 1$.

Hence, the answer is $6 + 1 = 7$.

-
What will be the reminder when $5^{19}$ divided by 16. –  Complex Guy May 14 '13 at 22:11
Well, $5^{2} \equiv 25 \equiv 9$, hence $5^{4} \equiv 81 \equiv 1$. This is quite useful: $5^{19} \equiv (5^4)^4 \cdot 5^2 \cdot 5 \equiv 9 \cdot 5 \equiv 45 \equiv 13$. –  Feanor May 14 '13 at 22:14

Hints:

$$20=3\pmod{17}\;,\;\;16=-1\pmod{17}\implies$$

$$20^{15}+16^{18}=3^{15}+(-1)^{18}=(**)$$

But for any integer $\,a\;,\;\;(a,17)=1\,$ , we have that $\,a^{16}=1\,$ , so

$$(**)=3^{16}\cdot 3^{-1}+1=1\cdot 6+1=7\ldots$$

and so the claim is false: the remainder is $\,7\,$ .

-
Sorry, I didn't get this $$\,a\;,\;\;(a,17)=1\,$$ –  Complex Guy May 14 '13 at 21:52
Fermat's Little Theorem. Google it. –  DonAntonio May 14 '13 at 21:53
Minor detail: there was no claim. The title is misleading, but it did not say divisible. The first sentence of the post is clearer. +1. –  julien May 14 '13 at 21:56
Well, in the title there indeed was a claim. Alas, this is one example more of the "style" to write some higher education students adopt...Thanks. For me, "is divided" is just the same as "divisible by", BTW. –  DonAntonio May 14 '13 at 21:58
I was just saying that the title is a truncature of the first sentence of the post, and that the OP did not mean that anything was divisible by $17$. Not that it is a fascinating issue...just that your "the claim is false" isn't necessary. –  julien May 14 '13 at 22:09
show 1 more comment

consider this over $\mathbb{Z}/17\mathbb{Z}$. Addition and multiplication are well defined, so we can without harm say $20^{15} + 16^{18} \equiv 3^{15} + (-1)^{18}$ mod 17. You want to show what it is equivalent to mod 17. To do this you would just crunch it out using Fermats litle theorem and stuff like that.

-
When you use the modulo operator, multiplication is conserved, e.g: $$20 \equiv 3 \pmod {17}$$ $$40 \equiv 6 \pmod {17}$$ So that: $$40*20 \equiv 6*3 \pmod {17}\equiv 1 \pmod {17}$$
The same holds for powers (since this is just multiplication many times), so: $$20^{15} \equiv 3^{15} \pmod {17}$$ $$16^{18} \equiv (-1)^{18} \pmod {17}$$ Now use: $$3^{15} = (3^5)^3 \equiv (243)^{3} \equiv (5)^{3} \equiv 6 \pmod {17}$$ To see that the remainder is $7$.