+0  
 
0
53
1
avatar

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

Best Answer 

 #1
avatar+287 
+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
avatar+287 
+2
Best Answer

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

Bginner Jun 18, 2021

8 Online Users