Dividing Your Power

This problem is such an interesting one that, just like a previous problem, was given in an exam, but broken down into more palatable steps.

Problem 1. Prove that there are infinitely many positive even integers $n$ such that $n \mid (2^n + 2)$ and $(n - 1) \mid (2^n+1)$ .

(Click for Solution)

Solution. Consider $n_1 = 2$ , which satisfies the property since $2 \mid (2^2 + 2)$ and $(2-1) \mid (2^2+1)$ trivially. The core idea is to inductively define $n_{i + 1}$ in terms of $n_i$ so that both integers satisfy $n_i \mid (2^{n_i} + 2)$ and $(n_i - 1) \mid (2^{n_i} +1)$ .

To that end, for any even $n_i = n$ such that $n \mid (2^n + 2)$ and $(n - 1) \mid (2^n+1)$ , define $n_{i+1} = m := 2^n + 2$ . We claim that $m \mid (2^m + 2)$ and $(m - 1) \mid (2^m+1)$ . By definition of $m$ , we observe that

$\displaystyle 2^m + 2 = 2\times (2^{m-1} + 1) = 2 \times (2^{2^n + 1} + 1).$

Since $(n - 1) \mid (2^n +1)$ , find an integer $k$ such that $2^n + 1 = k(n-1)$ . Since the left-hand side is odd, the right-hand side must be odd, so that $k$ is odd. Thus,

$2^{2^n + 1} + 1 = 2^{(n-1)k} + 1 = (2^{n-1})^k + 1.$

Consider the function $x^k + 1$ . Since $(-1)^k + 1 = 0$ , by the factor theorem, $(x+1)$ is a factor of $(x^k+1)$ . In particular, $(2^{n-1} + 1) \mid ((2^{n-1})^k + 1)$ . Let $l$ denote an integer such that