Sums with gcd $\sum_{n=1}^{1009} \gcd(2n, 2020) - \sum_{n=0}^{1008} \gcd(2n+1, 2019)$

Question

The problem $\sum\limits_{n=1}^{1009} \gcd(2n, 2020) - \sum\limits_{n=0}^{1008} \gcd(2n+1, 2019)$, has stumped me for a while. I plugged it into Wolfram Alpha, and got a 4-digit number. However, I have seen no feasible solutions, as I tried casework bashing, by taking the prime factorization and playing with numbers. Can someone tell me if this has no nice way to solve it without calculus? If there is a nice way, may someone help me out?

Answer 1

I'll start with the first sum.

First, note that $2020 = 20\cdot 101$ and $101$ is prime. Thus as long as $2n$ is not a multiple of $101$, $\gcd(2n, 2020) = \gcd(2n, 20)$. It's easy to compute this GCD for $n$ from $1$ to $10$: $$ \begin{array}{c|cccccccccc} n&1&2&3&4&5&6&7&8&9&10\\ \gcd(2n,20)&2&4&2&4&10&4&2&4&2&20 \end{array} $$ Since the sum of these values is $54$ and they repeat with period $10$, the sum of $\gcd(2n,20)$ for $1 \le n \le 1009$ is $101\cdot 54 - 20 = 5434$ ($101$ repetitions, except $n=1010$ is left out).

It only remains to correct those terms where $n$ is a multiple of $101$; i.e., for $n = 101, 202, \ldots, 909$. In each case, the $\gcd(2n,2020)=101\gcd(2n,20)$, and these values of $n$, when reduced mod $10$, correspond to the first nine in the table. So the sum of $\gcd(2n,2020)$ for these nine values of $n$ is $101\cdot 34 = 3434$ while the sum of $\gcd(2n,20)$ for the same values was $34$. The difference is $3400$, which, added to the previous total, yields the final answer of $8834$.

For the second sum, the prime factorization of $2019$ is $3\cdot 673$. Thus $\gcd(2n+1,2019) = \gcd(2n+1,3)$ when $2n+1$ is not a multiple of $673$; for $0\le n\le 1008$, the only exception is when $2n+1=673$ (i.e., $n=336$). Here are the first few values, which repeat with period $3$: $$ \begin{array}{c|ccc} n&0&1&2\\ \gcd(2n+1,3)&1&3&1 \end{array} $$ Thus the sum of $\gcd(2n+1,3)$ for $0 \le n \le 1008$ is $336\cdot 5 + 1 = 1681$ ($336$ repetitions, plus $n=1008$). Correcting for the case $2n+1 = 673$ changes a $1$ to a $673$, so the final sum is $1681 + 672 = 2353$.

Finally, the difference between the two sums is $8834 - 2353 = 6481$.