Japan Mathematical Olympiad

$$\boxed{\frac{2100^{210}}{2^{164} \cdot 3^{30}}}$$
Let the function $\gcd(a, b)$ denote the greatest common divisor of $|a|$ and $|b|$, with the definition that the greatest common divisor of $0$ and a non-negative integer $x$ is $x$. Let us also denote that, for conditions $P_1, P_2, \dots, P_k$, the notation $\sum_{P_1, P_2, \dots, P_k}$ represents the sum under the conditions where all of $P_1, P_2, \dots, P_k$ are satisfied. Unless otherwise stated, the modulus for congruences will be $2100$ in the following.

Let $M = 210$. Note that $M$ is square-free. For any prime $p$, $p \mid 2100$ and $p \mid 210$ are equivalent, thus $\gcd(s, 2100) = 1$ is equivalent to $\gcd(s, 210) = 1$ for any integer $s$.

Consider tuples of integers $(a_1, a_2, \dots, a_{2100})$ and $(b_1, b_2, \dots, b_{2100})$ satisfying
$$a_i \equiv \sum_{\substack{\gcd(j-i, 2100)=1 \\ 1 \le j \le 2100}} b_j.$$
For integers $i$ from $1$ to $M$, take integers $c_i$ from $0$ to $2099$ such that $c_i = \sum_{j=0}^{9} b_{i+M j}$ holds. Then, for integers $l$ from $1$ to $2100$, it follows that $a_l = \sum_{\substack{\gcd(j-l, M)=1 \\ 1 \le j \le M}} c_j$, and thus $a_{i+kM} \equiv a_i$ holds for integers $i$ from $1$ to $M$ and integers $k$ from $0$ to $9$. Conversely, for any tuple $(c_1, c_2, \dots, c_M)$ of integers from $0$ to $2099$, if we take $b_i$ as $\begin{cases} c_i & (1 \le i \le M), \\ 0 & (M+1 \le i \le 2100) \end{cases}$, then $c_i = \sum_{j=0}^{9} b_{i+M j}$ ($1 \le i \le M$) holds. Hence it suffices to find the number of tuples $(a_1, a_2, \dots, a_M)$ of integers from $0$ to $2099$ that satisfy the following condition:

There exists some tuple $(c_1, c_2, \dots, c_M)$ of integers from $0$ to $2099$ such that $a_i = \sum_{\substack{\gcd(j-i, M)=1 \\ 1 \le j \le M}} c_j$ holds for any integer $i$ from $1$ to $M$.

In the following, a tuple of $M$ integers from $0$ to $2099$ is called a good tuple, and for simplicity, we write $(A_i)$ to represent a good tuple $(A_1, A_2, \dots, A_M)$. We also define that $A_{k+M} = A_k$ for any good tuple $(A_i)$ and any positive integer $k$. Additionally, $i$ will represent an integer from $1$ to $M$ and $g(i)$ will denote $\gcd(i, M)$ hereinafter.

If good tuples $(S_i)$ and $(s_i)$ satisfy the following condition, $(S_i)$ is called the parent of $(s_i)$ and $(s_i)$ is called a child of $(S_i)$, respectively:
$$S_i = \sum_{j=0}^{g(i)-1} s_{i+\frac{M}{g(i)}j}$$
Furthermore, a good tuple $(s'_i)$ is called the inverse of $(s_i)$ if they satisfy the following condition:
$$s'_i = \sum_{\substack{M \mid j(j-i) \\ 1 \le j \le M}} \mu(j)s_j.$$
Here, $\omega(n)$ denotes the number of distinct prime factors of $n$, and $\mu(n)$ is defined by $\mu(n) = (-1)^{\omega(g(n))}$.

Lemma 1. $\mu(n)$ satisfies the following two properties.
(1) For coprime positive integers $m$ and $n$, $\mu(mn) = \mu(m)\mu(n)$.
(2) For a positive divisor $n$ of $M$,
$$\sum_{x|n} \mu(x) = \begin{cases} 1 & (n=1), \\ 0 & (n \ge 2). \end{cases}$$

Proof of Lemma 1.
(1) Since $m$ and $n$ are coprime, $g(mn) = g(m)g(n)$. Since $g(m)$ and $g(n)$ are also coprime, $\omega(g(m)g(n)) = \omega(g(m)) + \omega(g(n))$. Therefore,
$$\mu(mn) = (-1)^{\omega(g(mn))} = (-1)^{\omega(g(m))+\omega(g(n))} = (-1)^{\omega(g(m))}(-1)^{\omega(g(n))} = \mu(m)\mu(n)$$
follows.
(2) The case of $n=1$ is obvious. Assume $n \ge 2$. We write $n = 2^{e_2}3^{e_3}5^{e_5}7^{e_7}$ with $e_2, e_3, e_5, e_7 \in \{0, 1\}$. By property (1),
$$\sum_{x|n} \mu(x) = \left( \sum_{0 \le e_2 \le e_1} \mu(2^{e_2}) \right) \left( \sum_{0 \le e_3 \le e_1} \mu(3^{e_3}) \right) \left( \sum_{0 \le e_5 \le e_1} \mu(5^{e_5}) \right) \left( \sum_{0 \le e_7 \le e_1} \mu(7^{e_7}) \right).$$
Since $n \ge 2$, we can take $q \in \{2, 3, 5, 7\}$ with $e_q = 1$, which satisfies $\mu(q^0) + \mu(q^1) = 0$.
Therefore, $\sum_{x|n} \mu(x) = 0$ holds for $n \ge 2$.

Thus we have Lemma 1.

Next, we prove the following two lemmas.

Lemma 2. The following two properties hold:
(1) For any good tuple $(s_i)$, there exists exactly one child.
(2) For any good tuple $(s_i)$, there exists exactly one good tuple whose inverse is $(s_i)$.

Proof of Lemma 2.
(1) Note that, since there are only finite good tuples, it suffices to show that the number of child for a given good tuple is at most one. To be more precise, we show that if $(S_i)$ and $(T_i)$ are the parents of $(s_i)$ and $(t_i)$, respectively, then $(S_i) = (T_i)$ $\Rightarrow$ $(s_i) = (t_i)$.
Suppose otherwise, i.e., $(S_i) = (T_i)$ and there exists an $i$ such that $s_i \neq t_i$. Without loss of generality, we can assume that $i$ is the smallest among such integers. Since $\gcd(g(i), \frac{M}{g(i)}) = \gcd(i, \frac{M}{g(i)}) = 1$ and $g(i) \mid i$, it holds for any integer $j$ that
$$\begin{aligned} g\left(i + \frac{M}{g(i)}j\right) &= \gcd\left(g(i) \cdot \frac{M}{g(i)}, i + \frac{M}{g(i)}j\right) \\ &= \gcd\left(g(i), i + \frac{M}{g(i)}j\right) \gcd\left(\frac{M}{g(i)}, i + \frac{M}{g(i)}j\right) \\ &= \gcd\left(g(i), \frac{M}{g(i)}j\right) \gcd\left(\frac{M}{g(i)}, i\right) \\ &= \gcd(g(i), j). \end{aligned}$$
Therefore, for $1 \le j \le g(i) - 1$, $g\left(i + \frac{M}{g(i)}j\right) < g(i)$ and thus $s_{i+\frac{M}{g(i)}j} = t_{i+\frac{M}{g(i)}j}$ by the minimality of $g(i)$. Hence,
$$s_i \equiv S_i - \sum_{j=1}^{g(i)-1} s_{i+\frac{M}{g(i)}j} \equiv T_i - \sum_{j=1}^{g(i)-1} t_{i+\frac{M}{g(i)}j} \equiv t_i,$$
which contradicts the assumption that $s_i \neq t_i$.

(2) Similarly to (1), let $(s'_i)$ and $(t'_i)$ be the inverses of $(s_i)$ and $(t_i)$, respectively, and it suffices to show that $(s'_i) = (t'_i) \Rightarrow (s_i) = (t_i)$.
Suppose $(s'_i) = (t'_i)$ and there exists an $i$ such that $s_i \neq t_i$. Again, we can assume that $i$ is the smallest among such integers without loss of generality. Since $g(i) \mid M$, if $1 \le j \le M$ and $M \mid j(j - i)$, then $j^2 \equiv j(j - i) \equiv 0 \pmod{g(i)}$. Since $g(i)$ is square-free, we have $g(i) \mid j$ and thus $g(i) \mid g(j)$. Noting that $g(j) > g(i) \Rightarrow s_j = t_j$ from the maximality of $g(i)$, $s'_i = t'_i$ means
$$\begin{align*} \sum_{\substack{M \mid j(j-i), g(j)=g(i) \\ 1 \le j \le M}} \mu(j) s_j &\equiv \sum_{\substack{M \mid j(j-i) \\ 1 \le j \le M}} \mu(j) s_j - \sum_{\substack{M \mid j(j-i), g(j)>g(i) \\ 1 \le j \le M}} \mu(j) s_j \\ &\equiv s'_i - \sum_{\substack{M \mid j(j-i), g(j)>g(i) \\ 1 \le j \le M}} \mu(j) s_j \\ &= t'_i - \sum_{\substack{M \mid j(j-i), g(j)>g(i) \\ 1 \le j \le M}} \mu(j) t_j \\ &\equiv \sum_{\substack{M \mid j(j-i), g(j)=g(i) \\ 1 \le j \le M}} \mu(j) t_j. \end{align*}$$
Here, $M \mid j(j - i)$ implies $M/g(j) \mid (j - i)$. Also, $g(j) = g(i)$ implies $g(j) \mid (j - i)$. Since $g(j)$ and $M/g(j)$ are coprime, $M/g(j) \mid (j - i)$ and $g(j) \mid (j - i)$ mean $j = i$ under the condition $1 \le j \le M$. Hence the condition $s'_i = t'_i$ reduces to $s_i = t_i$, which contradicts the assumption that $s_i \ne t_i$.
This concludes the proof of Lemma 2. ■

Lemma 3. Consider good tuples $(a_i)$ and $(c_i)$, with $(A_i)$ and $(C_i)$ being their parents respectively, and let $(C'_i)$ be the inverse of $(C_i)$. The following two conditions are equivalent:
$$(1) \text{ For every } i, \text{ it holds that } a_i \equiv \sum_{\substack{\gcd(j-i,M)=1 \\ 1 \le j \le M}} c_j.$$
(2) For every $i$, it holds that $A_i \equiv \phi(g(i))C'_i$, where $\phi(n)$ is Euler's totient function.

Proof of Lemma 3. (1) $\implies$ (2): Suppose that (1) holds. By definition of inversion, we have
$$C'_i \equiv \sum_{\substack{M \mid j(j-i) \\ 1 \le j \le M}} \mu(j) C_j \equiv \sum_{M \mid j(j-i)} \sum_{k=0}^{g(j)-1} \mu(j) c_{j+\frac{M}{g(j)}k}.$$
Since $\mu(j) = (-1)^{\omega(g(j))} = (-1)^{\omega(g(g(j)))} = \mu(g(j))$, we have
$$C'_i \equiv \sum_{\substack{M \mid j(j-i) \\ 1 \le j \le M}} \sum_{k=0}^{g(j)-1} \mu(g(j)) c_{j+\frac{M}{g(j)}k}.$$
Rearranging terms based on the values of $g(j)$, we have
$$C'_i \equiv \sum_{v \mid M} \sum_{\substack{g(j)=v \\ M \mid j(j-i)}} \sum_{1 \le j \le M}^{v-1} \mu(v) c_{j+\frac{M}{v}k} \equiv \sum_{u=0}^{M-1} \sum_{v \mid M} \sum_{k=0}^{v-1} \sum_{\substack{g(j)=v \\ M \mid j(j-i) \\ j+v'k \equiv i+u \\ 1 \le j \le M}} \mu(v) c_{i+u}$$
where $v' = \frac{M}{v}$.
Thus, the right side can be written as $\sum_{u=0}^{M-1} \sum_{v|M} \alpha_{i,u,v} \mu(v) c_{i+u}$, where $\alpha_{i,u,v}$ is the number of integer pairs $(j, k)$ satisfying $1 \le j \le M, 0 \le k < v, g(j) = v, M | j(j-i)$, and $j+v'k = i+u$. We want to show that
$$\alpha_{i,u,v} = \begin{cases} 1 & (u \equiv 0 \pmod{v'} \text{ and } \gcd(i, v') = 1), \\ 0 & (\text{otherwise}). \end{cases}$$
holds.
Note that $M|j(j - i)$ and $g(j) = v$ mean that $M/v = v' | (j - i)$. Hence, we have $u \equiv j + v'k - i \equiv 0 \pmod{v'}$. This yields $\alpha_{i,u,v} = 0$ for $u \ne 0 \pmod{v'}$. Also, when $\gcd(i, v') \ne 1$, $v' | (j - i)$ implies $\gcd(j, v') \ne 1$ and thus $g(j) \ne v$. This yields $\alpha_{i,u,v} = 0$ for the case $\gcd(i, v') \ne 1$.
We now consider the case $u \equiv 0 \pmod{v'}$ and $\gcd(i, v') = 1$, and determine the number of pairs $(j, k)$ satisfying five conditions above. $g(j) = v$ implies $v | j$, or $j \equiv 0 \pmod{v}$. On the other hand, $j + v'k \equiv i + u \equiv i \pmod{v'}$ since $u \equiv 0 \pmod{v'}$. Since $v$ and $v'$ are coprime, there exists unique $j$ (up to mod $M$) that satisfies both congruences by the Chinese remainder theorem. Additionally, when $j$ is fixed, there is at most one $k$ that satisfies $j + v'k \equiv i + u$ and $0 \le k < v$. Hence, $\alpha_{i,u,v} \le 1$ for this case.
On the other hand, Chinese remainder theorem assures that we can take $j$ such that $1 \le j \le M, v | j$ and $v' | (j - i)$ are satisfied. Moreover, since $j \equiv i \pmod{v'}$ and $u \equiv 0 \pmod{v'}$, we can take $k$ such that $0 \le k < v$ and $j + v'k \equiv i + u \equiv u \pmod{v'}$ are satisfied. Since $v' | (j - i)$, it holds $\gcd(j, v') = \gcd(i, v') = 1$. Together with $v | j$, we have $g(j) = v$. Since $v | j$ and $v' | (j - i)$, it holds $M = vv' | j(j - i)$. This implies that we can construct the pair $(j, k)$ that satisfies all five conditions, and thus $\alpha_{i,u,v} \ge 1$. This concludes that $\alpha_{i,u,v} = 1$ for $u \equiv 0 \pmod{v'}$ and $\gcd(i, v') = 1$.
Note that $u \equiv 0 \pmod{v'}$ is equivalent to $\frac{M}{g(u)} | v$, and that $\gcd(i, v') = 1$ is equivalent to $g(i) | v$, we have
$$\sum_{v|M} \alpha_{i,u,v} \mu(v) = \sum_{v|M, \frac{M}{g(u)}|v, g(i)|v} \mu(v)$$
In this sum, if we let $v = g(i)w$, $w$ varies while satisfying $w \mid \frac{M}{g(i)}$ and $\frac{M}{g(u)} | g(i)w$. This is equivalent to $w \mid \frac{M}{g(i)}$ and $\frac{M}{g(iu)} | w$, thus letting $w = \frac{M}{g(iu)}x$, $x$ varies over all positive divisors of $\frac{g(iu)}{g(i)}$, and we have
$$\mu(v) = \mu(g(i)w) = \mu\left(\frac{Mg(i)}{g(iu)}x\right).$$
Since $x$ is a positive divisor of $\frac{g(iu)}{g(i)}$, $\frac{Mg(i)}{g(iu)}$ and $x$ are coprime and thus
$$\mu\left(\frac{Mg(i)}{g(iu)}x\right) = \mu\left(\frac{Mg(i)}{g(iu)}\right) \mu(x)$$
holds.
Since $\frac{g(iu)}{g(i)}$ is a divisor of $M$, according to Lemma 1(2), $\sum_{x|\frac{g(iu)}{g(i)}} \mu(x)$ is equal to $1$ when $\frac{g(iu)}{g(i)} = 1$ (i.e., $g(u) | g(i)$), and $0$ otherwise. Furthermore, when $g(u) | g(i)$, we have $\mu\left(\frac{Mg(i)}{g(iu)}\right) = \mu(M) = 1$. Hence
$$C'_i = \sum_{u=0}^{M-1} \mu\left(\frac{Mg(i)}{g(iu)}\right) \sum_{x|\frac{g(iu)}{g(i)}} \mu(x)c_{i+u} = \sum_{\substack{g(u)|g(i) \\ 0 \le u < M}} c_{i+u}.$$
On the other hand, since we assume that (1) holds, we have
$$A_i \equiv \sum_{j=0}^{g(i)-1} a_{i+\frac{M}{g(i)}j} \equiv \sum_{j=0}^{g(i)-1} \sum_{\substack{k=1 \\ 1 \le k \le M}}^{g(k)=1} c_{i+\frac{M}{g(i)}j+k}$$
and the coefficient of $c_{i+u}$ is the number of pairs of integers $(j, k)$ satisfying $0 \le j \le g(i) - 1$, $1 \le k \le M$, $\frac{M}{g(i)}j + k \equiv u$, and $g(k) = 1$. This is the number of $k$ satisfying $1 \le k \le M$, $k \equiv u \pmod{\frac{M}{g(i)}}$ and $g(k) = 1$. Therefore, by the Chinese remainder theorem, the coefficient of $c_{i+u}$ is $0$ when $\gcd(u, \frac{M}{g(i)}) > 1$ (i.e., when $g(u) \nmid g(i)$), and $\phi(g(i))$ otherwise (i.e., when $g(u) | g(i)$). Hence we have $A_i \equiv \phi(g(i)) \sum_{\substack{g(u)|g(i) \\ 0 \le u < M}} c_{i+u} \equiv \phi(g(i))C'_i$, which concludes this part.
$$(2) \implies (1): \text{ Suppose that (2) holds. Define a good tuple } (\tilde{a}_i) \text{ by } \tilde{a}_i \equiv \sum_{\substack{\gcd(j-i,M)=1 \\ 1 \le j \le M}} c_j, \text{ and let}$$
$(\tilde{A}_i)$ be the parent of $(\tilde{a}_i)$. Since we have $(A_i) = (\tilde{A}_i)$ from the above argument, (1) follows from the uniqueness of child. ■

From Lemmas 2 and 3, what we need to find is the number of good tuples $(A_i)$ such that there exists some good tuple $(C'_i)$ for which $A_i \equiv \phi(g(i))C'_i$ holds for every $i$. This number is equal to $\prod_{i=1}^{M} \frac{2100}{\gcd(2100, \phi(g(i)))}$. Since $\phi(g(i))$ is a divisor of $\phi(M) = 48$, $\gcd(2100, \phi(g(i)))$ is a divisor of $\gcd(2100, 48) = 12$.

* $2 \mid \gcd(2100, \phi(g(i)))$ is equivalent to claim that $i$ is a multiple of $3$, $5$, or $7$, hence the number of such $i$ is $2 \cdot (3 \cdot 5 \cdot 7 - 2 \cdot 4 \cdot 6) = 114$.
* $4 \mid \gcd(2100, \phi(g(i)))$ is equivalent to claim that $i$ is a multiple of either $21$ or $5$, hence the number of such $i$ is $2 \cdot (21 \cdot 5 - 20 \cdot 4) = 50$.
* $3 \mid \gcd(2100, \phi(g(i)))$ is equivalent to claim that $7 \mid i$, hence the number of such $i$ is $30$.

Thus, the answer is $\frac{2100^M}{2^{114+50} \cdot 3^{30}} = \frac{2100^{210}}{2^{164} \cdot 3^{30}}$.