Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 8 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
Sorry, I didn't get this $$ \,a\;,\;\;(a,17)=1\,$$ –  Complex Guy May 14 '13 at 21:52
1  
Fermat's Little Theorem. Google it. –  DonAntonio May 14 '13 at 21:53
1  
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. –  1015 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
1  
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. –  1015 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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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