Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction.
I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$.
Now assume it is true for $n$. Then for $n+1$, we have the expression
$$ 1 + 2^{(2^{n+1})} + 2^{(2^{n+2})}$$
which is equal to
$$1 + 2^{(2^n\cdot 2)} + 2^{(2^n \cdot 2^2)}$$
but I do not really see how it helps.
Any ideas?
On
Consider the polynomial $$f(x) = 1+x^{2^n} + \left(x^{2^{n}} \right)^2$$ We claim that $f(x) = (1+x+x^2)g(x)$, where $g(x)$ is also a polynomial for all $k \in \mathbb{Z}^+$. This is easy to prove, since $\omega = e^{2\pi i/3}$ and $\omega^2 = e^{4\pi i/3}$ are roots of $1+x+x^2$. We have $1+\omega^{2^n} + \left(\omega^{2^n}\right)^2 = 0$. Hence, $1+x+x^2$ divides $1+x^{2^n} + x^{2^{n+1}}$. Taking $x=2$, we obtain what you want.
On
Let's look at your sequence $\pmod 7$. $2^3 \equiv 1 \pmod 7$, therefore $2$ has order $3\pmod 7$. Since $2 \equiv -1 \pmod 3$, $\{2^n,2^{n+1}\} \equiv \{2,1\} \pmod 3$. Therefore $\{2^{2^n},2^{2^{n+1}}\} \equiv \{2,4\} \pmod 7$.
Your sequence is always $1+2+4 \equiv 0 \pmod 7$. It might look a little complicated at first, but the idea is that for $a^k \in \Bbb Z/n\Bbb Z$, k depends on the order of $a \pmod n$
On
Hint $\,\ \color{#c00}{w^3 \equiv 1}\,$ and $\,f(w) \equiv 1+w+w^2\,\Rightarrow\, f(w^2) \equiv 1+w^2+w\cdot\color{#c00}{w^3} \equiv f(w)$
On
As in Winther's post let $x_n=2^{2^n}$. Then the sequence is $I_n=1+x_n+x_n^2$, and $x_{n+1}=x_n^2$.
We suppose $I_n\equiv0\pmod 7 \implies x_n+x_n^2\equiv-1 \pmod 7$,
squaring both sides:
$x_n^2+2x_n^3+x_n^4\equiv1 \implies I_{n+1}=1+x_n^2+x_n^4\equiv 2(1-x_n^3)\equiv 0 \pmod 7$
since $x_n^3=2^{3\cdot2^n}\equiv1^{2^n}\equiv 1 \pmod 7$
Hint:
Let $I_n = x_n^2 + x_n + 1$ where $x_n$ satisfy $x_{n+1} = x_n^2$ with $x_0 = 2$. Then
$$I_{n+1} = x_{n}^4 + x_n^2 + 1 = (x_n^2-x_n+1)I_n$$
Proving that $7| I_n$ using induction on $n$ is now very simple.