If $n \in Z^+$, how many possible values are there for $gcd(n,n+3000)$?
Solution 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.
Solution 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)$.