Is this a valid proof technique regarding the divisibility of numbers?

Question

Claim: All numbers of this sequence are relatively prime to one another: $$2^1 + 1, 2^2 + 1, 2^4 + 1, \ldots, 2^{2^n} + 1$$

So, I decided to include $2^0 + 1$. That way:

Base case:

$$2^0 + 1 = 2$$

Because $2$ is even and the rest are odd, every number after it is coprime to it.

Now, before I get to the inductive step, I also noticed this about any arbitrary number of the sequence:

$$ 2^{2^k} + 1 = 2^{2\cdot2^{k-1}} + 1 = 4^{2^{k-1}} + 1 = (2\cdot2)^{2^{k-1}} +1 = 2^{2^{k-1}}2^{2^{k-1}}+1$$

So, then I decided to say: if I assume every number can be written in this form, and assume my claim holds for $1, \ldots, k$ then if this property holds for $k+1$, the claim is true (but I am not sure you can do this though, can someone confirm, deny, or help me further solidify this idea of mine?):

$$ 2^{2^{k+1}} + 1 = 2^{2\cdot2^k} + 1 = 4^{2^k} + 1 = (2\cdot2)^{2^k} +1 = 2^{2^k}2^{2^k}+1$$

To further elaborate: I am saying that since all $P(k)$ (where $P$ is my original proposition) follow a similar form, if the next number follows that form, the proposition holds true. At the same time, I haven't done induction quite this way before (it is usually easier, and more concrete, so to speak. No "forms" just explicit equations). Hopefully what I am saying makes sense. If you need further clarification please ask.

Answer 1

Solution without induction:

Take any $a,b\le n$, assume $a<b$. You need prove that $\gcd(2^{2^a}+1,2^{2^b}+1)=1.$

Let $d=\gcd(2^{2^a}+1,2^{2^b}+1)$. Then $d|2^{2^a}+1$ and $d|2^{2^b}+1$. From $d|2^{2^a}+1$ you'll get $d|2^{2^{a+1}}-1$ since $2^{2^{a+1}}-1=(2^{2^a}+1)(2^{2^a}-1)$. Continuing this process, you'll arrive at $d|2^{2^{a+(b-a)}}-1=2^{2^{b}}-1$. It follows that $d|2^{2^{b}}-1$. Since $d|2^{2^b}+1$ then $d|2$. However, $d$ must be $1$ because it is an odd number.

Answer 2

Suppose $p/2^{2^k}+1$ and $p/2^{2^l}+1$ ($p$ divides).

WLOG $k>l$.

Then $ p/2^{2^l} (2^{2^{k-l}}-1)$. Now we know $p \neq 2$ so it divides the parenthesis term.

Factorize the parenthesis term. $p/(2^{2^{k-l-1}}-1)(2^{2^{k-l-1}}+1)$. If $p$ divides the left parenthesis, repeat. If not, it divides the right parenthesis, so start this whole process again with $k=max(k-l-1, l)$,$l=min(k-l-1, l)$. By infinite descent, $p=1$, so the two initial numbers are coprime.

Also, where you thinking of strong/complete induction? The way you could leverage that in this situation is to set $k=n+1$ (where we have proved it up to $n$), then use the induction hypothesis to avoid infinite descent and simplify a little. More complicated if you ask me. http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction