How to find the number of coprime numbers to $100$?

Question

Is there a way to find the number of coprime numbers ($2$ digit numbers) to $100$ without writing them?

Answer 1

Use Euler's totient function $\phi(n).$

For a number $k$ such that , $$k = p_1^{a_1}p_2^{a_2}....p_n^{a_n}$$ $\phi(n) $ gives the total numbers which are coprime to $n$. $$\phi (n) = n\times\left(1-\frac1p_1\right)\times\left(1-\frac1p_2\right)...\times\left(1-\frac1p_n\right)$$

for $n = 100$ , we have $$\phi(100) =100 \left(1-\frac12\right)\left(1-\frac15\right)$$ $$ = 100 \times\frac12\times\frac45$$ $$\phi(100) = 40$$

Subtracting $1$ digit numbers , we have Number of Co-prime = $40-4 = 36$

Answer 2

To be relatively prome to $100$ it must be neither divisible by $5$ nor by $2$.

There are $10$ that are divisible by both $2$ and $5$ (that just means they are divisible by $10$)

There $40 = 50-10$ that are divisible by $2$ but not by $5$.

And there $10 =20 -10$ that are divisible by $5$ but not $2$.

And there are $x$ that are neither.

Adding those up we get that there are $10 + 40 + 10 + x=100$ numbers total.

So $x = 40$.

........

If you want to find the number of comprimes to $100$ that are less than $100$ that is called the Euler totient function $\phi(100)$.

A few handy results that I won't prove is that the function is multiplicative over relative prime numbers; that is if $n,m$ are coprime then $\phi(nm) =\phi(n)\phi(m)$ so $\phi(100) = \phi(4)\phi(25)$.

Another handy result is if $p$ is prime then $\phi(p) =p-1$ and $\phi(p^k)= (p-1)p^{k-1}$.

Combining these we get: If $n = p_1^{k_1}p_2^{k_1}....p_m^{k_m}$ where $p_i$ are prime $\phi(n) = (p_1-1)(p_2-1)...(p_m-1)p_1^{k_1-1}p_2^{k_1-1}....p_m^{k_m-1}$

So $\phi(100) =\phi(2^2)\phi(5^2) = (2-1)2^1(5-1)5^1 = 40$ (and $\phi(10^k) = 4*10^{k-1}$).

But if you want the number of all comprimes... that's infinite.

======