+0  
 
0
80
1
avatar

As n ranges over the positive integers, what is the sum of all possible values of the greatest common divisor of 3n+4 and 7n+15?

 May 13, 2022
 #1
avatar+9459 
0

We use Euclidean algorithm to simplify \(\gcd(3n + 4, 7n + 15)\).

 

\(\quad \gcd(3n + 4, 7n + 15)\\ = \gcd(3n+4, n + 7)\\ = \gcd(-17, n + 7)\\ = \gcd(n + 7, 17)\)

 

If x is an integer, \(\gcd(x, 17)\) can only be either 1 or 17. That means the sum of all possible values required is 1 + 17 = 18.

 May 14, 2022

21 Online Users

avatar