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.

Noter 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.

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. Then: 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 C2 = C1 + 1 because if the size is even then C1 must be equal to C2 otherwise C2 will be odd and will be equal to C1 + 1.

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

We can notice that because C2 is odd then C1 must be even. And therefore all terms in the two sums are divisible by 2 then the GCD will be >= 2 meaning that it will always be greater than 1.