2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – fleablood Sep 27 '18 at 7:42
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot @fleablood. I got the idea :) $\endgroup$ – emonhossain Sep 27 '18 at 10:32
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot @Fabio Lucchini :) $\endgroup$ – emonhossain Sep 27 '18 at 10:35
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot @Angel Moreno :) i got it $\endgroup$ – emonhossain Sep 27 '18 at 10:36
  • $\begingroup$ 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. $\endgroup$ – fleablood Sep 27 '18 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.