Euler’s Totient / Phi of $n$ calculates the number of units of a given number space $n$

1. Factorise n into its prime factors

eg. $\phi(18) = \phi(2) * \phi(3^2)
eg. $phi(4) = \phi(2^2) = 2^2 - 2^1 = 2$

2. Apply general formula

Where $a$ is a prime number, and $b$ the power.

$\phi(a^b) = a^b - a^{b-1}$

e.g.
$\phi(2) = 1$
$\phi(3) = 2$

Using Euler's totient

• When gcd(a,m) = 1; a^phi(m) === 1 mod m
• When gcd(a,prime) = 1; a^(prime-1) === 1 mod prime