# 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$?

$|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.

• I feel very, very silly all the sudden. I did hear him mention that function near the end of class, but I was so engrossed with figuring out the above problem that I did not pay close attention. Thank you very much. Commented Feb 21, 2012 at 15:22
• @JosuéMolina I have edited a bit. Hope you find it useful
– user21436
Commented Feb 21, 2012 at 15:25

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$.

• +1 This is the proof of the last result I have mentioned in my answer.
– user21436
Commented Feb 21, 2012 at 15:30