Modular Arithmetic #
Identities #
Modular Inverse #
\( b \) is inverse of \( a \) if:
\[ a*b \ mod \ n = 1 \]Find \( b \) using the Euclidean Algorithm.
Relatively Prime #
\( a \) and \( b \) are relatively prime if:
\[ gcd(a,b) = 1 \]Totient #
Let
\[ Z_n^{*} = \{ \text{relatively prime numbers to n } \} \]Totient of n:
\[ \phi(n) = |Z_n^{*}| \]Also, if:
\[ n = p * q \]where \( p \) and \( q \) are prime, then:
\[ \phi(n) = (p-1)(q-1) \]