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?
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.