Problem 1112

We will show that for every positive integer $k$, there exists a positive integer $n$ such that $(2^n + 1)$ is divisible by $n$, and $n$ has exactly $k$ prime factors.

(Thus, for $k=2000$, such an $n$ also exists.)

We will prove the statement by complete induction on $k$. For $k=1$, it is true: $9 \mid 2^9 + 1$.

For $k=2$: $9 \cdot 19 \mid 2^{9 \cdot 19} + 1$.

Assume that it is true for $k$ ($k \geq 2$):

$$p_{1}^{2} p_{2} p_{3} \ldots p_{k} \mid 2^{p_{1}^{2} p_{2} p_{3} \ldots p_{k}} + 1, \quad p_{1}=3$$

We need to show that it is also true for $k+1$. Let $p_{k+1}$ be a prime number greater than $p_{k}$, and $p_{k+1} \mid 2^{p_{k}} + 1$. $2^{p_{k}} \equiv -1 \quad (\bmod p_{k+1})$, and thus $2^{p_{1}^{2} p_{2} p_{3} \ldots p_{k} p_{k+1}} \equiv (-1)^{p_{1}^{2} p_{2} p_{3} \ldots p_{k-1} p_{k+1}} = -1 \quad (\bmod p_{k+1})$, which means $p_{k+1} \mid 2^{p_{1}^{2} p_{2} p_{3} \ldots p_{k} p_{k+1}} + 1$. On the other hand, by the induction hypothesis, $p_{1}^{2} p_{2} \ldots p_{k} \mid 2^{p_{1}^{2} p_{2} \ldots p_{k}} + 1$, so $2^{p_{1}^{2} p_{2} \ldots p_{k}} \equiv -1 \quad (\bmod p_{1}^{2} p_{2} \ldots p_{k}) \cdot 2^{p_{1}^{2} p_{2} \ldots p_{k} p_{k+1}} \equiv (-1)^{p_{k+1}} = -1 \quad (\bmod p_{1}^{2} p_{2} \ldots p_{k}) \cdot p_{1}^{2} p_{2} \ldots p_{k} p_{k+1} \mid 2^{p_{1}^{2} p_{2} \ldots p_{k} p_{k+1}} + 1$, because $p_{1}^{2} \cdot p_{2} \cdots \cdot p_{k}$ and $p_{k+1}$ are relatively prime. Thus, for $k+1$, $n = p_{1}^{2} \cdot p_{2} \cdots \cdots p_{k} \cdot p_{k+1}$ is suitable, which completes the inductive proof.

Lemma: If $p$ is a prime, then $\left(2^{p} + 1\right)$ has a prime divisor greater than $p$.

Proof. Let $q$ be a prime divisor of $\left(2^{p} + 1\right)$ that is not greater than $p$. Then $q > 2$ and

$$2^{p} \equiv -1 (\bmod q). \quad \text{ Squaring } \quad 2^{2p} \equiv 1 (\bmod q)$$

By Fermat's Little Theorem, $2^{q-1} \equiv 1 (\bmod q)$. From this, using the Euclidean algorithm, we get $2^{(2p, q-1)} \equiv 1 (\bmod q)$. Since $p \mid q-1$, we have $2^{2p} \equiv 1 (\bmod q)$. But $2^{p} \equiv -1 (\bmod q)$, which is a contradiction. Therefore, $\left(2^{p} + 1\right)$ must have a prime divisor greater than $p$.