Let's work through this problem step by step: find all positive integers (n) such that (n^2) divides (2^n + 1). I'll start with the key number theory tool we need, then build up to the full solution.

Problem Statement #

Find all positive integers (n) where (n^2 \mid 2^n + 1).

Solution Approach & Proof #

First, we'll rely on the Lifting The Exponent (LTE) Lemma—a super useful tool for tackling divisibility problems involving powers. Let's start with core definitions and the lemma itself:

Key Definition #

Let (v_p(n)) denote the highest power of a prime (p) that divides (n). Formally, (v_p(n) = k) means (p^k \mid n) but (p^{k+1} \nmid n).

LTE Lemma Breakdown #

We split this into cases based on the prime (p):

• For any odd prime (p):
  $$v_p(x^n - y^n) = v_p(x - y) + v_p(n)$$
• For the prime (2):
  $$v_2(x^n - y^n) = v_2(x - y) + v_2(x + y) + v_2(n) - 1$$
• When (n) is odd, substitute (y) with (-y) to get the sum version of the lemma:
  $$v_p(x^n + y^n) = v_p(x + y) + v_p(n)$$

Now let's apply this to our problem:

1. (n) must be odd: Since (2^n + 1) is always odd, (n) can't have 2 as a factor (even (n^2) can't divide an odd number).
2. All prime divisors of (n) are 3: Let (p) be a prime divisor of (n). Then (p \mid 2^n + 1), so (2^{2n} \equiv 1 \pmod{p}). The order of 2 modulo (p) divides (2n) but not (n), so it must divide 2. This means (2^2 \equiv 1 \pmod{p}), so (p \mid 3). The only possible prime divisor of (n) is 3.
3. Check powers of 3: Let (n = 3^k) where (k \geq 1). We need (3^{2k} \mid 2^{3k} + 1). Using the odd prime LTE lemma with (p=3), (x=2), (y=1), (n=3^k):
   $$v_3(2^{3k} + 1) = v_3(2 + 1) + v_3(3^k) = 1 + k$$
   We need (1 + k \geq 2k), which simplifies to (k \leq 1).
4. Verify valid values:
   • (k=1): (n=3), (3^2=9), and (2^3 + 1 = 9) — (9 \mid 9), so this works.
   • (k=0): (n=1), (1^2=1) divides any integer, so (1 \mid 3) — this also works.

Final Result #

The only positive integers (n) satisfying (n^2 \mid 2^n + 1) are 1 and 3.

内容的提问来源于stack exchange，提问作者QFTheorist