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.