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$?
The GCD of two numbers is the largest positive integer that divides both numbers evenly. The division algorithm says that for any two positive integers $a$ and $b$, there exist unique integers $q$ and $r$ such that $a = bq + r$ and $0 \leq r < b$. The Euclidean algorithm uses the fact that the GCD of $a$ and $b$ is the same as the GCD of $b$ and $r$, since $r$ is the remainder when $a$ is divided by $b$. So, to find the GCD of $3n+4$ and $n$, I can apply the division algorithm and write $3n+4 = nq + r$, where $q$ and $r$ are some integers. Then, the GCD of $3n+4$ and $n$ is the same as the GCD of $n$ and $r$. Since $r$ is the remainder when $3n+4$ is divided by $n$, it must be less than $n$. For example, if $q=2$, then $nq = 2n$ and $r = 3n+4 - 2n = n+4$. This is not a valid choice of $r$, since it is larger than $n$. If $q=3$, then $nq = 3n$ and $r = 3n+4 - 3n = 4$. This is a valid choice of $r$, since it is less than $n$. So, one possible pair of values for $q$ and $r$ is $(3,4)$. This means that the GCD of $3n+4$ and $n$ is the same as the GCD of $n$ and $4$. This depends on the value of $n$. If $n$ is even, then the GCD of $n$ and $4$ is either $2$ or $4$, depending on whether $n$ is divisible by $4$. If $n$ is odd, then the GCD of $n$ and $4$ is $1$, since $4$ is even and $n$ is not. So, the GCD of $3n+4$ and $n$ can only take three possible values: $1$, $2$, or $4$. The question asks for the sum of all possible values of the GCD. So, I just need to add up these three values and get $1+2+4 = 7$. 