# Difference of two powers of $3$ divisible by $2011$

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.

Hint:

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

Or

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