# Application of Fermat's little theorem to check divisibility

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.

• You can't show something that isn't true. And $2^{70}$ is a power of $2$. So it can't be divisible by $13$. It can only be divisible by a power of $2$ Same thing with $3^{70}$. – fleablood Sep 27 '18 at 7:42

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

• Thanks a lot @fleablood. I got the idea :) – emonHR Sep 27 '18 at 10:32

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

• Thanks a lot @Fabio Lucchini :) – emonHR Sep 27 '18 at 10:35

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

• Thanks a lot @Angel Moreno :) i got it – emonHR Sep 27 '18 at 10:36
• s'okay and very easy. BUt it doesn't use Fermat's Little Theorem. Which admittedly one doesn't need... but it was asked for. – fleablood Sep 27 '18 at 14:58