费马小定理的讲解视频——系统掌握数论核心定理的权威指南

k + (kᵖ - k)/p

群论法：乘法群的阶

考虑模p的剩余类乘法群 (ℤ/pℤ)×，其阶为p-1。任取元素a ≠ 0，其生成的循环子群阶d整除p-1（拉格朗日定理）。

因此aᵈ ≡ 1 (mod p)，进而aᵖ⁻¹ = (aᵈ)⁽ᵖ⁻¹⁾/ᵈ ≡ 1⁽⁽ᵖ⁻¹⁾/ᵈ⁾ = 1 (mod p)

乘以a得aᵖ ≡ a (mod p)

群论视角揭示了费马小定理的本质——群中元素阶的性质。这是费马小定理的讲解视频进阶内容，适合数学专业学生。

数学归纳法

对a进行归纳：

• 基础：a=1时，1ᵖ ≡ 1 (mod p) 显然成立
• 假设a=k时成立：kᵖ ≡ k (mod p)
• 证明a=k+1时：(k+1)ᵖ ≡ kᵖ + 1ᵖ (mod p)

由于二项式系数C(p,i)（0

(k+1)ᵖ = kᵖ + C(p,1)kᵖ⁻¹ + ... + C(p,p-1)k + 1 ≡ kᵖ + 1 (mod p)

由归纳假设，kᵖ ≡ k，故(k+1)ᵖ ≡ k + 1 (mod p)

此证明在费马小定理的讲解视频中逐行拆解，特别强调二项式系数的整除性。

项式定理法（费马原始思路）

费马考虑a² - 1 = (a-1)(a+1)的因子结构。推广到质数幂：

设a = mp + r（0 ≤ r < p），则aᵖ - a = (mp+r)ᵖ - (mp+r)

展开后，所有含p的项模p为0，仅剩rᵖ - r。因此只需证rᵖ ≡ r (mod p)（0 ≤ r < p）

当r=0时显然；当r≠0时，考虑集合{r, 2r, ..., (p-1)r}模p的余数恰好是{1,2,...,p-1}的排列

故r·2r·...·(p-1)r ≡ 1·2·...·(p-1) (mod p)

即rᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)

因(p-1)!与p互质，可约去得rᵖ⁻¹ ≡ 1 (mod p)

这是费马小定理的讲解视频中最具历史价值的证明，还原费马原始思维。

费马小定理的讲解视频：快速幂模板

// C++快速幂（模质数p）
long long mod_pow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b) {
        if (b & 1) res = res  a % p;
        a = a  a % p;
        b >>= 1;
    }
    return res;
}
// 求模逆元（p为质数）
long long mod_inv(long long a, long long p) {
    return mod_pow(a, p-2, p);
}

此模板在费马小定理的讲解视频中逐行讲解，适用于编程竞赛和工程实践。

费马小定理的讲解视频竞赛技巧

例：求100! mod 101

是质数，由威尔逊定理（费马小定理推论）：100! ≡ -1 (mod 101)

例：求C(1000,500) mod 1009（1009是质数）

预处理阶乘：fact[i] = i! mod 1009

预处理逆阶乘：inv_fact[i] = (i!)⁻¹ mod 1009 = (i!)¹⁰⁰⁷ mod 1009

C(1000,500) = fact[1000] × inv_fact[500] × inv_fact[500] mod 1009

费马小定理的讲解视频提供完整代码和优化技巧。