A proof that the GCD(even sum, odd sum) > 1 for a consecutive set of integers.

Правка en11, от Banda., 2023-08-22 21:03:55

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.

Теги math, number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский Banda. 2023-08-22 21:03:55 10 Tiny change: 'lways > 1.\n\n\n\n\n' -> 'lways > 1.'
en10 Английский Banda. 2022-11-11 18:01:34 344
en9 Английский Banda. 2022-11-11 06:40:19 0 (published)
en8 Английский Banda. 2022-11-11 06:39:42 2 Tiny change: '^2 - C1`\n`sum of ' -> '^2 - C1`\n\n`sum of '
en7 Английский Banda. 2022-11-11 06:39:12 5 Tiny change: 'our set.\nThen:\n`sum of ' -> 'our set.\n\n`sum of '
en6 Английский Banda. 2022-11-11 06:38:37 44
en5 Английский Banda. 2022-11-11 06:37:18 1 Tiny change: 'n\n**Note: **\nA spec' -> 'n\n**Note:**\nA spec'
en4 Английский Banda. 2022-11-11 06:37:09 2 Tiny change: '\n\n**Note**\nA spec' -> '\n\n**Note:**\nA spec'
en3 Английский Banda. 2022-11-11 06:36:53 27
en2 Английский Banda. 2022-11-11 06:35:30 53
en1 Английский Banda. 2022-11-11 06:34:38 1752 Initial revision (saved to drafts)