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

• https://cp-algorithms.com/algebra/module-inverse.html

This is calculated using EEA.

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
    cout << "No solution!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

MATH135

Inverses in ${\mathbb{Z}}_m$ (INV ${\mathbb{Z}}_m$)

Let $a$ be an integer with $1\le a\le m-1$. The element $[a]$ in ${\mathbb{Z}}_m$ has a multiplicative inverse if and only if $\gcd (a,m)=1$. Moreover, when $\gcd (a,m)=1$, the multiplicative inverse is unique.

Inverses in ${\mathbb{Z}}_p$ (INV ${\mathbb{Z}}_p$)

For all prime numbers $p$ and non-zero elements $[a]$ in ${\mathbb{Z}}_p$, the multiplicative inverse $[a{]}^{-1}$ exists and is unique.