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

Guest Jun 16, 2021

#1**+1 **

Suppose p is the greatest common divisor of n and 3n+4. We will show that p would have to be a factor of 4 with possible values 1, 2, and 4.

We have n = kp, (1)

and 3n+4= mp, (2)

for some. integers k, and m.

We also know that k and m have no common factors other than 1 (they are relatively prime) because of p being the greatest of the common factors.

Substitute (1) in (2) to get

3(kp)+4 = mp (3)

Rearrange the terms in (3) to isolate the term '4' and factor out p:

4 = p(m - 3k) (4)

Equation (4) shows that we have factored 4 as p times some nonzero integer (m cannot equal to 3times k), which shows that

p is a factor of 4. But positive integer factors of 4 are only 1, 2, and 4. Sum of these numbers is 7.

Guest Jun 17, 2021