Is the greatest common divisor of n^2+1000 and (n+1)^2+1000 always 1?

Nice work by Mary and Falzoon! (I hope I'm not jumping in too soon.) For those who prefer algebra to bulk arithmetic, here is a classical approach. Apply the Euclidean Algorithm! (For those not familiar with that technique, I've inserted considerable explanation between the essential 3 lines of the proof.)

Any divisor of both [n²+1000] and [(n+1)²+1000] must also divide:

   [(n+1)²+1000] - [n²+1000] = [2n+1]

and similarly, any divisor of both [2n+1] and [n²+1000] also divides [(n+1)²+1000] = [2n+1] + [n²+1000], as well as:

   2 [n²+1000] - n [2n+1] = [2000 - n]

Hence, unless "n" is even, any common divisor of [2n+1] and [2000 - n] is also a common divisor of the original two numbers and any common divisor of the original two numbers must (regardless of the parity of "n") be a common divisor of:

   2 [2000 - n] + [2n+1] = 4001

Which is prime. The desired GCD must divide 4001, and hence is either 1 (like the given examples) or is 4001. In the later case we have that 4001 divides [2000-n], which is so if and only if n=2000+4001k for some integer k.

The GCD is 4001 if n=2000, 6001, 10002, 14003, ... and is 1 otherwise.

Simple excel function will find it.

Column A with 1 to 1000, simple fill!

Column B function =A1^2+1000

Column C function =(A1+1)^2+1000

Column C function =GCD(B1,C1)

n=1 to 1999, GCD=1 , Since you have asked for n=1 to 1000, then answer is yes. ALWAYS 1.//

n=2000, GCD=4001. this is the first GCD other than 1.

I will try how mathematically prove this.

Smallest counter-example is n = 2000 with GCD = 4001.

Others are n = 6001, n = 10002, n = 14003, etc. with the same GCD.

Looks like the pattern for n is (2000 + 4001*k) for k = 0, 1, 2, 3, ...,

all with GCD = 4001. That is surprising. Now how to prove it?