2164⋅3302100210
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 P1,P2,…,Pk, the notation ∑P1,P2,…,Pk represents the sum under the conditions where all of P1,P2,…,Pk 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∣2100 and p∣210 are equivalent, thus gcd(s,2100)=1 is equivalent to gcd(s,210)=1 for any integer s.
Consider tuples of integers (a1,a2,…,a2100) and (b1,b2,…,b2100) satisfying
ai≡gcd(j−i,2100)=11≤j≤2100∑bj.
For integers i from 1 to M, take integers ci from 0 to 2099 such that ci=∑j=09bi+Mj holds. Then, for integers l from 1 to 2100, it follows that al=∑gcd(j−l,M)=11≤j≤Mcj, and thus ai+kM≡ai holds for integers i from 1 to M and integers k from 0 to 9. Conversely, for any tuple (c1,c2,…,cM) of integers from 0 to 2099, if we take bi as {ci0(1≤i≤M),(M+1≤i≤2100), then ci=∑j=09bi+Mj (1≤i≤M) holds. Hence it suffices to find the number of tuples (a1,a2,…,aM) of integers from 0 to 2099 that satisfy the following condition:
There exists some tuple (c1,c2,…,cM) of integers from 0 to 2099 such that ai=∑gcd(j−i,M)=11≤j≤Mcj 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 (Ai) to represent a good tuple (A1,A2,…,AM). We also define that Ak+M=Ak for any good tuple (Ai) 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 (Si) and (si) satisfy the following condition, (Si) is called the parent of (si) and (si) is called a child of (Si), respectively:
Si=j=0∑g(i)−1si+g(i)Mj
Furthermore, a good tuple (si′) is called the inverse of (si) if they satisfy the following condition:
si′=M∣j(j−i)1≤j≤M∑μ(j)sj.
Here, ω(n) denotes the number of distinct prime factors of n, and μ(n) is defined by μ(n)=(−1)ω(g(n)).
Lemma 1. μ(n) satisfies the following two properties.
(1) For coprime positive integers m and n, μ(mn)=μ(m)μ(n).
(2) For a positive divisor n of M,
x∣n∑μ(x)={10(n=1),(n≥2).
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, ω(g(m)g(n))=ω(g(m))+ω(g(n)). Therefore,
μ(mn)=(−1)ω(g(mn))=(−1)ω(g(m))+ω(g(n))=(−1)ω(g(m))(−1)ω(g(n))=μ(m)μ(n)
follows.
(2) The case of n=1 is obvious. Assume n≥2. We write n=2e23e35e57e7 with e2,e3,e5,e7∈{0,1}. By property (1),
x∣n∑μ(x)=(0≤e2≤e1∑μ(2e2))(0≤e3≤e1∑μ(3e3))(0≤e5≤e1∑μ(5e5))(0≤e7≤e1∑μ(7e7)).
Since n≥2, we can take q∈{2,3,5,7} with eq=1, which satisfies μ(q0)+μ(q1)=0.
Therefore, ∑x∣nμ(x)=0 holds for n≥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), there exists exactly one child.
(2) For any good tuple (si), there exists exactly one good tuple whose inverse is (si).
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) and (Ti) are the parents of (si) and (ti), respectively, then (Si)=(Ti) ⇒ (si)=(ti).
Suppose otherwise, i.e., (Si)=(Ti) and there exists an i such that si=ti. Without loss of generality, we can assume that i is the smallest among such integers. Since gcd(g(i),g(i)M)=gcd(i,g(i)M)=1 and g(i)∣i, it holds for any integer j that
g(i+g(i)Mj)=gcd(g(i)⋅g(i)M,i+g(i)Mj)=gcd(g(i),i+g(i)Mj)gcd(g(i)M,i+g(i)Mj)=gcd(g(i),g(i)Mj)gcd(g(i)M,i)=gcd(g(i),j).
Therefore, for 1≤j≤g(i)−1, g(i+g(i)Mj)<g(i) and thus si+g(i)Mj=ti+g(i)Mj by the minimality of g(i). Hence,
si≡Si−j=1∑g(i)−1si+g(i)Mj≡Ti−j=1∑g(i)−1ti+g(i)Mj≡ti,
which contradicts the assumption that si=ti.
(2) Similarly to (1), let (si′) and (ti′) be the inverses of (si) and (ti), respectively, and it suffices to show that (si′)=(ti′)⇒(si)=(ti).
Suppose (si′)=(ti′) and there exists an i such that si=ti. Again, we can assume that i is the smallest among such integers without loss of generality. Since g(i)∣M, if 1≤j≤M and M∣j(j−i), then j2≡j(j−i)≡0(modg(i)). Since g(i) is square-free, we have g(i)∣j and thus g(i)∣g(j). Noting that g(j)>g(i)⇒sj=tj from the maximality of g(i), si′=ti′ means
M∣j(j−i),g(j)=g(i)1≤j≤M∑μ(j)sj≡M∣j(j−i)1≤j≤M∑μ(j)sj−M∣j(j−i),g(j)>g(i)1≤j≤M∑μ(j)sj≡si′−M∣j(j−i),g(j)>g(i)1≤j≤M∑μ(j)sj=ti′−M∣j(j−i),g(j)>g(i)1≤j≤M∑μ(j)tj≡M∣j(j−i),g(j)=g(i)1≤j≤M∑μ(j)tj.
Here, M∣j(j−i) implies M/g(j)∣(j−i). Also, g(j)=g(i) implies g(j)∣(j−i). Since g(j) and M/g(j) are coprime, M/g(j)∣(j−i) and g(j)∣(j−i) mean j=i under the condition 1≤j≤M. Hence the condition si′=ti′ reduces to si=ti, which contradicts the assumption that si=ti.
This concludes the proof of Lemma 2. ■
Lemma 3. Consider good tuples (ai) and (ci), with (Ai) and (Ci) being their parents respectively, and let (Ci′) be the inverse of (Ci). The following two conditions are equivalent:
(1) For every i, it holds that ai≡gcd(j−i,M)=11≤j≤M∑cj.
(2) For every i, it holds that Ai≡ϕ(g(i))Ci′, where ϕ(n) is Euler's totient function.
Proof of Lemma 3. (1) ⟹ (2): Suppose that (1) holds. By definition of inversion, we have
Ci′≡M∣j(j−i)1≤j≤M∑μ(j)Cj≡M∣j(j−i)∑k=0∑g(j)−1μ(j)cj+g(j)Mk.
Since μ(j)=(−1)ω(g(j))=(−1)ω(g(g(j)))=μ(g(j)), we have
Ci′≡M∣j(j−i)1≤j≤M∑k=0∑g(j)−1μ(g(j))cj+g(j)Mk.
Rearranging terms based on the values of g(j), we have
Ci′≡v∣M∑g(j)=vM∣j(j−i)∑1≤j≤M∑v−1μ(v)cj+vMk≡u=0∑M−1v∣M∑k=0∑v−1g(j)=vM∣j(j−i)j+v′k≡i+u1≤j≤M∑μ(v)ci+u
where v′=vM.
Thus, the right side can be written as ∑u=0M−1∑v∣Mαi,u,vμ(v)ci+u, where αi,u,v is the number of integer pairs (j,k) satisfying 1≤j≤M,0≤k<v,g(j)=v,M∣j(j−i), and j+v′k=i+u. We want to show that
αi,u,v={10(u≡0(modv′) and gcd(i,v′)=1),(otherwise).
holds.
Note that M∣j(j−i) and g(j)=v mean that M/v=v′∣(j−i). Hence, we have u≡j+v′k−i≡0(modv′). This yields αi,u,v=0 for u=0(modv′). Also, when gcd(i,v′)=1, v′∣(j−i) implies gcd(j,v′)=1 and thus g(j)=v. This yields αi,u,v=0 for the case gcd(i,v′)=1.
We now consider the case u≡0(modv′) 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≡0(modv). On the other hand, j+v′k≡i+u≡i(modv′) since u≡0(modv′). 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≡i+u and 0≤k<v. Hence, αi,u,v≤1 for this case.
On the other hand, Chinese remainder theorem assures that we can take j such that 1≤j≤M,v∣j and v′∣(j−i) are satisfied. Moreover, since j≡i(modv′) and u≡0(modv′), we can take k such that 0≤k<v and j+v′k≡i+u≡u(modv′) 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 αi,u,v≥1. This concludes that αi,u,v=1 for u≡0(modv′) and gcd(i,v′)=1.
Note that u≡0(modv′) is equivalent to g(u)M∣v, and that gcd(i,v′)=1 is equivalent to g(i)∣v, we have
v∣M∑αi,u,vμ(v)=v∣M,g(u)M∣v,g(i)∣v∑μ(v)
In this sum, if we let v=g(i)w, w varies while satisfying w∣g(i)M and g(u)M∣g(i)w. This is equivalent to w∣g(i)M and g(iu)M∣w, thus letting w=g(iu)Mx, x varies over all positive divisors of g(i)g(iu), and we have
μ(v)=μ(g(i)w)=μ(g(iu)Mg(i)x).
Since x is a positive divisor of g(i)g(iu), g(iu)Mg(i) and x are coprime and thus
μ(g(iu)Mg(i)x)=μ(g(iu)Mg(i))μ(x)
holds.
Since g(i)g(iu) is a divisor of M, according to Lemma 1(2), ∑x∣g(i)g(iu)μ(x) is equal to 1 when g(i)g(iu)=1 (i.e., g(u)∣g(i)), and 0 otherwise. Furthermore, when g(u)∣g(i), we have μ(g(iu)Mg(i))=μ(M)=1. Hence
Ci′=u=0∑M−1μ(g(iu)Mg(i))x∣g(i)g(iu)∑μ(x)ci+u=g(u)∣g(i)0≤u<M∑ci+u.
On the other hand, since we assume that (1) holds, we have
Ai≡j=0∑g(i)−1ai+g(i)Mj≡j=0∑g(i)−1k=11≤k≤M∑g(k)=1ci+g(i)Mj+k
and the coefficient of ci+u is the number of pairs of integers (j,k) satisfying 0≤j≤g(i)−1, 1≤k≤M, g(i)Mj+k≡u, and g(k)=1. This is the number of k satisfying 1≤k≤M, k≡u(modg(i)M) and g(k)=1. Therefore, by the Chinese remainder theorem, the coefficient of ci+u is 0 when gcd(u,g(i)M)>1 (i.e., when g(u)∤g(i)), and ϕ(g(i)) otherwise (i.e., when g(u)∣g(i)). Hence we have Ai≡ϕ(g(i))∑g(u)∣g(i)0≤u<Mci+u≡ϕ(g(i))Ci′, which concludes this part.
(2)⟹(1): Suppose that (2) holds. Define a good tuple (a~i) by a~i≡gcd(j−i,M)=11≤j≤M∑cj, and let
(A~i) be the parent of (a~i). Since we have (Ai)=(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) such that there exists some good tuple (Ci′) for which Ai≡ϕ(g(i))Ci′ holds for every i. This number is equal to ∏i=1Mgcd(2100,ϕ(g(i)))2100. Since ϕ(g(i)) is a divisor of ϕ(M)=48, gcd(2100,ϕ(g(i))) is a divisor of gcd(2100,48)=12.
* 2∣gcd(2100,ϕ(g(i))) is equivalent to claim that i is a multiple of 3, 5, or 7, hence the number of such i is 2⋅(3⋅5⋅7−2⋅4⋅6)=114.
* 4∣gcd(2100,ϕ(g(i))) is equivalent to claim that i is a multiple of either 21 or 5, hence the number of such i is 2⋅(21⋅5−20⋅4)=50.
* 3∣gcd(2100,ϕ(g(i))) is equivalent to claim that 7∣i, hence the number of such i is 30.
Thus, the answer is 2114+50⋅3302100M=2164⋅3302100210.