+0

# Number Theory

0
231
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 n + 16?

Jun 7, 2021

#1
+288
+2

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

Jun 18, 2021

#1
+288
+2
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$.