费马小定理与乘法逆元

费马小定理与乘法逆元

引言

在算法竞赛中，模运算下的除法操作无法直接进行，而乘法逆元是解决这一问题的核心工具。费马小定理作为数论中的经典结论，是质数模场景下求解逆元的最优方法之一。本文将从定理推导、逆元定义、代码实现到实战例题，讲解费马小定理与乘法逆元的应用，并补充扩展欧几里得逆元求解方法。

一、费马小定理

1. 定理内容

费马小定理是数论中针对质数模运算的核心结论，为逆元求解提供了理论基础。

2. 核心推论

• 互质性简化：因 ( p ) 是质数，所有小于 ( p ) 的正整数 ( a ) 必然满足 ( gcd(a, p) = 1 )，即质数模下非零数均符合费马小定理条件。
• 证明思路（二项式定理）：
  

3. 应用场景

费马小定理在竞赛中最核心的应用是质数模下的乘法逆元求解，是处理模除法的首选方法。

二、乘法逆元

1. 定义

模运算中无直接除法，需通过逆元实现“除法等效”：

3. 代码实现（快速幂）

计算 ( a^{p-2} mod p ) 需用快速幂（时间复杂度 ( O(log p) )），避免大数直接计算溢出：

// Java 快速幂+逆元模板
public class Main {
public static long 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 res;
}

// 求a在模p下的逆元（p为质数）
public static long inv(long a, long p) {
return qmi(a, p – 2, p);
}
}

三、实战例题：求模 ( 10^9+7 ) 下的逆元

1. 题目描述

给定正整数 ( N )，求其在模 ( 10^9+7 ) 下的乘法逆元。

2. 解题思路

3. Java 参考代码

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long p = (long) 1e9 + 7; // 竞赛常用质数模
int t = scan.nextInt();
while (t— > 0) {
long a = scan.nextLong();
long res = qim(a, p – 2, p);
System.out.println(res);
}
}

// 快速幂模板（兼容大数）
public static long qim(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 res;
}
}

四、扩展：竞赛常用逆元求解方法合集

1. 费马小定理求逆元（优化版）

理论推导

工业级Java模板（含异常处理）

/**
* 费马小定理求逆元（模数p必须是质数）
* @param a 待求逆元的数
* @param p 模数（质数）
* @return a在模p下的逆元，无逆元返回-1
*/
public class FermatInverse {
// 快速幂核心函数（防溢出）
private static long qmi(long a, long b, long p) {
long res = 1;
a = a % p; // 预处理：先取模避免大数溢出
while (b > 0) {
if ((b & 1) == 1) {
res = (res * a) % p;
}
a = (a * a) % p;
b >>= 1;
}
return res;
}

// 费马小定理求逆元（含互质校验）
public static long fermatInv(long a, long p) {
if (gcd(a, p) != 1) {
return –1; // 无逆元（a与p不互质）
}
return qmi(a, p – 2, p);
}

// 辅助：欧几里得算法求最大公约数
private static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}

// 测试示例
public static void main(String[] args) {
long a = 2, p = 1000000007;
long inv = fermatInv(a, p);
System.out.println(inv); // 输出：500000004
}
}

2. 扩展欧几里得算法求逆元

理论推导

Java模板

/**
* 扩展欧几里得算法求逆元（p无需是质数）
*/
public class ExtGcdInverse {
// 扩展欧几里得核心函数（题目指定实现）
// 返回值：[gcd(a,b), x, y] 满足 a*x + b*y = gcd(a,b)
private static int[] extendGcd(int a, int b) {
if (b == 0) return new int[]{a, 1, 0}; // 边界条件
int[] res = extendGcd(b, a % b);
// 反向推导解：gcd = b*x' + (a%b)*y' = a*y' + b*(x' – a/b*y')
return new int[]{res[0], res[2], res[1] – (a / b) * res[2]};
}

// 扩展欧几里得求逆元（int范围）
public static int extGcdInv(int a, int p) {
int[] res = extendGcd(a, p);
int gcd = res[0];
int x = res[1];

if (gcd != 1) {
return –1; // 无逆元
}
// 调整x为正整数
return (x % p + p) % p;
}

// 扩展：long类型（竞赛常用，避免溢出）
private static long[] extendGcdLong(long a, long b) {
if (b == 0) return new long[]{a, 1, 0};
long[] res = extendGcdLong(b, a % b);
return new long[]{res[0], res[2], res[1] – (a / b) * res[2]};
}

public static long extGcdInvLong(long a, long p) {
long[] res = extendGcdLong(a, p);
long gcd = res[0];
long x = res[1];
if (gcd != 1) {
return –1;
}
return (x % p + p) % p;
}

// 测试示例
public static void main(String[] args) {
// int范围测试
int a1 = 3, p1 = 7;
int inv1 = extGcdInv(a1, p1);
System.out.println(inv1); // 输出：5

// long范围测试（竞赛场景）
long a2 = 5, p2 = 1000000007;
long inv2 = extGcdInvLong(a2, p2);
System.out.println(inv2); // 输出：400000003
}
}

五、总结

1. 核心要点

2. 选型建议

3. 避坑指南

• 费马小定理仅适用于质数模，非质数模需切换扩展欧几里得；
• 逆元求解前需校验 ( gcd(a,p)=1 )，否则逆元不存在；
• 大数运算需全程取模，避免溢出（Java优先用long类型）。