# 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.

-
Have you played around and checked e.g. which remainders mod $2^5$ the powers $1^1, 2^2, 3^3, 4^4, 5^5, 6^6, 7^7, 8^8, 9^9, \ldots$ have? –  Hagen von Eitzen Apr 9 '13 at 22:34
Not sure that helps, but $2011$ is prime. –  1015 Apr 9 '13 at 22:55
This smells awfully of Euler's theorem... it surely isn't a coincidence that $2011 \equiv -1 \pmod{2012}$ –  vonbrand Apr 9 '13 at 22:59
this is so 2012... –  Lost1 Apr 9 '13 at 23:00
Following on from Hagen von Eitzen's comment I find that $1^1+2^2+3^3+ \cdots \equiv 1,4,27,0,-11,0,-9,0,9,0,19,0,-3,0,-17,0,17,0,11,0 \cdots \pmod{2^6}$. The cycle is the same for all $2^k$ as far as I can see. –  John Marty Apr 9 '13 at 23:06

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.

-