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?

supremecheetah Jun 3, 2023

#1**0 **

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.

Guest Jun 5, 2023