How to prove that there exists two powers of $3$ that differ by a number that is divisible by $2011$?

Imagine you calculate $3^n \pmod {2011}$ for a set of $2012 n$'s. Two of these must match.


Among the numbers $3,3^2,.., 3^{2012}$ there exists two with the same remainder when divided by $2011$.


Since $2011$ is prime, by Fermat Little Theorem

$$3^{2010} \equiv 1 \pmod {2011}$$

Thus $3^{2010+k}-3^k$ is divisible by $2011$.

  • P.S. I think $3$ is a primitive root $\pmod{2011}$ which means one can actually find all such pairs of numbers. – N. S. May 21 '13 at 13:55

If you divide by 2011 then there are 2011 possible remainders, if you look at the sequence 3, 3^2, ... 3^2012 then there are 2012 members in this sequence so by the pigeonhole princple two of them must have the same remainder on division by 2011, and hence there difference must be divisible by 2011.

Hint: $2$ of the $2012$ integers $\ 3^0, 3^1, \ldots, 3^{2011}\ $ have the same remainder when divided by $2011,\,$ i.e. the pigeonholes are the $2011$ possible remainders modulo $2011$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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