+0  
 
0
113
1
avatar+130 

Find the remainder when 2^70 + 3^70 is divied by 13

 

 

Thank You!

 Mar 15, 2021
 #1
avatar+420 
0

First, use the addition rule of modular arithmetic: \((a+b) \text{mod }n = (a \text{ mod }n + b\text{ mod }n) \text{ mod }n\).

That means first you should calculate the individual modulus of each of the numbers a and b (which are 2^70 and 3^70) first.

To do that, use Fermat's little theorem, which is that, for 2 numbers a and n, if n is prime, and if a is not divisible by n, then \(a^{n-1}≡1 (\text {mod }n)\). 13 is prime, and 2 and 3 are not divisible by 13, so Fermat's little theorem can apply here.

Also, use the fact that for any number a, p, x, and n, \(a^p (\text{mod } n) = a^{px} (\text{mod }n)\), and the multiplication rule that \((a\cdot b) \text{mod }n = (a \text{ mod }n \cdot b\text{ mod }n) \text{ mod }n\)\(\). So first, to solve 2^70 mod 13, 

\(2^{12} ≡ 1(\text{mod }13)\\ 2^{60} ≡ 1(\text{mod }13)\\ 2^{60}\cdot2^{10} ≡ 1\cdot2^{10}≡2^{10}(\text{mod }13)\\ 1024(\text{mod }13) = 10\)

 Now, 3^70 mod 13 (in a very similar fashion)

\(3^{12} ≡ 1(\text{mod }13)\\ 3^{60} ≡ 1(\text{mod }13)\\ 3^{60}\cdot3^{10} ≡ 1\cdot3^{10}≡3^{10}(\text{mod }13)\\ 59049(\text{mod }13) = 3\)

Now, using the addition rule mentioned in the beginning,

 \((2^{70}+3^{70}) \text{mod }13 = (2^{70} \text{ mod }13 + 3^{70}\text{ mod }13) \text{ mod }13\\ =(10+3) \text{mod }13 = \boxed{0}\)\(\)

So the remainder of this is equal to zero.

 

It seems like you're asking a lot of questions about modular arithmetic, and I think a great place to learn more about it is at https://brilliant.org/number-theory/?subtopic=modular-arithmetic 

 Mar 15, 2021

16 Online Users