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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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