Find number of values for $e \in \mathbb Z$ such that $\gcd(e, 10000) = 1$, where $1<e<10000$

Question

I need to the number of values of $e \in \mathbb Z$ such that $\gcd(e, 10000) = 1$, where $1<e<10000$.

I have no idea where to even start.

Answer 1

The prime factorization of $10{,}000$ is $2^4*5^4$. So, if we consider the $10{,}000$ integers between $1$ and $10{,}000$ inclusively then we will want to remove all integers that have either a $2$ or a $5$ in their prime factorizations.

So, start with the $10{,}000$ integers. Remove half (the even integers in that range) and then remove $1/5$ of the remaining integers (remove those with $5$ as a factor).

This yields $10{,}000 \cdot (1-\frac{1}{2}) \cdot (1-\frac{1}{5}) = 4,000$ integers in $\{1, \cdots , 10{,}000\}$ that are relatively prime to $10{,}000$.

Edit: We do not want to include $1$ for a possibility of $e$ and so we remove this one possibility. This yields $4{,}000 - 1 = 3{,}999$ such integers.