+0

0
91
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\$?

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.

Jun 17, 2021