0

Can someone please verify (or falisfy) the following proof of the statement in the title.

Proof. Consider $$19\vert 2^{2^{6k+2}}+3.$$ $19$ divides this sum if and only if $$16\vert 2^{2^{6k+2}}$$ since $2^{2^{6k+2}}\equiv 16~mod~19$ and $3\equiv 3~mod~19$ implies that $$2^{2^{6k+2}}+3\equiv 16+3\equiv 19\equiv 0~mod~19\Leftrightarrow 19\vert 2^{2^{6k+2}}+3.$$ Thus, we need only show that $$16\vert 2^{2^{6k+2}}.$$

Consider $2^{2^{6k+2}}$. $$2^{2^{6k+2}}=2^{4^{3k+1}}=2^{4^{3k}\cdot 4^{1}}=(2^{4})^{4^{3k}}=16^{4^{3k}}$$ and since $16$ is divisible by $16$ (...), then $$16\vert 16^{4^{3k}}$$ for every $k=0,1,2,3,\cdots$.

Victor Galeano
  • 559
  • A simpler proof is that $19$ divides the sum iff $1$ divides $2^{2^{6k + 2}} - 15$, which is then obvious. – WhatsUp Dec 01 '19 at 19:57

3 Answers3

0

Your proof is incorrect. The error is made in

$$2^{2^{6k+2}}\equiv 16 \pmod {19} \Leftarrow 16 \mid 2^{2^{6k+2}}$$

The statement is true.

Hint: Show that $2^{6k+2} \equiv 4 \pmod{18}$.
Hence by Fermat's Little theorem, $ 2^{ 2^{6k+2}} \equiv 2^4 \equiv 16 \pmod{19}$ as desired.

Calvin Lin
  • 68,864
  • Ok. I dont know if I see what's incorrect. Could you expand on the error that I made? – Victor Galeano Dec 01 '19 at 20:44
  • @VictorGaleano Please explain why $ 16 \mid k \Rightarrow $k \equiv 16 \pmod{19}$. E.g. what if $ k = 32$ or $48$? – Calvin Lin Dec 01 '19 at 22:40
  • Okay. I think I see your point. I think the part about $19\vert 2^{2^{6k+2}}+3\Leftrightarrow 16\vert 2^{2^{6k+2}}$ is due to some confusion on my part. But is the folowing implication still false: If $2^{2^{6k+2}}\equiv 16\pmod 19$ and $3\equiv 3\pmod 19$, then $2^{2^{6k+2}}+3\equiv 16+3\equiv 19\equiv 0\pmod 19$. Meaning $19\vert 2^{2^{6k+2}}+3$?

    (I dont why but \pmod does not seem to work properly, as you can see in the text, so sorry for that)

     – Victor Galeano Dec 02 '19 at 08:21
  • The "following implication" is correct. $(a + b) \pmod{p}$ is equal to $(a \pmod{p} + b \pmod {p}) \pmod {p}$. That is why after showing that 2^2^6k+2 $ \equiv 16 \pmod{19}$, we can conclude that the problem is true. – Calvin Lin Dec 02 '19 at 16:09
0

When you say $19\mid2^{2^{6k+2}}+3$ if and only if $16\mid2^{2^{6k+2}}$, you seem to be thinking that for any number $n$, $n\equiv16$ mod $19$ if and only if $16\mid n$. That is false in either direction, as the counterexamples $n=32$ and $n=35$ show.

A correct proof involves showing (by induction) that $2^{2^{6k+2}}\equiv16$ mod $19$ for all $k\ge0$. The base case is easy enough: $2^{2^2}=2^4=16$. For the induction step, if $2^{2^{6k+2}}\equiv16$ mod $19$, then, from $2^{6(k+1)+2}=2^{6k+2}\cdot2^6=2^{6k+2}\cdot64$, the law of exponents gives

$$2^{2^{6(k+1)+2}}=(2^{2^{6k+2}})^{64}\equiv16^{64}\mod19$$

after which, from Fermat's Little Theorem that $a^{18}\equiv1$ mod $19$ if $19\not\mid a$, we have

$$16^{64}=(16^{18})^3\cdot16^{10}\equiv16^{10}=16\cdot16^9=16\cdot4^{18}\equiv16\mod19$$

Barry Cipra
  • 79,832
  • Note that he doesn't need "if and only if". He just needs "if" (which is still incorrect). – Calvin Lin Dec 01 '19 at 22:42
  • @CalvinLin, true. I was just citing what the OP said, in order to point out what I took to be the error in his thinking. (The logical statement "$19\mid 2^{2^{6k+2}}+3$ if and only if $16\mid 2^{2^{6k+2}}$" itself happens to be true for all $k\ge0$, but only because both sides of the "if and only if" happen to be true for all $k\ge0$.) – Barry Cipra Dec 01 '19 at 23:29
0

Here is a second attempt of proving the statement using induction. It is rather messy, but hopefully correct this time around. Note that this is actually just a messier version of @Barry Cipra proposed proof (hopefully).

Proof. $$19\vert 2^{2^{6k+2}}+3\Leftrightarrow 2^{2^{6k+2}}\equiv 16~~(\text{mod}~~ 19).$$ $(i)$ For the base case we show that the congruence holds for $k=0$. $$2^{2^{6\cdot 0+2}}\equiv 2^{4}\equiv 16~~(\text{mod}~~ 19),$$ so the base case holds.

$(ii)$ For the induction step suppose $ 2^{2^{6k+2}}\equiv 16~~(\text{mod}~~ 19)$ holds true for $k=m$. That is $$ 2^{2^{6m+2}}\equiv 16~~(\text{mod}~~ 19).$$

$(iii)$ Now we show that the statement in $(ii)$ holds true for $k=m+1$. That is $$ 2^{2^{6(m+1)+2}}\equiv 16~~(\text{mod}~~ 19).$$

Consider $2^{2^{6(m+1)+2}}$. Using the induction step $(ii)$ we get that $$2^{2^{6(m+1)+2}}\equiv 2^{2^{6m+8}}\equiv 2^{2^{6m+2}\cdot 2^{6}}\equiv \left(2^{2^{6m+2}} \right)^{64}\equiv 16^{64}.$$ Moreover, when using Fermats little theorem we get that $$16^{64}\equiv (-3)^{64}\equiv (-3)^{18\cdot 3+10}\equiv \left((-3)^{3}\right)^{18}\cdot (-3)^{10}\equiv 1\cdot (-3)^{10}\equiv \cdots \equiv -250\equiv 16~~(\text{mod}~~ 19).$$ We have thus shown that the statement $$2^{2^{6(m+1)+2}}\equiv 16~~(\text{mod}~~ 19)$$ is true. Therefore we may conclude that $$2^{2^{6k+2}}\equiv 16~~(\text{mod}~~ 19)\Leftrightarrow 19\vert 2^{2^{6k+2}}+3$$ for every $k=0,1,2,\cdots$.

Victor Galeano
  • 559