If $n \in Z^+$, how many possible values are there for $gcd(n,n+3000)$?

Question

I'm working my way through Grimaldi's textbook, and there's one exercise in the supplementary exercises for Chapter 4 that I don't understand how to approach.

Here is the problem: if $n \in Z^+$, how many possible values are there for $gcd(n,n+3000)$?

In case the notation $gcd(x,y)$ is not universal, it refers to the greatest common divisor of $x$ and $y$. I reviewed the teacher's solutions for an explanation for how to solve this problem, but it relies on the fact that $gcd(n,n+3000)$ is a divisor of $3000$, which I don't understand. Any help on either solving the problem or explaining why $gcd(n,n+3000)$ is a common divisor of $3000$ this would be greatly appreciated. Thank you!

Answer 1

There are exactly $\sigma_0(3000)=32$ values.

If $d$ is divisor of 3000, Then $d=\text{gcd}(d, d+3000)$. And by Euclidean algorithm, $\text{gcd}(d, d+3000)=\text{gcd}(d, 3000)$ is divisor of 3000.

Answer 2

Denote the greatest common divisor of x and y be (x,y), then $$(n,n+3000)=(n,3000)$$ Since $$ 3000=2^{3} \times 3 \times 5^{3} $$ Therefore there are at most $$(3+1)\times (1+1)\times (3+1)=32$$possible values for $gcd(n,n+3000)$.