For a natural number $n \in \mathbb{N}$ define Eulers totient function as

$$\phi(n) = \big \vert \left \{x \in \mathbb{N} \ \vert \ 0 < x \leq n, \ gcd(x,n) = 1 \right \} \ \big \vert.$$