+0

# Pls Help

0
496
1
+130

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

Thank You!

Mar 15, 2021

#1
+505
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.