Eulers Theorem

\forall a,b,n \in \mathbb{N} with \gcd(a,n) = 1 the following holds:

a^{b} \mod n = a^{b \mod \varphi(n)} \mod n

Eulers phi function \varphi(n)

Is used to calculate the magnitude of \mathbb{Z}_{n}^{*}. With n \in \mathbb{N}:

\varphi(n) = | \{ x \in \{1,\ldots,n-1\} \;|\; \gcd(x,n) = 1 \}| = |\mathbb{Z}_n^*|

With p, q \in \mathbb{P}, p \neq q, n = p \cdot q the following holds: \varphi(n)=(p-1)(q-1)