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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.