+0  
 
0
67
1
avatar+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?

 Jun 3, 2023
 #1
avatar
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.

 Jun 5, 2023

0 Online Users