+0

Number Theory

0
135
1

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
+9461
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