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$.
\[\begin{array}{cccc}
n & 3n+4 & n+16 & \gcd(3n+4, n+16) \\ \hline
1 & 7 & 17 & 1 \\
2 & 10 & 18 & 2 \\
4 & 16 & 20 & 4 \\
17 & 55 & 33 & 11 \\
6 & 22 & 22 & 22 \\
28 & 88 & 44 & 44
\end{array}\]
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$.
\[\begin{array}{cccc}
n & 3n+4 & n+16 & \gcd(3n+4, n+16) \\ \hline
1 & 7 & 17 & 1 \\
2 & 10 & 18 & 2 \\
4 & 16 & 20 & 4 \\
17 & 55 & 33 & 11 \\
6 & 22 & 22 & 22 \\
28 & 88 & 44 & 44
\end{array}\]
Thus, the answer is $1+2+4+11+22+44=84$.
