Modular Arithmetic #

Identities #

\( b \) is inverse of \( a \) if:

\( a*b \ mod \ n = 1 \)

Find \( b \) using the Euclidean Algorithm.

\( a \) and \( b \) are relatively prime if:

\( gcd(a,b) = 1 \)

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) \)

\( x^k \ mod \ n = x^{k \ mod \ \phi(n) } \ mod \ n \)