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 _{\begin{array}{c}\gcd (j-i,2100)=1\\ 1\le j\le 2100\end{array}}{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+Mj}$ holds. Then, for integers $l$ from $1$ to $2100$, it follows that $a_l={\sum }_{\begin{array}{c}\gcd (j-l,M)=1\\ 1\le j\le M\end{array}}{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 , then $c_i={\sum }_{j=0}^9{b}_{i+Mj}$ ($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 }_{\begin{array}{c}\gcd (j-i,M)=1\\ 1\le j\le M\end{array}}{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^{\prime })$ is called the inverse of $(s_i)$ if they satisfy the following condition: $$s_i^{\prime }=\sum _{\begin{array}{c}M\mid j(j-i)\\ 1\le j\le M\end{array}}\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{array}{ll}1& (n=1),\\ 0& (n\ge 2).\end{array}$$

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\ne 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{array}{rl}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{array}$$ 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\ne t_i$.

(2) Similarly to (1), let $(s_i^{\prime })$ and $(t_i^{\prime })$ be the inverses of $(s_i)$ and $(t_i)$, respectively, and it suffices to show that $(s_i^{\prime })=(t_i^{\prime })\Rightarrow (s_i)=(t_i)$. Suppose $(s_i^{\prime })=(t_i^{\prime })$ and there exists an $i$ such that $s_i\ne 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(\mathrm{mod}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^{\prime }=t_i^{\prime }$ means $$\begin{array}{rl}\sum _{\begin{array}{c}M\mid j(j-i),g(j)=g(i)\\ 1\le j\le M\end{array}}\mu (j)s_j& \equiv \sum _{\begin{array}{c}M\mid j(j-i)\\ 1\le j\le M\end{array}}\mu (j)s_j-\sum _{\begin{array}{c}M\mid j(j-i),g(j)>g(i)\\ 1\le j\le M\end{array}}\mu (j)s_j\\ & \equiv s_i^{\prime }-\sum _{\begin{array}{c}M\mid j(j-i),g(j)>g(i)\\ 1\le j\le M\end{array}}\mu (j)s_j\\ & =t_i^{\prime }-\sum _{\begin{array}{c}M\mid j(j-i),g(j)>g(i)\\ 1\le j\le M\end{array}}\mu (j)t_j\\ & \equiv \sum _{\begin{array}{c}M\mid j(j-i),g(j)=g(i)\\ 1\le j\le M\end{array}}\mu (j)t_j.\end{array}$$ 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^{\prime }=t_i^{\prime }$ 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^{\prime })$ 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 _{\begin{array}{c}\gcd (j-i,M)=1\\ 1\le j\le M\end{array}}{c}_j.$$ (2) For every $i$, it holds that $A_i\equiv \varphi (g(i))C_i^{\prime }$, where $\varphi (n)$ is Euler's totient function.

Proof of Lemma 3. (1) $⟹$ (2): Suppose that (1) holds. By definition of inversion, we have $$C_i^{\prime }\equiv \sum _{\begin{array}{c}M\mid j(j-i)\\ 1\le j\le M\end{array}}\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^{\prime }\equiv \sum _{\begin{array}{c}M\mid j(j-i)\\ 1\le j\le M\end{array}}\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^{\prime }\equiv \sum _{v\mid M}\sum _{\begin{array}{c}g(j)=v\\ M\mid j(j-i)\end{array}}\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 _{\begin{array}{c}g(j)=v\\ M\mid j(j-i)\\ j+v^{\prime }k\equiv i+u\\ 1\le j\le M\end{array}}\mu (v)c_{i+u}$$ where $v^{\prime }=\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^{\prime }k=i+u$. We want to show that $${\alpha }_{i,u,v}=\{\begin{array}{ll}1& (u\equiv 0(\mathrm{mod}{v}^{\prime })\text{ and }\gcd (i,v^{\prime })=1),\\ 0& (\text{otherwise}).\end{array}$$ holds. Note that $M|j(j-i)$ and $g(j)=v$ mean that $M/v=v^{\prime }|(j-i)$. Hence, we have $u\equiv j+v^{\prime }k-i\equiv 0(\mathrm{mod}{v}^{\prime })$. This yields ${\alpha }_{i,u,v}=0$ for $u\ne 0(\mathrm{mod}{v}^{\prime })$. Also, when $\gcd (i,v^{\prime })\ne 1$, $v^{\prime }|(j-i)$ implies $\gcd (j,v^{\prime })\ne 1$ and thus $g(j)\ne v$. This yields ${\alpha }_{i,u,v}=0$ for the case $\gcd (i,v^{\prime })\ne 1$. We now consider the case $u\equiv 0(\mathrm{mod}{v}^{\prime })$ and $\gcd (i,v^{\prime })=1$, and determine the number of pairs $(j,k)$ satisfying five conditions above. $g(j)=v$ implies $v|j$, or $j\equiv 0(\mathrm{mod}v)$. On the other hand, $j+v^{\prime }k\equiv i+u\equiv i(\mathrm{mod}{v}^{\prime })$ since $u\equiv 0(\mathrm{mod}{v}^{\prime })$. Since $v$ and $v^{\prime }$ 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^{\prime }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^{\prime }|(j-i)$ are satisfied. Moreover, since $j\equiv i(\mathrm{mod}{v}^{\prime })$ and $u\equiv 0(\mathrm{mod}{v}^{\prime })$, we can take $k$ such that $0\le k<v$ and $j+v^{\prime }k\equiv i+u\equiv u(\mathrm{mod}{v}^{\prime })$ are satisfied. Since $v^{\prime }|(j-i)$, it holds $\gcd (j,v^{\prime })=\gcd (i,v^{\prime })=1$. Together with $v|j$, we have $g(j)=v$. Since $v|j$ and $v^{\prime }|(j-i)$, it holds $M=v{v}^{\prime }|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(\mathrm{mod}{v}^{\prime })$ and $\gcd (i,v^{\prime })=1$. Note that $u\equiv 0(\mathrm{mod}{v}^{\prime })$ is equivalent to $\frac{M}{g(u)}|v$, and that $\gcd (i,v^{\prime })=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^{\prime }=\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 _{\begin{array}{c}g(u)|g(i)\\ 0\le u<M\end{array}}{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 _{\begin{array}{c}k=1\\ 1\le k\le M\end{array}}^{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(\mathrm{mod}\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 $\varphi (g(i))$ otherwise (i.e., when $g(u)|g(i)$). Hence we have $A_i\equiv \varphi (g(i)){\sum }_{\begin{array}{c}g(u)|g(i)\\ 0\le u<M\end{array}}{c}_{i+u}\equiv \varphi (g(i))C_i^{\prime }$, which concludes this part. $$(2)⟹(1):\text{ Suppose that (2) holds. Define a good tuple }({\tilde{a}}_i)\text{ by }{\tilde{a}}_i\equiv \sum _{\begin{array}{c}\gcd (j-i,M)=1\\ 1\le j\le M\end{array}}{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^{\prime })$ for which $A_i\equiv \varphi (g(i))C_i^{\prime }$ holds for every $i$. This number is equal to ${\prod }_{i=1}^M\frac{2100}{\gcd (2100,\varphi (g(i)))}$. Since $\varphi (g(i))$ is a divisor of $\varphi (M)=48$, $\gcd (2100,\varphi (g(i)))$ is a divisor of $\gcd (2100,48)=12$.

$2\mid \gcd (2100,\varphi (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,\varphi (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,\varphi (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}}$.