For each $n\in\mathbb{N}$ let $d_n$ denote the gcd of $n$ and $(2019-n)$. Find value of $d_1+d_2+\cdots d_{2018}+d_{2019}$
solution: $(2019-n,n)=(n,2019)$.So we have to find $(2019,1)+(2019,2)+\cdots (2019,2019)$.Now since $2019=3\cdot 673$.So its easy to obtain $6725$ ig.
This is not my solution. But how can I prove it formally?
Note that $(n , 2019 - n) = (2019, 2019 - n)$. A simple check gives that $673 \times 3 = 2019$ is the prime factorization of $2019$. Let $L = \sum_{1}^{2019} (2019,i)$.
Once you have this, we notice that only four possible gcds are possible. We break it up : let $S_m = |\{1 \leq n \leq 2019 : (2019 , n) = m\}|$. Then we get $$ L = 2019S_{2019} + 673S_{673} + 3S_3 + S_1 $$
We now note that all the $S_i$ are sizes of disjoint sets which total to $2019$. With this information, it is trivial to see that $S_{2019} = 1$.
We can explicitly calculate members of $S_{673} $ and $ S_3$. Show yourself that $S_{673} = \{1,...,2019\} \cap \{ 673 | x , x \neq 2019\}$ like how you usually show containment of sets (and find a similar expression for $S_3$). It is now obvious that $S_{673} = 2 , S_3 = 672$, from which you find $|S_1|$ and finish.