Cubed GCD

(This problem was inspired by an AIME problem .)

Let $d_n = \gcd(a_n, a_{n + 1}).$ Since $\gcd(a, b) = \gcd(a, b - a),$ we have

$\begin{aligned} d_n &= \gcd(100 + n^3, 100 + (n + 1)^3) \\ &= \gcd(100 + n^3, (n + 1)^3 - n^3) \\ &= \gcd(100 + n^3, 3n^2 + 3n + 1). \\ \end{aligned}$

Because $3 \nmid 3n^2 + 3n + 1,$ we can multiply $100 + n^3$ by 3 without changing the value of the greatest common divisor: $d_n = \gcd(300 + 3n^3, 3n^2 + 3n + 1).$ Now, we apply the Euclidean Algorithm:

$\begin{aligned} d_n &= \gcd(300 + 3n^3, 3n^2 + 3n + 1) \\ &= \gcd(300 + 3n^3 - (n - 1)(3n^2 + 3n + 1), 3n^2 + 3n + 1) \\ &= \gcd(2n + 301, 3n^2 + 3n + 1). \end{aligned}$

Because $4 \nmid 2n + 301,$ we can multiply $3n^2 + 3n + 1$ by 4 and apply the Euclidean Algorithm again:

$\begin{aligned} d_n &= \gcd(2n + 301, 12n^2 + 12n + 4) \\ &= \gcd(2n + 301, 12n^2 + 12n + 4 - (6n - 897)(2n + 301)) \\ &= \gcd(2n + 301, 270001). \end{aligned}$

Thus, $D = 270001,$ and $N = \dfrac{270001 - 301}{2} = 134850,$ making our final answer $D + N \equiv 270001 + 134850 \equiv \boxed{851} \! \pmod{1000}.$

---

BONUS: What if instead of $a_n = 100 + n^3$ we had $a_n = C + n^3,$ where $C$ is an arbitrary positive integer? What are $D$ and $N$ in this case?