Problem 1634

1. Understanding the Problem:
We are given a complex number $\omega$ such that $\omega^{2013} = 1$ and $\omega^m \neq 1$ for $m = 1, 2, \ldots, 2012$. This means $\omega$ is a primitive 2013th root of unity. We need to find the number of ordered pairs $(a, b)$ with $1 \le a, b \le 2013$ such that
$$\frac{(1 + \omega + \cdots + \omega^a)(1 + \omega + \cdots + \omega^b)}{3}$$
is an algebraic integer.

2. Cyclotomic Polynomials:
The sum $1 + \omega + \cdots + \omega^a$ can be simplified using the formula for the sum of a geometric series:
$$1 + \omega + \cdots + \omega^a = \frac{1 - \omega^{a+1}}{1 - \omega}$$
Since $\omega$ is a primitive 2013th root of unity, $1 - \omega$ is a unit in $\mathbb{Z}[\omega]$.

3. Algebraic Integers:
A complex number is an algebraic integer if it is a root of some monic polynomial with integer coefficients. We need to determine when
$$\frac{(1 - \omega^{a+1})(1 - \omega^{b+1})}{3(1 - \omega)^2}$$
is an algebraic integer.

4. Automorphisms and Galois Theory:
Let $f_k$ denote the automorphism that sends $\omega$ to $\omega^k$ where $\gcd(k, 2013) = 1$. The number $t = \frac{(1 - \omega^{a+1})(1 - \omega^{b+1})}{3}$ must be an algebraic integer. By considering the field $\mathbb{Q}[\omega]$, we know that $f_k(t)$ is also an algebraic integer.

5. **Units in $\mathbb{Z}[\omega]$:**
Since $1 - \omega$ is a unit in $\mathbb{Z}[\omega]$, multiplying by it does not change the property of being an algebraic integer. Thus, $t$ is an algebraic integer if and only if
$$\frac{(1 - \omega^{a+1})(1 - \omega^{b+1})}{3}$$
is an algebraic integer.

6. Cyclotomic Polynomial Evaluation:
We use the fact that
$$\prod_{k \in S} f_k(1 - \omega^{a+1}) = \Phi_{n}(1)^{\varphi(2013)/\varphi(n)}$$
where $n = \frac{2013}{\gcd(2013, a+1)}$. By the lemma, $\Phi_n(1) = 1$ if $n$ is not a prime power, and $\Phi_n(1) = p$ if $n$ is a prime power $p$.

7. Condition for Algebraic Integer:
The expression
$$\frac{\Phi_{n}(1)^{\varphi(2013)/\varphi(n)} \cdot \Phi_{n'}(1)^{\varphi(2013)/\varphi(n')}}{3^{1200}}$$
is integral if and only if $\frac{2013}{\gcd(a+1, 2013)} = \frac{2013}{\gcd(b+1, 2013)} = 3$ or one of the gcd's is 2013.

8. Counting Valid Pairs:
For $\frac{2013}{\gcd(a+1, 2013)} = 3$, $\gcd(a+1, 2013) = 671$. There are $\varphi(3) = 2$ such values for $a+1$ and similarly for $b+1$. Thus, there are $2 \times 2 = 4$ pairs $(a, b)$.

For one of the gcd's being 2013, there are $2013$ choices for $a$ and $2$ choices for $b$, giving $2013 \times 2 = 4026$ pairs. Adding the cases where both gcd's are 2013, we get $2013 \times 2 - 1 + 2 \times 2 = 4029$.

The final answer is $\boxed{4029}$.