You're going to need to generalize!

$\text {Since } 10000 = 10^4 = 2^4 × 5^4 \text { , therefore exactly those integers will be}$

$\text {coprime to 10000, which are neither divisible by 2 nor divisible by 5. }$

Hence, we can get our sum S by applying PIE (the principle of inclusion-exclusion) and the sum of the arithmetic sequence formula:

$S = \frac { 10000×10001 }{ 2 } - 2 × \frac { 5000×5001 }{ 2 } - 5 × \frac { 2000×2001 }{ 2 } + 10 × \frac { 1000×1001 }{ 2 } =$

$= \boxed { 20000000 }$

Remarks:

1.) For the sake of simplicity, we summed the integers till 10000 (despite the question says < 10000), but we filtered the 10000 out (since it is not coprime to itself), so we got the correct result in the end.

2.) It is not necessary to generalise in order to solve a simple case like this (where we have no more than 2 prime factors). However, in cases where we have (more than) 3 prime factors, we might be better off by using Euler's Totient Function (see the solutions of Alex G and Zach Abueg regarding this).

Relevant wiki: Euler's Totient Function

The sum $S$ of all positive integers less than $n$ and relatively prime to $n$ is $\dfrac{n \phi (n)}{2} \ \forall \ n > 2$ .

Proof:

If $k \in \big \{1, \ldots , n - 1\big \}$ is relatively prime to $n$ , then so is $n - k$ , so the integers that are being summed up can be combined into $\dfrac{\phi (n)}{2}$ pairs whose members sum to $n$ . If $n > 2$ , $\dfrac n2$ is never relatively prime to $n$ , so we must have pairs $\big \{k, n - k \big \}$ .

Now, a number $n$ with prime factorization

$n = p_1^{q_1}p_2^{q_2} \cdots p_k^{q_k}$

will have

$\displaystyle \phi (n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$

positive integers less than $n$ that are relatively prime to $n$ . With that in mind, we solve for $n = 10^4$ .

$\displaystyle \begin{aligned} 10^4 & = 2^4 \times 5^4 \\ \implies \phi \left(10^4\right) & = 10^4 \left(1 - \frac 12\right)\left(1 - \frac 15\right) = 4 \times 10^3 \\ \implies S & = \frac{10^4 \times 4 \times 10^3}{2} = \boxed{2 \times 10^7} \end{aligned}$

I think the approach of @Zee Ell approach is best, but here is an alternative approach.

The numbers which are relatively prime to $10^4$ will satisfy:

$n \equiv 1,3,7,9 \pmod{10}.$

They will be of the forms:

$n = 10k+1, \quad 10k+3, \quad 10k+7, \quad 10k+9$

for some integer $k,$ $0\le k \le 999.$ Summing all of these integers gives:

$\begin{aligned} S &= \sum\limits_{k=0}^{999}(10k+1)+\sum\limits_{k=0}^{999}(10k+3)+\sum\limits_{k=0}^{999}(10k+7)+\sum\limits_{k=0}^{999}(10k+9) \\ &= \sum\limits_{k=0}^{999}(40k+20) \\ &= 40\left(\frac{999 \cdot 1000}{2}\right) + 20(1000) \\ &= \boxed{20000000} \end{aligned}$

To solve this problem, we find the general formula for the sum of positive integers less than $n$ which are relatively prime to $n$ .

Let $\text{gcd}(a,b)$ denote the greatest common divisor of two integers $a$ and $b$ .

From the wiki, we know that $\text{gcd}(c,d) =\text{gcd}(c,c-d)$ for integers $d < c$ .

In order to make the notation more manageable, let us consider the sequence of integers less than some number $n$ which are relatively prime to $n$ . Let us call this sequence $C$ , and let it be the sequence:

$c_0, c_1 , c_2, \ldots c_{\phi(n)-2} , c_{\phi(n)-1}$

Note that there are exactly $\phi(n)$ ( $\phi(n)$ is the totient function) integers in $C$ by the definition of the totient.

We are now trying to find a closed form for the sum $S$ :

$\sum_{i=0}^{\phi(n)-1} c_i$

By definition, $\text{gcd}(n,c_i) = 1$ for all $1 \leq i \leq \phi(n)-1$ (the definition of relatively prime integers). Also by definition, the sequence includes all integers $c < n$ such that $\text{gcd}(n,c) = 1$ . We know that $\text{gcd}(n,n-c_i)=\text{gcd}(n,c_i) =1$ and that $n-c_i < n$ , hence $n-c_i$ must be in the sequence $C$ . In fact, it must be true that $n-c_i = c_{\phi(n)-1-i}$ .

For a concrete example, consider $n=9$ . The sequence $C$ would be:

$1,2,4,5,7,8$

The sequence has length $6 = \phi(9)$ . It is apparent that $9-1 = 8$ , $9-2 = 7$ , $9-4 = 5$ , $9-5 = 4$ , $9-7 = 2$ , $9-8 = 1$ , which is equivalent to saying that $n-c_i = c_{\phi(n)-1-i}$ for all $c_i$ in $C$ .

We now rewrite $C$ as

$c_0, c_1, c_2 \ldots n-c_2, n-c_1, n-c_0$

We can now rewrite $S$ as:

$S = \sum_{i=0}^{\phi(n)} c_i = c_0+c_1+c_2 + \ldots + n-c_2 + n-c_1 + n-c_0 = c_0 -c_0 + c_1 - c_1 + c_2 -c_2 + \ldots + n + n = n + \ldots + n$

Where $n$ is repeated exactly $\dfrac{\phi(n)}{2}$ times. Hence,

$S = \dfrac{n\phi(n)}{2}$

Substituting $n=10^4$ ,

$\dfrac{10^4 \cdot \phi(10^4)}{2} = \dfrac{10^4 \cdot 4000}{2} = 2 \cdot 10^7$

$10000=2^{4}\times 5^{4}$

We are going to going to get the desired sum by subtracting sum of integers less than $10000$ divisible by $2$ or $5$ from sum of first $9999$ integers.

It is easy to calculate the sum of first $9999$ integers: $\sum_{k=1}^{9999}k=\frac{9999\times 10000}{2}=9999\times 5000$ .

Next, sum of all even numbers less then 10000:

$\sum =2+4+6+8+...+9998=2(1+2+3+4+...+4999)=2\times \frac{4999\times 5000}{2}=5000\times 4999$ .

Then, sum of all numbers divisible by $5$ minus all even numbers in this group equals:

$\sum =\underbrace{5+15+25+35+...+9995}_{1000}=\frac{(5+9995)\times 1000}{2}=1000\times 5000$

${\color{cyan} \text{(note that there are 1999 numbers divisible by 5 less than 10000, and that 999 of them are even)}}$

Hence, desired sum is:

$9999\times 5000 - 4999\times 5000 - 1000\times 5000=5000(9999-4999-1000)=5000\times 4000=\boxed{20,000,000}$

I solve this by a much simpler way

I first find what numbers are relatively prime to 10000 between 1 to 10 included

I find that 1,3,7,9 are relatively prime to 10000

then I concluded that every even number and also with last digit 5 or 0 are and only not relatively prime to 10000.

It is because, $10000=2^4 \times 5^4$

every even number has a factor 2, and every number with last digit 5 has a factor 5, and also every number with a last digit 0 has a factor 10, so these number aren't relatively prime to 10000.

so along the first four number , I get 11,13,17,19 and 21,23,27,29 and so on, until 9991,9993,9997,9999.

I add it up by summation

$\frac{1000}{2}(1+9991+3+9993+7+9997+9+9999)=\boxed{2 \times 10^7}$

• Thanks to @Agnishom Chattopadhyay for the correction.

Since the factors of 10^4 are 2^4 and 5^4, The numbers relatively prime to 10^4 must be multiples of 2 or 5. We can see that any even number is a multiple of two so instead we can just find the sum of all positive odd integers less than 10^4 and remove any divisible by 5. Those that are divisible by 5 are the ones ending in 5. Thus, our answer can be Sum of Odd Numbers - Sum of Odd Numbers Ending in 5 This becomes $\frac{5000X10000}{2}$ - $\frac{1000X10000}{2}$ = 25000000-5000000 which gives a answer of 20000000

Notes: The equation was from the rule that a+(a+k)+(a+2k).....+(a+nk)= $\frac{(a+a+nk)*(n+1)}{2}$

5000 was the number of odd numbers less than 10^4 and 10000 was (1+9999)

1000 was the number of odd numbers less than 10^4 ending in 5 and 10000 was (5+9995)

As @Zee Ell pointed out we are looking for the sum of numbers below 10⁴ which are not multiples of 2 or 5. We can first add all the odd numbers below 10⁴, and then substract the odd multiples of 5 to get our answer.

As we are interested in the numbers smaller than 10⁴, the last even number we need to consider is 9999, which is the 5000th odd number (x is the $\frac{x+1}{2}$ th odd number). The sum of the first n odd numbers is n² so we get 5000²=25×10⁶. We then need to substract the odd multiples of 5 from that (5+15+25+35...). We can factor out the 5 so we end up with 5(1+3+5+7...) which is 5 times the sum of odd numbers... up to $\frac{9995}{5}$ =1999, which is the 1000th odd number. So 5× that sum is 5×1000²=5×10⁶. Substract, and we end up with 20×10⁶, or 2×10⁷

General solution

Consider the general case: given a positive integer $N > 2$ , how much is $\sum_{1 \leq d < N,\ (N,d)=1} d\ ?$ The answer is $\frac 12 \phi(N) N,$ where $\phi$ is the Euler totient function.

Here , $\phi(10^4) = 10^3\cdot \phi(10) = 10^3 \cdot \phi(2)\cdot \phi(5) = 10^3\cdot 1\cdot 4 = 4\times 10^3,$ so that the answer is $\frac 12\cdot 4\times 10^3 \cdot 10^4 = 2\cdot 10^7 = \boxed{20\,000\,000}.$

---

Proof

Observe that if $(N,d) = 1$ then $(N-d,d) = 1$ . (Also, $N$ and $N-d$ are distinct numbers in this case; the only exception would be $d = N/2$ but then $(N,d) = N/2 > 1$ .)

Thus the values to be added come in pairs, and the sum of each pair is $d + (N-d) = N$ . The number of pairs is half the number of values to be added; and the number of values to be added is $\phi(N)$ . This immediately gives $\text{(number of pairs)}\cdot \text{(sum of each pair)} = \frac12\phi(N)\cdot N.$

This seemingly tedious chore can be done in two simple steps using two sums of consecutive odd numbers.

$10^4$ = $2^4$ x $5^4$

Every number less than 10,000 that is not relatively prime has a factor of 2 or 5. Those numbers consist of the even numbers and odd multiples of 5.

The problem can be solved directly by summing the odd numbers and subtracting the sum of the odd multiples of 5, both using the fact that the sums of consecutive odd numbers are perfect squares.

There are 5000 positive odd integers less than 10,000. The sum of those is $5000^2$ = 25,000,000.

All that is necessary is to subtract the odd multiples of 5 to get the answer.

The odd multiples of 5, 5 + 15 + ,,, + 9995 = 5 x ( 1+ 3 +...+ 1999 ). Again a sum of consecutive odd numbers.

There are 1000 odd multiples of 5 less than $10^4$ so 1+ 3 +...+ 1999 = 1000^2 = 1,000,000

The sum of the odd multiples of 5 less than $10^4$ is 5 x 1,000,000 = 5,000,000

The solution is 25,000,000 - 5,000,000 = 20,000,000

This was a simple problem. The only numbers NOT coprime with 10,000 are the odd integers with the exception of those divisible by 5. So sum all the odd numbers from 1 to 9999. Then sum all numbers 5+15+25+.....+9995 and subtract the second sum from the first.