Brazilian Math Olympiad

Answer: 71.

Since $\underbrace{11\dots1}_{2012 \text{ ones}} = \frac{10^{2012}-1}{9}$, the problem is equivalent to finding the smallest $n$ such that, for some $k$,
$$\begin{align*} n^k &\equiv \frac{10^{2012} - 1}{9} \pmod{10^{2012}} \\ 9n^k &\equiv -1 \pmod{10^{2012}} \\ &\iff n^{-k} \equiv -9 \pmod{10^{2012}} \\ &\iff \left\{ \begin{array}{l} n^{-k} \equiv -9 \pmod{2^{2012}} \\ n^{-k} \equiv -9 \pmod{5^{2012}} \end{array} \right. \end{align*}$$

Let's look at $n^{-k} \bmod 8$ first. It's immediate that $n$ is odd. Since $1^2 \equiv 3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \pmod 8$, we must have $n \equiv 7 \pmod 8$ and $-k$ odd. Now look at it mod 16: let $k = -m$ and $n = 8u - 1$. Then
$$(8u - 1)^m \equiv -1 + 8um \pmod{16}$$

and
$$\begin{align*} n^m &\equiv -9 \pmod{16} \\ 8um - 1 &\equiv -9 \pmod{16} \\ &\iff um \equiv 1 \pmod{2}, \end{align*}$$

that is, $u$ is odd. Therefore $n = 8(2t + 1) - 1 \equiv 7 \pmod{16}$.

Now look at $n^{-k} \bmod 5$: since $-k$ is odd, and $1^3 \equiv 1 \pmod 5$, $2^3 \equiv 3 \pmod 5$, $3^3 \equiv 2 \pmod 5$ and $4^3 \equiv 4 \pmod 5$, we must have $n \equiv 1 \pmod 5$. Putting everything together, we have $n \equiv 7 \pmod{16}$ and $n \equiv 1 \pmod 5 \implies n \equiv 71 \pmod{80}$, and thus $n \ge 71$.

We claim that $n = 71$ does the job. First notice that, by the Lifting the Exponent lemma, $\nu_2(71^N - 1) = \nu_2(71^2 - 1) + \nu_2(N) - 1 = \nu_2(N) + 3$ and $\nu_5(71^N - 1) = \nu_5(71 - 1) + \nu_5(N) = \nu_5(N) + 1$.

Now, notice that this implies $71^v \equiv 71^w \pmod{2^t}$ $\iff 71^{v-w} \equiv 1 \pmod{2^t}$ $\iff \nu_2(v-w) + 3 \ge t \iff 2^{t-3} \mid v-w \iff v \equiv w \pmod{2^{t-3}}$. We analyze now the possible residues of $71^N \pmod{2^t}$: first, we know that $71 \equiv 7 \pmod{16}$, and $71^2 \equiv 1 \pmod{16}$, so all residues $71^N \pmod{2^t}$ are congruent to either 1 or $7 \pmod{16}$, so one eighth of the residues appear, in a total of $2^{t-3}$ residues. But $71^v \equiv 71^w \pmod{2^t}$ $\iff v \equiv w \pmod{2^{t-3}}$, so there are at most $2^{t-3}$ residues. This means that the residues are all numbers congruent to 1 or $7 \pmod{16}$. So, for all $t \ge 4$ there is $N$ such that $71^N \equiv -9 \pmod{2^t}$. Notice that $N$ is unique mod $2^{t-3}$.

The same argument applies mod $5^t$: all residues of $71^N \pmod{5^t}$ are congruent to $1 \pmod 5$ and $71^v \equiv 71^w \pmod{5^t} \iff 71^{v-w} \equiv 1 \pmod{5^t} \iff \nu_5(v-w) + 1 \ge t \iff 5^{t-1} \mid v-w \iff v \equiv w \pmod{5^{t-1}}$. One fifth of the residues appear, all of them congruent to 1 mod 5. So the residues are all numbers congruent to 1 mod 5, and for all $t \ge 2$ there is $N$ such that $71^N \equiv -9 \pmod{5^t}$. Notice that $N$ is unique mod $5^{t-1}$.

We can finish the problem now: we only need to find $N$ that is congruent to a number mod $2^t$ and to a number mod $5^t$, but it exists due to the Chinese remainder theorem. Now plug $t = 2012$.