乘法逆元

定义

证明

由于b与m互质，根据欧拉定理，有b``φ(m)``≡ 1 (mod m)
b * b``φ(m) - 1 ``≡ 1 (mod m)
故b模m的乘法逆元是b``φ(m) - 1

1. m为质数 费马小定理

φ(m) = m - 1
b``-1`` = b``(m - 2)``(mod m)

1. m不为质数

b-1 = b``φ(m) - 1 ``(mod m)

用途

在除数b与m互质的情况下，用于将一个mod m条件下的除法转换成乘法

求解

例题

快速幂求逆元

876. 快速幂求逆元

给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1之间的逆元。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。
输出格式
输出共 n 行，每组数据输出一个结果，每个结果占一行。
若 ai 模 pi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int a = sc.nextInt(), p = sc.nextInt();
            if (a % p == 0) System.out.println("impossible");
            else System.out.println(qmi(a, p-2, p));
        }
    }
    static int qmi(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return (int) res;
    }
}

此题不存在逆元的情况只有a是p的倍数时才不存在 因为p是质数，gcd(a, p) != 1只有在 a % p == 0 情况下才成立，此时 gcd(a, p) == p

扩展欧几里得算法求逆元

扩展欧几里得算法求逆元

结论：
已知x与m互质，x关于m的乘法逆元为y，x * y % m = 1
则有xk关于m的乘法逆元为yk
证明：
因为x * y % m = 1
所以(x * y)k % m = 1，即xk * yk % m = 1