Application of Fermat's little theorem to check divisibility

Question

Using Fermat's little theorem to prove:
$(i)19\mid 2^{2^{6k+2}}+3$, where $k=0,1,2.....$
$(ii)13\mid 2^{70}+3^{70}$
My Approach: I couldn't think of how to go with $(i)$ but i tried $(ii)$ to show $2^{70} \equiv 0\pmod {13}$ and $3^{70} \equiv 0\pmod {13}$.Since,
$$2^{12} \equiv 1 \pmod {13}\Rightarrow (2^{12})^5\equiv 1 \pmod {13}\Rightarrow2^{60} \equiv 1 \pmod {13}$$Again, $$2^4 \equiv 3 \pmod {13}\Rightarrow2^8.2^2 \equiv 10\pmod {13}$$Using both result:
$2^{70} \equiv 10\pmod {13}$
I failed again to show that. Any hints or solution will be appreciated.
Thanks in advance.

Answer 1

$n|a + b$ does not mean that $n|a$ and $n|b$. It means that if $a \equiv k \mod n$ then $b \equiv -k \mod n$.

So if $2^{70}\equiv 10 \mod 13$ (which it is) then $13|2^{70} + 3^{70}$ if $3^{70} \equiv -10 \mod 13$.

Does $3^{70}\equiv -10 \mod 13$?

Well If $0 < a < 13$ then $a^{12} \equiv 1 \mod 13$ and $a^{60} = (a^{12})^5\equiv 1 \mod 13$ so $a^{70} \equiv a^{10}\mod 13$.

And $2^{10} \equiv 10 \mod 13$.

And $3^3 \equiv 27 \equiv 1 \mod 13$ so $3^9 \equiv 1^3 \mod 13$ and $3^{10} \equiv 3 \equiv -10 \mod 13$.

So $2^{70} + 3^{70}\equiv 2^{10} + 3^{10} \equiv 10 + (-10)\equiv 0 \mod 13$.

i) is a lot harder but the idea is that as $2^{18} \equiv 1 \mod 19$ then if $2^{6k + 2}\equiv m \mod 18$ then $2^{2^{6k+2}}\equiv 2^m \mod 19$.

$2^{6k+2} = 64^k*4 = (7*9 + 1)^k*4$. Note $(7*9 + 1)^k$ will be $1$ more than a multiple of $9$. So $(7*9 + 1)^k*4$ will be $4$ more than a multiple of $4*9 = 2*18$. So $2^{6k+2} \equiv 4 \mod 18$.

And $2^{2^{6k + 2}}\equiv 2^4 \equiv 16 \mod 19$.

So $2^{2^{6k+2}}+3 \equiv 16 + 3 \equiv 0 \mod 19$.

Answer 2

We have $$2^{6k+1}\equiv 8^{2k}\cdot 2\equiv 2\pmod{9} $$ from which $$2^{6k+2}\equiv 4\pmod {18} $$ hence by Fermat's little theorem $$2^{2^{6k+2}}\equiv 2^4\equiv -3\pmod {19} $$

For the second $2^4\equiv 3\pmod {13} $ and $2^{12}\equiv 1\pmod {13}$ by Fermat little theoren hence $$2^{70}+3^{70}\equiv 2^{70}+2^{280}\equiv 2^{10}+2^{4}\equiv 9\cdot 4+3\equiv 0\pmod {13} $$

Answer 3

In (mod 13): $ 3^{70} = 9^{35} = (-4)^{35} = -(4^{35}) = -(2^{70}) $

So that: $ 2^{70} + 3^{70} = 0 (mod 13) $

The main idea is: $ 3^2 = (-1)2^2 $ (mod 13)

For all odd n: $ 13 $ $|$ $2^{2n} + 3^{2n} $