Find all integers $n>1$ such that$\frac{2^n+1}{n+1}$ is an integer.

Solution 1:

HINT: The following procedure is a sort of descent proving the impossibility of solution.

It is obvious that the denominator cannot be even so $n$ should be even and the quotient (supposing it is integer) should be odd. $$2^{2n}+1=(2n+1)(2k+1)\iff2^{2n}=4kn+2(k+n)\iff2^{2n-1}=2kn+k+n$$ It follows that $k$ and $n$ have the same parity. We have to consider the two possible cases which give $$►(1)\text{ both odd: } 2^{2n-1}==2^3k_1n_1+(2+1)(k_1+n_1)+2^2$$
$$►(2)\text{ both even: } 2^{2n-1}=2^3k_1n_1+2(k_1+n_1) $$ $(1)$ and $(2)$ give respectively $$2^{n-2}=2^2k_1n_1+(2+1)(k_1+n_1)+2\\2^{n-2}=2^2k_1n_1+k_1+n_1$$ Both cases require $k_1$ and $n_1$ have the same parity.

Iterating the procedure we get in each step $k_i$ and $n_i$ have the same parity which leads, after sufficient iterations, to an equality in which an integer is equal to another greater integer. Contradiction.

$$\text{ A concise example}$$ $$(2^6+1)=(6+1)(2k+1)=14k+6+1\iff2^6=14k+6\iff2^5=7k+3\\ 2^5=7k+3\Rightarrow2^5=7(2k_1+1)+3=14k_1+10\iff2^4=7k_1+5\\2^4=7k_1+5\Rightarrow2^4=7(2k_2+1)+5=14k_2+12\iff2^3=7k_2+6\text{ absurde }.$$