Monthly Archives: February 2016

Greatest common divisor of two consequetive triangle numbers

Posted on by

0

Currently thinking of simple problems which showcase how the Euclidean algorithm can be applied to deducing more theoretical results. It’s a largely abandoned algorithm in the Swedish primary and secondary educational systems and I suspect it’s mostly because it is a)hard to teach other than out of habit and b) the computational skill of students is too unreliable for them to work enough problems in a short enough time for it to be taugh within a few classes. (and c) it’s not as useful as other things like elementary geometry)

The problem which I’m going to review here was just inspired by the pretty well known result that two consecutive Fibonacci numbers are relatively prime where a proof by the Euclidean algorithm is delightfully elegant but once you’ve shown that one in an educational setting I only think it fair to have available some problems showcasing the same method and which are of equivalent difficulty.

Finding the greatest common divisor of two triangle numbers only superficially applies the Euclidean algorithm and its division into two cases makes it necessary to identify the two cases first.

The two distinctive cases are when the index of the largest of two consecutive triangle numbers is even and the other when it is odd. A triangle number being alternately defined by

T_{n} = 1 + 2 + 3 + ... + n = \cfrac{n(n + 1)}{2}\qquad \text{or} \qquad T_{n} = T_{n-1} + n.

Case 1. The larger one has an odd index. T_{2n}, T_{2n +1}. Applying the Euclidean algorithm we have

T_{2n + 1} = T_{2n} + 2n + 1

T_{2n} = 2n(2n + 1)/2 = n(2n + 1) + 0

After two steps we get that the greatest common divisor was 2n + 1 and we summarize

\boxed{\gcd(T_{2n}, T_{2n + 1}) = 2n + 1}

Case 2: The larger one has an even index. T_{2n-1}, T_{2n} Applying the Euclidean algorithm again we have

T_{2n} = T_{2n-1} + 2n

T_{2n-1} = (2n-1)2n/2 = (2n-1)n = (n - 1)2n + n

(n -1)2n = 2n + 0

and we have thus found that if the larger triangle number has an even index then the greatest common divisor is n.

\boxed{\gcd(T_{2n-1}, T_{2n}) = n}