Congruence and Modular Arithmetic

# Modular Multiplicative Inverse

## Competitive Programming

Needed to learn this after messing up this question https://codeforces.com/contest/2008/problem/F

Resources

This is calculated using EEA.

## MATH135

### Inverses in $Z_{m}$ (INV $Z_{m}$)

Let $a$ be an integer with $1≤a≤m−1$. The element $[a]$ in $Z_{m}$ has a multiplicative inverse if and only if $g(a,m)=1$. Moreover, when $g(a,m)=1$, the multiplicative inverse is unique.

### Inverses in $Z_{p}$ (INV $Z_{p}$)

For all prime numbers $p$ and non-zero elements $[a]$ in $Z_{p}$, the multiplicative inverse $[a]_{−1}$ exists and is unique.