费马小定理

费马小定理是数论中的一个重要定理。

如果 p 是一个质数，而整数 a 不是 p 的倍数，则有 a^(p-1) ≡ 1 (mod p)。

简单来说，就是对于给定的质数 p 和与 p 互质的整数 a，a 的(p-1)次幂除以 p 的余数恒为 1。

费马小定理在密码学等领域有广泛的应用。例如，在一些加密算法中会利用到它的性质。

比如，当 p = 5，a = 2 时，2^(5-1) = 16，16 除以 5 的余数为 1，符合费马小定理。

逆元

逆元是指在某个运算中，一个元素与另一个元素的运算结果为单位元。在数学中，逆元是一个重要的概念，它在群论、环论、域论等领域中都有广泛的应用。

一般定义为：对于一个数$n$，$n$和其加法逆元（或称相反数）之和是加法单位（即零）。对于$n$，其加法逆元表示为$-n$。

在模运算中，逆元的概念也很重要。对于一个正整数$a$和一个素数$p$，如果存在一个整数$x$，使得$ax\equiv1\pmod{p}$，那么$x$就是$a$在模$p$下的逆元。

逆元的公式为：$a$的逆元为$a^{p-2}\pmod{p}$。

在实际应用中，求逆元的方法有很多种，其中比较常用的方法是扩展欧几里得算法和费马小定理。

费马小定理与逆元

利用费马小定理求逆元的基本思想如下：

当 p 为质数且 a 与 p 互质时，根据费马小定理有 a^(p-1) ≡ 1 (mod p)，将其变形可得 a * a^(p-2) ≡ 1 (mod p)，这里的 a^(p-2) 就可以看作 a 在模 p 下的逆元。

公式可以表示为：a 的逆元为 a^(p-2) (mod p)。

例如，在模 7 下，要求 3 的逆元，根据费马小定理，3^(7-1) ≡ 1 (mod 7)，即 3^6 ≡ 1 (mod 7)，那么 3 的逆元就是 3^5 = 243 ≡ 5 (mod 7)。