IMO 2000 · Problem 5

Can we find \(N\) divisible by just 2000 different primes, so that \(N\) divides \(2^N+1\)? [\(N\) may be divisible by a prime power.]

Official text of the problem. Official problem paper (PDF)

Answer

Yes. In fact, such an \(N\) exists with any prescribed positive number of distinct prime divisors.

Solution

We prove by induction that for every integer \(k\ge1\), there is an odd positive integer \(n\), divisible by \(3\), with exactly \(k\) distinct prime divisors and satisfying \[ n\mid 2^n+1. \] For \(k=1\), take \(n=3\).

Suppose such an \(n\) has been constructed. Put \[ x=2^n,\qquad A=x^2-x+1. \] Since \(n\) is odd, \(x\equiv-1\pmod3\). Writing \(x=3t-1\), we obtain \[ A=3(3t^2-3t+1). \] Thus \(3\mid A\) but \(9\nmid A\). Also \(n\ge3\), so \(x\ge8\) and \(A>3\). Consequently, \(A/3>1\) has a prime divisor \(q\ne3\). Since \(A\) is odd, \(q\) is odd.

We claim that \(q\nmid n\). Otherwise, \(n\mid x+1\) would imply \(x\equiv-1\pmod q\), giving \[ 0\equiv A=x^2-x+1\equiv3\pmod q, \] contrary to \(q\ne3\).

Now set \[ m=3nq. \] Because \(n\mid x+1\) and \(3\mid A\), \[ 3n\mid(x+1)A=x^3+1=2^{3n}+1. \] Furthermore, \(q\mid A\) and \(\gcd(q,3n)=1\), so \[ m\mid2^{3n}+1. \] As \(q\) is odd, this yields \[ 2^m=(2^{3n})^q\equiv(-1)^q=-1\pmod m. \] Hence \(m\mid2^m+1\). Moreover, \(m\) is odd and has exactly \(k+1\) distinct prime divisors: \(3\) already divides \(n\), while \(q\) does not.

This completes the induction. Taking \(k=2000\) gives the required \(N\).

The solution was checked against Evan Chen's published IMO solution notes.