math-eulers-theorem.html
* created: 2025-11-18T16:25
* modified: 2025-11-18T16:28
title
Eulers Theorem
description
Allow for the quick calculation for $a^b \mod p$.
Euler's 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
Euler's function
With n \in \mathbb{N}, then is:
\varphi(n) = | \{ x \in \{1,\ldots,n-1\} \;|\; \gcd(x,n) = 1 \}| = |\mathbb{Z}_n^*|
the order of \mathbb{Z}^{*}_{n}.