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