+0  
 
0
42
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$?

 Jun 16, 2021
 #1
avatar
+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

13 Online Users

avatar