Austrian Mathematical Olympiad

It is obvious that $N$ and $2012$ must be relatively prime. If $N^k \equiv 1 \pmod{n}$ and $N^m \equiv 1 \pmod{n}$ both hold, so does $N^d \equiv 1 \pmod{n}$ for $d = \gcd(k, m)$. From $m = \varphi(n)$, we see that $N^k \equiv 1 \pmod{n}$ implies that there exists a divisor $d$ of $\varphi(n)$ with $N^d \equiv 1 \pmod{n}$. Since $2012 = 4 \cdot 503$ and $\varphi(503) = 502 = 2 \cdot 251$ (where $503$ and $251$ are both prime), the only possible exponents $d$ with $N^d \equiv 1 \pmod{503}$ of interest to us are $1$, $2$, $251$ and $502$. We need therefore only consider the exponents $d=1$ and $d=2$. Since $N^1 \equiv 1$ automatically implies $N^2 \equiv 1$ we only require the rests $+1$ and $-1$ modulo $503$. Since $N^2 \equiv 1 \pmod{4}$ holds for all odd values of $N$, the values of $n$ with the required property are exactly the numbers $N = 1006 \cdot u + 1$ and $N = 1006 \cdot v - 1$. Since $1006 \cdot 995 = 1000970$ and $1006 \cdot 994 = 999964$, only $0 \le u \le 994$ and $1 \le v \le 994$ are possible, and the required number of integers $N$ is equal to $995 + 994 = 1989$.
$\square$