Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.