Show that $(k+1) \nmid 2^{k}+1$ for any $k\in \mathbb{N}$

Question

Show that $(k+1) \nmid 2^{k}+1$ for any $k\in \mathbb{N}$

I had found out this question from somewhere and here's my solution. I am not sure if I am missing out something in the solution. Please check if it's correct.

My partial solution (not sure if it adds any value) :

If $k$ is odd there's a clear contradiction since an even number can't divide an odd number, which shows $k$ is even.

This shows that $k+1$ is odd, meaning, it has got all odd prime divisors. Let $p$ be an odd prime dividing it. Since $k$ is even, observe that $2^{k}$ is a squared number and $2^{k}\equiv -1 \pmod{p}$. By the theorem stated here we see that $p = 4x+1$ for some $x$. This shows that each and every odd prime factor of $k+1$ is of the form $4j+1$ and so is $k+1$.

---

And I couldn't proceed anymore!

Answer 1

You are on the right track. If $k$ is odd there is no way that $(k+1)$ is a divisor of $2^k+1$, so $k$ is even. If $k$ is even all the prime divisors of $2^k+1$ are of the form $4j+1$, hence $k$ is a multiple of $4$, say $k=4m$. All the prime divisors of $$ 2^{4m}+1 = \Phi_8(2^m) $$ are $\equiv 1\pmod{8}$, hence $k$ is a multiple of $8$, say $k=8n$. All the prime divisors of $$ 2^{8n}+1 = \Phi_{16}(2^n) $$ are $\equiv 1\pmod{16}$, hence $k$ is a multiple of $16$ etcetera, this process never stops.

Answer 2

First of all, $k$ is even. We multiply $2$ to the right factor. Suppose that $k+1|2^{k+1}+2$. Then, $2^{k+1}+2-2(k+1)$ is also a multiple of $k+1$. We consider a maximum odd prime divisor of $k+1$. Denote it by $p$. With use of the binomial theorem, $2^{k+1}+2-2(k+1)$= the summation of $k+1$; choose $i$ from $2$ to $k-1$ and $2$, we can observe that $k+1$; choose $i$ (for $i=2,..,k-1$) is a multiple of $p$ with small computation. Therefore, $p|k+1|2^{k+1}+2-2(k+1)$, which is a contradiction.

For the small computation, first take $i$ up to $\dfrac k2$. By symmetry, it is sufficient. Then, the number of $p$ in denominator is less than that in numerator. It's quite intuitive but I recommend you to draw a line with $p$ multiples points.