+130 Find the remainder when 2^70 + 3^70 is divied by 13
Thank You!
+506 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
