Given $S=\left\{n\in\mathbb{N}:n<N\text{ and }\gcd(n,N)=1\right\}$, what is $\left|S\right|$? Yesterday, in our modern algebra lecture, our professor asked us to find the number of positive integers $n<81$, such that $\gcd(n,81)=1$. Intuitively, I realized that I had to find the number of prime factorization combinations that satisfy $2^{i}\cdot3^{0}\cdot5^{j}\cdot7^{k}<81$. Unfortunately, I was not able to accomplish much. I tried utilizing some of the concepts that I have been learning in my number theory class, such as the $\sigma$ and $\tau$ functions, to no avail. Moreover, the way he solved it was by noticing that $81=3^4$. He then proceeded to perform the next calculation, which is still recondite to me: $81-\left \lfloor 81/3 \right \rfloor=81-27=54$. Is this correct? And if so, why is this true? And how can I apply this 'procedure' to $12=2^2\cdot3$? Thanks in advance.

$|S|$ is the definition of Euler's Totient Function.

> Define $CP_n:=\\{n>N \in \mathbb N \mid GCD(n,N)=1 \\}$.
>
> Euler's Totient function $\phi$ is a function $\phi: \mathbb N \to \mathbb N$ such that $n \mapsto |CP_n|$. In words, $\phi (n)$ is the number of numbers less than and co-prime to $n$.

I'll recollect some properties here:

> * $\phi(p)=p-1 \iff p$ is a prime number.
> * For co-prime integers, $a$ and $b$, $\phi(ab)=\phi(a)\phi(b)$. That is, $\phi$ is multiplicative.
> * $\phi(p^k)=p^{k-1}(p-1)$ for prime $p$.
>


For proofs, please go through the Wikipedia page. In particular, the last equality is very helpful to solve your problem.