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

 Jun 16, 2021

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.

 Jun 17, 2021

36 Online Users