+274 For all positive integers n, the nth triangular number T_n is defined as T_n = 1+2+3+...+n. What is the greatest possible value of the greatest common divisor of 4T_n and n-1?
Since gcd(a,b)=gcd(b,a−b), we can repeatedly apply this rule to get gcd(4Tn,n−1)=gcd(4Tn−(n−1),n−1)=gcd(3Tn,n−1)
Now, we can write Tn=2n(n+1). We can see that n−1 divides Tn, so gcd(3Tn,n−1)=gcd(3Tn/(n−1),n−1).
We can now apply the Euclidean algorithm to get gcd(3Tn/(n−1),n−1)=gcd(n−1,3Tn/(n−1)−(n−1))=gcd(n−1,2)
The greatest possible value of gcd(n−1,2) is 2, which occurs when n=3.
