As n ranges over the positive integers, what is the sum of all possible values of the greatest common divisor of 3n + 4 and n + 16?
+287 We can write 44 as a linear combination of $3n+4$ and $n+16$ like this
44=−(3n+4)+3(n+16)
so 44 must be a multiple of $\gcd(3n+4, n+16)$. Since $44=2^2\cdot 11$, so $\gcd(3n+4, n+16)$ can only be one of 1, 2, 4, 11, 22, and 44. I'll show in the following table that any of these six numbers can actually be the gcd of $3n+4$ and $n+16$ for some positive integer $n$.
n3n+4n+16gcd(3n+4,n+16)1717121018241620417553311622222228884444
Thus, the answer is $1+2+4+11+22+44=84$.
+287 We can write 44 as a linear combination of $3n+4$ and $n+16$ like this
44=−(3n+4)+3(n+16)
so 44 must be a multiple of $\gcd(3n+4, n+16)$. Since $44=2^2\cdot 11$, so $\gcd(3n+4, n+16)$ can only be one of 1, 2, 4, 11, 22, and 44. I'll show in the following table that any of these six numbers can actually be the gcd of $3n+4$ and $n+16$ for some positive integer $n$.
n3n+4n+16gcd(3n+4,n+16)1717121018241620417553311622222228884444
Thus, the answer is $1+2+4+11+22+44=84$.
