# Problem 2. (3 points)

Find the sum of natural numbers from 1 to 3000 inclusive that have common divisors with the number 3000, greater than 1.
# Answer: 3301500

## Solution:

$3000=2^{3} \cdot 3 \cdot 5^{3}$, so we are interested in numbers divisible by 2, 3, or 5. First, let's find the number of such numbers. For this, we will use the principle of inclusion and exclusion. There are exactly $\frac{3000}{2}=1500$ even numbers from 1 to 3000, $\frac{3000}{3}=1000$ numbers divisible by 3, and $\frac{3000}{5}=600$ numbers divisible by 5. However, if we simply add the numbers 1500, 1000, and 600, we will count some numbers twice, specifically, numbers divisible by $2 \cdot 3=6$, $2 \cdot 5=10$, and $3 \cdot 5=15$. Therefore, we need to subtract $\frac{3000}{6}=500$, $\frac{3000}{10}=300$, and $\frac{3000}{15}=200$ from the sum. However, $1500+1000+600-500-300-200=2100$ is still incorrect. Since in this expression, numbers that have all three prime factors are counted three times and then subtracted three times, we need to add these numbers again. The number of such numbers is $\frac{3000}{2 \cdot 3 \cdot 5}=100$, so the number of numbers that have common divisors with 3000 and do not exceed it is 2200.

Notice now that if a number $x$ has common divisors with a number $N$, then the number $N-x$ also has the same common divisors with $N$. Therefore, all the numbers of interest, except for the numbers 1500 and 3000, can be paired with a sum of 3000 (the number 3000 would have to be paired with 0, and the number 1500 with itself). There are 1099 such pairs, so the final answer is $1099 \cdot 3000 + 3000 + 1500 = 1100 \cdot 3000 + 1500 = 3301500$.

Note: Numbers less than 3000 and coprime with it can also be paired in the same way, so participants familiar with Euler's function could derive the formula for the answer as $\frac{N(N+1)-N \cdot \varphi(N)}{2}$.