Prove that $2^{n+2}$ is a divisor of the number $k^{2^{n}}-1$

Question

Question :

If n is a natural number and k is an odd number

$k\in \mathbb{Z}$ then show that $2^{n+2}$ is a divisor of

the number $k^{2^{n}}-1$

My try as following :

I'm think use induction :

$n=1$ then $2^{3}=8$ since $k$ is odd so : $k^{2}=1\mod 8$ We find : $2^{3}$ divisor of $k^{2}-1$ (correct )

Now for $n+1$ how I prove $2^{n+3}\mid (k^{2^{n+1}}-1)$

And if can prove it without induction ??

Answer 1

$$\frac{k^{2^{n+1}}-1}{2^{n+3}}=\frac{k^{2^{n}}-1}{2^{n+2}}\times \frac{k^{2^n}+1}{2}$$ The first fraction on RHS is an integer by induction hypothesis and second one is integer because $k$ is odd, hence LHS is integer and you are done!

To prove without induction Observe that $$k^{2^n}-1=(k^2-1)\prod_{r=1}^{n-1}(k^{2^r}+1)$$ $$\Longrightarrow \frac{k^{2^n}-1}{2^{n+2}}=\frac{k^2-1}{2^3}\times \prod_{r=1}^{n-1}\frac{k^{2^r}+1}{2}$$ which is an integer because $k^2\equiv 1\pmod 8$ and all powers of $k$ are odd.

Answer 2

A simple solution for non-advanced people like me:

By using the factorization of the difference of squares: $$k^{2^{n}}-1=(k^{2^{n-1}}+1)(k^{2^{n-2}}+1)(k^{2^{n-3}}+1)\ldots(k+1)(k-1)$$ This obviously has $n+1$ terms (as an example factor $x^2-1$ or $x^8-1$). And if $k$ is odd all of the terms in the product is even and thus $k^{2^{n}}-1$ is divisible by $2^{n+1}$.

Of course, the question was testing divisibility with $2^{n+2}$, the other factor of $2$ come in with either the $k-1$ or the $k+1$ term. Since $k$ is odd both $k-1$ and $k+1$ are even and thus one must be divisible by $4$ (because of consecutive evens).

I don't know if this is a valid proof, as the above proof was far more complex than mine so can someone please verify this?

Answer 3

The trick is $k^{2*m} - 1 = (k^m -1)(k^m+1)$ and if $2^z\mid k^m -1$ then $k^m$ is odd and $k^m + 1$ is even so $2^z|k^m-1$ and $2\mid k^m+1$ so $2^z*2\mid (k^m-1)(k^m+1)$.

So by induction:

Base case: If $k$ is odd the $k = 2m+1$ for some $m$ and $(2m+1)^2-1= 4m^2 + 4m = 4m(m-1)$ either $m$ or $m-1$ is even so $2|m(m-1)$ and $2^3 = 8 = 4*2\mid 4*m(m-1)$

Induction case: So if ${2^{k-1}}\mid (k^{2^{k+1}}-1)$ then $k$ is odd and $2^{2^k}=2^{2^{k-1}}*2\mid (k^{2^{k+1}}-1)(k^{2^{k+1}} + 1) = (k^{2^{k+2}} - 1)$.