Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a fast way , or a direct function to give the count of numbers less than $x$ and co-prime to $x$ . for example if $x$ = 3 ; then $n = 2$ and if $x$ = 8 ; then $n = 4$.

share|cite|improve this question
Euler's totient function – user2468 Aug 25 '12 at 14:28

4 Answers 4

up vote 4 down vote accepted

The relevant function is the Euler Totient function and the link contains several ways to compute it.

share|cite|improve this answer

Yes there is. First of all, you have to prime factorize your $x$, any put it in exponential form. Suppose you have the number $x = 50$. The prime factorization is $5^2 * 2^1$. Now take each number seperately. Take the bases and subtract 1 from all of them. $5-1=4$. $2-1=1$. Now evaluate the each base/exponent combination after subtracting the exponent by 1. $5^{2-1}=5$. $2^{1-1}=1$. Now multiply your answers. $(4)(1)(5)(1) = 20$.

If you want to try out your examples, $3=3^1$. So your answer would be $(3-1)(3^{1-1}) = (2)(1) = 2.$ For your other example, $8=2^3. n=(2-1)(2^{3-1})=(1)(4)=4$.

I guess in general, prime factorize your $x$ to $a_1^{b_1}*a_2^{b_2}* ... * a_n^{b_n}$ and your answer will be $((a_1-1)(a_1^{b_1-1}))*((a_2-1)(a_2^{b_2-1}))*...*(a_n-1)(a_n^{b_n-1})$

share|cite|improve this answer

You can also use the inclusion-exclusion principle. Example: $1001=7\cdot 11\cdot 13$ has three distinct prime factors, 7, 11, and 13. among numbers from 1 to 1001, there are $143=11\cdot 13$ multiples of 7, $91=7\cdot 13$ multiples of 11, $77=7\cdot 11$ multiples of 13, 13 multiples of 77, 11 multiples of 91, 7 multiples of 143, and 1 multiple of 1001. Therefore $\phi(1001)=1001-(143+91+77)+(13+11+7)-1=720$

share|cite|improve this answer

Here is a cool proof that I learnt on how to compute the Euler Totient Function $\varphi$ that uses probability theory. On one hand, $\varphi(x)/x$ is the probability that a number selected between $1$ and $x$ is coprime to $x$ while we can alternatively compute the probability as follows:

A number between $1$ and $x$ is coprime to $x$ iff it is coprime to each of its prime factors. Given a prime factor $p$ of $x$, the probability that a number selected between $1$ and $p$ is coprime to $p$ is


Since the events of selecting when a number is coprime to each prime factor are independent, we can multiply the probabilities together to get the total probability being $\prod_{p|x} (p-1)/p$. Equating this with the result before gives you the pretty formula

$$\varphi(x) = x\prod_{p|x} \frac{p-1}{p}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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