Hello Codeforces,

This is mathematical proof that the GCD between the sum of even indices and the sum of odd indices of a consecutive set of integers is always greater than one.

Note: A special case for this problem is when the size of the set is <= 2 then the GCD will be equal to 1, So I assume that the given set size is greater than 2.

And also We assume X >= 1.

First let's define our problem:

Given a consecutive set of integers: X, X + 1, X + 2, X + 3,.....

We want to prove that if we took the sum of the even indices (assuming zero-based indexing): sumOfEven = X + X + 2 +.... And took the sum of the odd indices: sum of odd = X + 1 + X + 3 +...

Then GCD(sum of even, sum of odd) > 1 always.

So let's assume C1 will be the number of even indices in our set and C2 will be the number of odd indices in our set.

sum of even = C1*X + C1*(C1 - 1) = C1*X + C1^2 - C1

sum of odd = C2*X + C2^2

Now we have two cases:

First if C1 = C2:

sum of even = C1*X + C1^2 - C1 = C1(X + C1 - 1)

sum of odd = C1*X + C1^2 = C1(X + C1)

We can notice that the GCD will be C1 and since the size of the set size is > 2 then C1 >= 2, the GCD will always be greater than one.

Second if C1 != C2:

Then we can notice that C1 = C2 + 1 because if the size is even then C1 must be equal to C2 otherwise C1 will be odd and will be equal to C2 + 1.

sum of even = C1(X + C1 - 1)

sum of odd = (C1 - 1)(X + C1 - 1)

We can notice that both of the sums are divisible by X + C1 - 1 then we know that the GCD will be at least X + C1 - 1 and because if C1 != C2 and the size of the set is > 2 then C1 >= 2 and because X >= 1 then X + C1 - 1 >= 2 which implies that GCD between the two sums will be always > 1.