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

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.

• Are you familiar with the totient function? – John Lou Nov 13 '17 at 3:48
• Are you really supposed to find all the values or merely the number of such values? – Randall Nov 13 '17 at 3:51
• @JohnLou No im not – Mark Dodds Nov 13 '17 at 3:54
• @Randall yes I only need the number of such values – Mark Dodds Nov 13 '17 at 3:54
• $e$ must be relatively prime to $10000$. Euler's totient function finds the number of numbers that are relatively prime to a given value. – John Lou Nov 13 '17 at 4:03

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.