23. (ROM 5) ${ }^{\mathrm{IMO} 3}$ Find all positive integers $n$ having the property that $\frac{2^{n}+1}{n^{2}}$ is an integer.
23. Let us assume \( n > 1 \). Obviously \( n \) is odd. Let \( p \geq 3 \) be the smallest prime divisor of \( n \). In this case \((p-1, n)=1\). Since \( 2^n + 1 \mid 2^{2n} - 1 \), we have that \( p \mid 2^{2n} - 1 \). Thus it follows from Fermat's little theorem and elementary number theory that \( p \mid (2^{2n} - 1, 2^{p-1} - 1) = 2^{(2n, p-1)} - 1 \). Since \((2n, p-1) \leq 2\), it follows that \( p \mid 3 \) and hence \( p = 3 \). Let us assume now that \( n \) is of the form \( n = 3^k d \), where \( 2, 3 \nmid d \). We first prove that \( k = 1 \). Lemma. If \( 2^m - 1 \) is divisible by \( 3^r \), then \( m \) is divisible by \( 3^{r-1} \). Proof. This is the lemma from (SL97-14) with \( p = 3, a = 2^2, k = m \), \(\alpha = 1\), and \(\beta = r\). Since \( 3^{2k} \) divides \( n^2 \mid 2^{2n} - 1 \), we can apply the lemma to \( m = 2n \) and \( r = 2k \) to conclude that \( 3^{2k-1} \mid n = 3^k d \). Hence \( k = 1 \). Finally, let us assume \( d > 1 \) and let \( q \) be the smallest prime factor of \( d \). Obviously \( q \) is odd, \( q \geq 5 \), and \((n, q-1) \in \{1, 3\}\). We then have \( q \mid 2^{2n} - 1 \) and \( q \mid 2^{q-1} - 1 \). Consequently, \( q \mid 2^{(2n, q-1)} - 1 = 2^{2(n, q-1)} - 1 \), which divides \( 2^6 - 1 = 63 = 3^2 \cdot 7 \), so we must have \( q = 7 \). However, in that case we obtain \( 7 \mid n \mid 2^n + 1 \), which is a contradiction, since powers of two can only be congruent to 1, 2, and 4 modulo 7. It thus follows that \( d = 1 \) and \( n = 3 \). Hence \( n > 1 \Rightarrow n = 3 \). It is easily verified that \( n = 1 \) and \( n = 3 \) are indeed solutions. Hence these are the only solutions.