Function inv_mod

pub fn inv_mod(x: i64, m: i64) -> i64

Returns an integer $y \in [0, m)$ such that $xy \equiv 1 \pmod m$.

Constraints

• $\gcd(x, m) = 1$
• $1 \leq m$

Panics

Panics if the above constraints are not satisfied.

Complexity

• $O(\log m)$

Example

use ac_library::math;

assert_eq!(math::inv_mod(3, 7), 5);