Maths Olympiad Prep

Library / /49 of 63

Number theory Difficulty 7.6 National olympiad, round 2 Prove it Japan

Find the number of tuples (a1,a2,,a2100)(a_1, a_2, \dots, a_{2100}) of integers between 00 and 20992099 inclusive that satisfy the following condition:
There exists a tuple of integers (b1,b2,,b2100)(b_1, b_2, \dots, b_{2100}) such that for every integer ii from 11 to 21002100,
aigcd(ji,2100)=11j2100bj(mod2100) a_i \equiv \sum_{\substack{\gcd(j-i, 2100)=1 \\ 1 \le j \le 2100}} b_j \pmod{2100}
holds.

Solution

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

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

Consider tuples of integers (a1,a2,,a2100)(a_1, a_2, \dots, a_{2100}) and (b1,b2,,b2100)(b_1, b_2, \dots, b_{2100}) satisfying
aigcd(ji,2100)=11j2100bj. a_i \equiv \sum_{\substack{\gcd(j-i, 2100)=1 \\ 1 \le j \le 2100}} b_j.
For integers ii from 11 to MM, take integers cic_i from 00 to 20992099 such that ci=j=09bi+Mjc_i = \sum_{j=0}^{9} b_{i+M j} holds. Then, for integers ll from 11 to 21002100, it follows that al=gcd(jl,M)=11jMcja_l = \sum_{\substack{\gcd(j-l, M)=1 \\ 1 \le j \le M}} c_j, and thus ai+kMaia_{i+kM} \equiv a_i holds for integers ii from 11 to MM and integers kk from 00 to 99. Conversely, for any tuple (c1,c2,,cM)(c_1, c_2, \dots, c_M) of integers from 00 to 20992099, if we take bib_i as {ci(1iM),0(M+1i2100)\begin{cases} c_i & (1 \le i \le M), \\ 0 & (M+1 \le i \le 2100) \end{cases}, then ci=j=09bi+Mjc_i = \sum_{j=0}^{9} b_{i+M j} (1iM1 \le i \le M) holds. Hence it suffices to find the number of tuples (a1,a2,,aM)(a_1, a_2, \dots, a_M) of integers from 00 to 20992099 that satisfy the following condition:

There exists some tuple (c1,c2,,cM)(c_1, c_2, \dots, c_M) of integers from 00 to 20992099 such that ai=gcd(ji,M)=11jMcja_i = \sum_{\substack{\gcd(j-i, M)=1 \\ 1 \le j \le M}} c_j holds for any integer ii from 11 to MM.

In the following, a tuple of MM integers from 00 to 20992099 is called a good tuple, and for simplicity, we write (Ai)(A_i) to represent a good tuple (A1,A2,,AM)(A_1, A_2, \dots, A_M). We also define that Ak+M=AkA_{k+M} = A_k for any good tuple (Ai)(A_i) and any positive integer kk. Additionally, ii will represent an integer from 11 to MM and g(i)g(i) will denote gcd(i,M)\gcd(i, M) hereinafter.

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

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

Proof of Lemma 1.
(1) Since mm and nn are coprime, g(mn)=g(m)g(n)g(mn) = g(m)g(n). Since g(m)g(m) and g(n)g(n) are also coprime, ω(g(m)g(n))=ω(g(m))+ω(g(n))\omega(g(m)g(n)) = \omega(g(m)) + \omega(g(n)). Therefore,
μ(mn)=(1)ω(g(mn))=(1)ω(g(m))+ω(g(n))=(1)ω(g(m))(1)ω(g(n))=μ(m)μ(n) \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=1n=1 is obvious. Assume n2n \ge 2. We write n=2e23e35e57e7n = 2^{e_2}3^{e_3}5^{e_5}7^{e_7} with e2,e3,e5,e7{0,1}e_2, e_3, e_5, e_7 \in \{0, 1\}. By property (1),
xnμ(x)=(0e2e1μ(2e2))(0e3e1μ(3e3))(0e5e1μ(5e5))(0e7e1μ(7e7)). \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 n2n \ge 2, we can take q{2,3,5,7}q \in \{2, 3, 5, 7\} with eq=1e_q = 1, which satisfies μ(q0)+μ(q1)=0\mu(q^0) + \mu(q^1) = 0.
Therefore, xnμ(x)=0\sum_{x|n} \mu(x) = 0 holds for n2n \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 (si)(s_i), there exists exactly one child.
(2) For any good tuple (si)(s_i), there exists exactly one good tuple whose inverse is (si)(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 (Si)(S_i) and (Ti)(T_i) are the parents of (si)(s_i) and (ti)(t_i), respectively, then (Si)=(Ti)(S_i) = (T_i) \Rightarrow (si)=(ti)(s_i) = (t_i).
Suppose otherwise, i.e., (Si)=(Ti)(S_i) = (T_i) and there exists an ii such that sitis_i \neq t_i. Without loss of generality, we can assume that ii is the smallest among such integers. Since gcd(g(i),Mg(i))=gcd(i,Mg(i))=1\gcd(g(i), \frac{M}{g(i)}) = \gcd(i, \frac{M}{g(i)}) = 1 and g(i)ig(i) \mid i, it holds for any integer jj that
g(i+Mg(i)j)=gcd(g(i)Mg(i),i+Mg(i)j)=gcd(g(i),i+Mg(i)j)gcd(Mg(i),i+Mg(i)j)=gcd(g(i),Mg(i)j)gcd(Mg(i),i)=gcd(g(i),j). \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 1jg(i)11 \le j \le g(i) - 1, g(i+Mg(i)j)<g(i)g\left(i + \frac{M}{g(i)}j\right) < g(i) and thus si+Mg(i)j=ti+Mg(i)js_{i+\frac{M}{g(i)}j} = t_{i+\frac{M}{g(i)}j} by the minimality of g(i)g(i). Hence,
siSij=1g(i)1si+Mg(i)jTij=1g(i)1ti+Mg(i)jti, 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 sitis_i \neq t_i.

(2) Similarly to (1), let (si)(s'_i) and (ti)(t'_i) be the inverses of (si)(s_i) and (ti)(t_i), respectively, and it suffices to show that (si)=(ti)(si)=(ti)(s'_i) = (t'_i) \Rightarrow (s_i) = (t_i).
Suppose (si)=(ti)(s'_i) = (t'_i) and there exists an ii such that sitis_i \neq t_i. Again, we can assume that ii is the smallest among such integers without loss of generality. Since g(i)Mg(i) \mid M, if 1jM1 \le j \le M and Mj(ji)M \mid j(j - i), then j2j(ji)0(modg(i))j^2 \equiv j(j - i) \equiv 0 \pmod{g(i)}. Since g(i)g(i) is square-free, we have g(i)jg(i) \mid j and thus g(i)g(j)g(i) \mid g(j). Noting that g(j)>g(i)sj=tjg(j) > g(i) \Rightarrow s_j = t_j from the maximality of g(i)g(i), si=tis'_i = t'_i means
Mj(ji),g(j)=g(i)1jMμ(j)sjMj(ji)1jMμ(j)sjMj(ji),g(j)>g(i)1jMμ(j)sjsiMj(ji),g(j)>g(i)1jMμ(j)sj=tiMj(ji),g(j)>g(i)1jMμ(j)tjMj(ji),g(j)=g(i)1jMμ(j)tj. \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, Mj(ji)M \mid j(j - i) implies M/g(j)(ji)M/g(j) \mid (j - i). Also, g(j)=g(i)g(j) = g(i) implies g(j)(ji)g(j) \mid (j - i). Since g(j)g(j) and M/g(j)M/g(j) are coprime, M/g(j)(ji)M/g(j) \mid (j - i) and g(j)(ji)g(j) \mid (j - i) mean j=ij = i under the condition 1jM1 \le j \le M. Hence the condition si=tis'_i = t'_i reduces to si=tis_i = t_i, which contradicts the assumption that sitis_i \ne t_i.
This concludes the proof of Lemma 2. ■

Lemma 3. Consider good tuples (ai)(a_i) and (ci)(c_i), with (Ai)(A_i) and (Ci)(C_i) being their parents respectively, and let (Ci)(C'_i) be the inverse of (Ci)(C_i). The following two conditions are equivalent:
(1) For every i, it holds that aigcd(ji,M)=11jMcj. (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 ii, it holds that Aiϕ(g(i))CiA_i \equiv \phi(g(i))C'_i, where ϕ(n)\phi(n) is Euler's totient function.

Proof of Lemma 3. (1)     \implies (2): Suppose that (1) holds. By definition of inversion, we have
CiMj(ji)1jMμ(j)CjMj(ji)k=0g(j)1μ(j)cj+Mg(j)k. 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 μ(j)=(1)ω(g(j))=(1)ω(g(g(j)))=μ(g(j))\mu(j) = (-1)^{\omega(g(j))} = (-1)^{\omega(g(g(j)))} = \mu(g(j)), we have
CiMj(ji)1jMk=0g(j)1μ(g(j))cj+Mg(j)k. 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)g(j), we have
CivMg(j)=vMj(ji)1jMv1μ(v)cj+Mvku=0M1vMk=0v1g(j)=vMj(ji)j+vki+u1jMμ(v)ci+u 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=Mvv' = \frac{M}{v}.
Thus, the right side can be written as u=0M1vMαi,u,vμ(v)ci+u\sum_{u=0}^{M-1} \sum_{v|M} \alpha_{i,u,v} \mu(v) c_{i+u}, where αi,u,v\alpha_{i,u,v} is the number of integer pairs (j,k)(j, k) satisfying 1jM,0k<v,g(j)=v,Mj(ji)1 \le j \le M, 0 \le k < v, g(j) = v, M | j(j-i), and j+vk=i+uj+v'k = i+u. We want to show that
αi,u,v={1(u0(modv) and gcd(i,v)=1),0(otherwise). \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 Mj(ji)M|j(j - i) and g(j)=vg(j) = v mean that M/v=v(ji)M/v = v' | (j - i). Hence, we have uj+vki0(modv)u \equiv j + v'k - i \equiv 0 \pmod{v'}. This yields αi,u,v=0\alpha_{i,u,v} = 0 for u0(modv)u \ne 0 \pmod{v'}. Also, when gcd(i,v)1\gcd(i, v') \ne 1, v(ji)v' | (j - i) implies gcd(j,v)1\gcd(j, v') \ne 1 and thus g(j)vg(j) \ne v. This yields αi,u,v=0\alpha_{i,u,v} = 0 for the case gcd(i,v)1\gcd(i, v') \ne 1.
We now consider the case u0(modv)u \equiv 0 \pmod{v'} and gcd(i,v)=1\gcd(i, v') = 1, and determine the number of pairs (j,k)(j, k) satisfying five conditions above. g(j)=vg(j) = v implies vjv | j, or j0(modv)j \equiv 0 \pmod{v}. On the other hand, j+vki+ui(modv)j + v'k \equiv i + u \equiv i \pmod{v'} since u0(modv)u \equiv 0 \pmod{v'}. Since vv and vv' are coprime, there exists unique jj (up to mod MM) that satisfies both congruences by the Chinese remainder theorem. Additionally, when jj is fixed, there is at most one kk that satisfies j+vki+uj + v'k \equiv i + u and 0k<v0 \le k < v. Hence, αi,u,v1\alpha_{i,u,v} \le 1 for this case.
On the other hand, Chinese remainder theorem assures that we can take jj such that 1jM,vj1 \le j \le M, v | j and v(ji)v' | (j - i) are satisfied. Moreover, since ji(modv)j \equiv i \pmod{v'} and u0(modv)u \equiv 0 \pmod{v'}, we can take kk such that 0k<v0 \le k < v and j+vki+uu(modv)j + v'k \equiv i + u \equiv u \pmod{v'} are satisfied. Since v(ji)v' | (j - i), it holds gcd(j,v)=gcd(i,v)=1\gcd(j, v') = \gcd(i, v') = 1. Together with vjv | j, we have g(j)=vg(j) = v. Since vjv | j and v(ji)v' | (j - i), it holds M=vvj(ji)M = vv' | j(j - i). This implies that we can construct the pair (j,k)(j, k) that satisfies all five conditions, and thus αi,u,v1\alpha_{i,u,v} \ge 1. This concludes that αi,u,v=1\alpha_{i,u,v} = 1 for u0(modv)u \equiv 0 \pmod{v'} and gcd(i,v)=1\gcd(i, v') = 1.
Note that u0(modv)u \equiv 0 \pmod{v'} is equivalent to Mg(u)v\frac{M}{g(u)} | v, and that gcd(i,v)=1\gcd(i, v') = 1 is equivalent to g(i)vg(i) | v, we have
vMαi,u,vμ(v)=vM,Mg(u)v,g(i)vμ(v) \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)wv = g(i)w, ww varies while satisfying wMg(i)w \mid \frac{M}{g(i)} and Mg(u)g(i)w\frac{M}{g(u)} | g(i)w. This is equivalent to wMg(i)w \mid \frac{M}{g(i)} and Mg(iu)w\frac{M}{g(iu)} | w, thus letting w=Mg(iu)xw = \frac{M}{g(iu)}x, xx varies over all positive divisors of g(iu)g(i)\frac{g(iu)}{g(i)}, and we have
μ(v)=μ(g(i)w)=μ(Mg(i)g(iu)x). \mu(v) = \mu(g(i)w) = \mu\left(\frac{Mg(i)}{g(iu)}x\right).
Since xx is a positive divisor of g(iu)g(i)\frac{g(iu)}{g(i)}, Mg(i)g(iu)\frac{Mg(i)}{g(iu)} and xx are coprime and thus
μ(Mg(i)g(iu)x)=μ(Mg(i)g(iu))μ(x) \mu\left(\frac{Mg(i)}{g(iu)}x\right) = \mu\left(\frac{Mg(i)}{g(iu)}\right) \mu(x)
holds.
Since g(iu)g(i)\frac{g(iu)}{g(i)} is a divisor of MM, according to Lemma 1(2), xg(iu)g(i)μ(x)\sum_{x|\frac{g(iu)}{g(i)}} \mu(x) is equal to 11 when g(iu)g(i)=1\frac{g(iu)}{g(i)} = 1 (i.e., g(u)g(i)g(u) | g(i)), and 00 otherwise. Furthermore, when g(u)g(i)g(u) | g(i), we have μ(Mg(i)g(iu))=μ(M)=1\mu\left(\frac{Mg(i)}{g(iu)}\right) = \mu(M) = 1. Hence
Ci=u=0M1μ(Mg(i)g(iu))xg(iu)g(i)μ(x)ci+u=g(u)g(i)0u<Mci+u. 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
Aij=0g(i)1ai+Mg(i)jj=0g(i)1k=11kMg(k)=1ci+Mg(i)j+k 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 ci+uc_{i+u} is the number of pairs of integers (j,k)(j, k) satisfying 0jg(i)10 \le j \le g(i) - 1, 1kM1 \le k \le M, Mg(i)j+ku\frac{M}{g(i)}j + k \equiv u, and g(k)=1g(k) = 1. This is the number of kk satisfying 1kM1 \le k \le M, ku(modMg(i))k \equiv u \pmod{\frac{M}{g(i)}} and g(k)=1g(k) = 1. Therefore, by the Chinese remainder theorem, the coefficient of ci+uc_{i+u} is 00 when gcd(u,Mg(i))>1\gcd(u, \frac{M}{g(i)}) > 1 (i.e., when g(u)g(i)g(u) \nmid g(i)), and ϕ(g(i))\phi(g(i)) otherwise (i.e., when g(u)g(i)g(u) | g(i)). Hence we have Aiϕ(g(i))g(u)g(i)0u<Mci+uϕ(g(i))CiA_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)    (1): Suppose that (2) holds. Define a good tuple (a~i) by a~igcd(ji,M)=11jMcj, and let (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}
(A~i)(\tilde{A}_i) be the parent of (a~i)(\tilde{a}_i). Since we have (Ai)=(A~i)(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 (Ai)(A_i) such that there exists some good tuple (Ci)(C'_i) for which Aiϕ(g(i))CiA_i \equiv \phi(g(i))C'_i holds for every ii. This number is equal to i=1M2100gcd(2100,ϕ(g(i)))\prod_{i=1}^{M} \frac{2100}{\gcd(2100, \phi(g(i)))}. Since ϕ(g(i))\phi(g(i)) is a divisor of ϕ(M)=48\phi(M) = 48, gcd(2100,ϕ(g(i)))\gcd(2100, \phi(g(i))) is a divisor of gcd(2100,48)=12\gcd(2100, 48) = 12.

* 2gcd(2100,ϕ(g(i)))2 \mid \gcd(2100, \phi(g(i))) is equivalent to claim that ii is a multiple of 33, 55, or 77, hence the number of such ii is 2(357246)=1142 \cdot (3 \cdot 5 \cdot 7 - 2 \cdot 4 \cdot 6) = 114.
* 4gcd(2100,ϕ(g(i)))4 \mid \gcd(2100, \phi(g(i))) is equivalent to claim that ii is a multiple of either 2121 or 55, hence the number of such ii is 2(215204)=502 \cdot (21 \cdot 5 - 20 \cdot 4) = 50.
* 3gcd(2100,ϕ(g(i)))3 \mid \gcd(2100, \phi(g(i))) is equivalent to claim that 7i7 \mid i, hence the number of such ii is 3030.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.