I'm working on the following exercise which appears in an old group theory exam I'm currently preparing for. I'm looking for a way to calculate this manually in an efficient way because no calculators or any electronic devices are allowed on the exam.
For how many elements $g\in\mathbb{Z}/270\mathbb{Z}$ do we have $\langle g\rangle\neq\mathbb{Z}/270\mathbb{Z}?$
So the way I see this, I have to calculate $\phi(270)$, where $\phi(\cdot)$ is the Euler totient function, because if an $x$ such that $x|270$ divides $g$, $\mathrm{order}(x)<270$, so $\langle g\rangle\neq\mathbb{Z}/270\mathbb{Z}$, and if $\gcd(g,270)=1$, $\mathrm{order}(x)=270$ and thus $\langle g\rangle=\mathbb{Z}/270\mathbb{Z}$.
I'm aware of the following formula for the Euler phi function: $$\phi(n)=n\prod_{p|n, \ p \ \textrm{prime}}\left(1-\frac1p\right),$$ however, since we did not cover this in this course, I don't think I would be allowed to use this here. Another formula that is covered in my course in Gauss's formula: $$\sum_{d|n}\phi(d)=n,$$ but this one does not to make the problem simpler.
I did it the following way: the prime factorization of $270$ is given by $2\cdot3^3\cdot5$ so if we are looking for the numbers that are coprime to $270$, we should look for numbers in $\{0,1,2,\ldots,269\}$ what are not divisible by $2,3$ and $5$. There are $270/2=135$ numbers in this set divisible by $2$, $270/3=90$ divisible by $3$, $270/5=54$ divisible by $5$, $270/6=45$ divisible by both $2$ and $3$, $270/10=27$ divisible by both $2$ and $5$, $270/15=18$ divisible by both $5$ and $3$ and there are $270/30=9$ numbers in this set divisible by $2$,$3$ and $5$. Thus, by the inclusion-exclusion principle: $$270-\phi(270)=135+90+54-45-27-18+9=198\iff\phi(270)=72,$$ which is confirmed by a calculator. So there are $198$ elements $g\in\mathbb{Z}/270\mathbb{Z}$ such that $\langle g\rangle\neq\mathbb{Z}/270\mathbb{Z}$.
My question: This method looks way to devious to me, since you can't earn many points for this question on the exam and also inclusion-exclusion, although really elementary, is not covered in this course. I think I'm missing something and that there is a simpler way to solve this. So do you know a quicker way to solve this question? Also in general, for large values $n$, how do we calculate $\phi(n)$ efficiently? Also, I'm aware of another thread on this site with essentially the same question but the solution uses $\phi(n)=n\prod_{p|n, \ p \ \textrm{prime}}\left(1-\frac1p\right),$ which I can't use here.
The Euler's Totient functions is multiplicative over relatively prime factors.
$$ \phi (270) = \phi (27) \phi (2)\phi (5)= (18)(1)(4)=72$$