Given $S=\left\{n\in\mathbb{N}:nYesterday, 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.
 A: $|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.
A: We want to find out how many numbers $k$ there are in the list $1, 2, 3, \ldots, 81$ with the property $\gcd(k, 81) = 1$. This is the same as finding out how many numbers there are left when we remove the ones with the property $\gcd(k, 81) \neq 1$. You can see that $\gcd(k, 81) \neq 1$ if and only if $3$ divides $k$. Thus your answer is $81 - M$, where $M$ is the amount of numbers divisible by $3$ in the list. Then we notice that $M = \lfloor 81/3 \rfloor$, which gives you the correct solution $81 - \lfloor 81/3 \rfloor = 54$.
