modular arithmetic - Elementary Number Theory; prove existence

Prove that there exists a positive integer $n$ such that
$$2^{2012}\;|\;n^n+2011.$$

I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ then prove for $2^{k+1}$). But I couldn't get anywhere with that.

Or perhaps you could try and use some modular arithmetic, but that gets nasty.

Any help would be greatly appreciated.

Answer

We prove by induction on $m \geq 1$ that there exists an odd positive integer $n$ such that $2^m \mid n^n+2011$.

When $m=1$, simply take $n=1$. We have $2^1 \mid 1^1+2011$.

Suppose that the statement holds for $m=k$. By the induction hypothesis, there exists an odd positive integer $n$ such that $2^m \mid n^n+2011$. If $2^{m+1} \mid n^n+2011$, then we are done.

Otherwise $n^n+2011 \equiv 2^m \pmod{2^{m+1}}$, so $$(2^m+n)^{2^m+n} \equiv (2^m+n)^n \equiv n^n+\binom{n}{1}n^{n-1}2^m \equiv n^n+2^m \pmod{2^{m+1}}$$ (Note: Here we have used the fact that $\gcd(x, 2)=1$ implies $x^{2^{m-1}}=x^{\varphi(2^{m+1})} \equiv 1 \pmod{2^{m+1}}$) Thus $2^{m+1}\mid (2^m+n)^{2^m+n}+2011$, so we can choose $2^m+n$, which is odd.

We are thus done by induction. In particular, when $m=2012$, there exists a positive integer $n$ such that $2^{2012} \mid n^n+2011$.

P.S. It is a coincidence that $2011$ is prime, and that $2011 \equiv -1 \pmod{2012}$. We only need the fact that $2011$ is odd.