Euclidean Algorithm Modified

The Euclidean algorithm makes repeated use of the fact that $\gcd(x,y)=\gcd(x+ty,y)$ , where $t$ is an integer. We can do the same here: $\begin{aligned} \gcd \left(a^3-2a^2+2021,a^2-3a+3 \right) &= \gcd \left(a^3-2a^2+2021 - a \times \left(a^2-3a+3 \right),a^2-3a+3 \right) \\ &=\gcd \left(a^2-3a+2021,a^2-3a+3 \right) \\ &=\gcd \left(2018,a^2-3a+3 \right) \end{aligned}$

Now, $2018=2 \times 1009$ ( $1009$ is prime). But $a^2-3a+3$ is always odd; so this $\gcd$ is either $1$ or $1009$ .

Are there any $a$ such that $1009$ divides $a^2-3a+3$ ? As it happens, yes: within the given range, all of $\{376,636,1385,1645\}$ are solutions (and these are the only ones in the range).

So the sum is $4 \times 1009 + 2016 \times 1 = \boxed{6052}$ .

$a^2 - 3a + 3$ must be odd number, and: $\\ a^3 - 2a^2 + 2021 = (a+1)(a^2 - 3a + 3) + 2 \times 1009 \\ \therefore gcd(a^3 - 2a^2 + 2021, a^2 - 3a + 3) = gcd(a^2 - 3a + 3, 1009)$

I guess $a^2 - 3a + 3$ and 1009 are coprime but not get proven yet.