费马小定理
描述
若(p)为素数,(ain Z),则有(a^pequiv apmod p)。如果(p mid a),则有(a^{p-1}equiv 1pmod p)。
证明
费马小定理的证法有很多,此处介绍3种
证法一
摘自:《初等数论》 冯志刚 著,有改动
此处用归纳法证明。
当(a=1)时,原命题显然成立。
设(a=n)时命题成立,即(n^pequiv npmod p),故(n^p-nequiv 0pmod p)。
考虑二项式系数(C^k_p=frac{p!}{k!(p-k)!}),若(k)不为(p)或(0),由于分子有质数(p),但分母不含(p),故分子的(p)能保留,不被约分而除去,即(C^k_p)恒为(p)的倍数。
故有
所以对于任意(ain N_+),有(pmid (a^p-a)),故有(a^pequiv apmod p)。
证法二
摘自: Wikipedia,有改动
与证法一类似,先证明当(p)是质数时(C^k_p)恒为(p)的倍数。
然后就可以得到
当(b=a-1)时,可得(a^pequiv apmod p)
证法三
摘自:Matrix67的博客
首先我们证明这样一个结论:如果(p)是一个素数的话,那么对任意一个小于(p)的正整数(a),(a, 2a, 3a,cdots, (p-1)a)除以(p)的余数正好是一个(1)到(p-1)的排列。
假如结论不成立的话,那么就是说有两个小于(p)的正整数(m)和(n)使得(na)和(ma)除以(p)的余数相同。不妨假设(n>m),则(p)可以整除(a(n-m))。由于(p)是素数,那么(a)和(n-m)中至少有一个含有因子(p)。这显然是不可能的,因为(a)和(n-m)都比(p)小。
故:
也即:
两边同时除以((p-1)!),就得到了我们的最终结论:
应用
例题:LJJ算数
题目描述
LJJ刚上完了一节课!这节课是数学课!他知道了加减属于一级运算,乘除属于二级运算,幂则属于三级运算,而幂的优先级>乘除的优先级>加减的优先级(这是几年级的数学课)。但是,从上一套试卷+上一题中,我们知道了LJJ是一个总是突发奇想并且智商不够的人(也就是说他又想出一个问题给你咯)。他发明了一种四级运算,我们姑且用符号#来表示(找不到别的符号了)。我们知道(a imes b=a+a+a+cdots+a)(加b次),(a^b=a imes a imes a imes a imes cdots imes a)(乘b次),则(a#b=((((a^a)^a)^a)^ cdots )^a)(进行幂运算b次),自然,#的优先级比幂的优先级高。那么,LJJ就请你来帮他求(a#b mod {1000000007})咯。
输入格式:
输入仅1行,即(a,b)。
输出格式:
输出仅1行,即(a#b mod 1000000007)。
输入输出样例
输入样例#1:
3 5
输出样例#1:
968803245
说明
首先说明,样例答案不mod其实是4.4342648824303776994824963061915e+38(来自出题人的恶意)
然后,数据范围:
对于20%的数据,(ale1000,ble1000)
对于50%的数据,(ale 10^{16},ble 10000)
对于100%的数据,(ale 10^{16},ble 10^{16})
题解
由费马小定理,得
由此递归式,易知
于是用两次快速幂+取模即可。
代码
#include <cstdio>
typedef long long LL;
inline LL pow_mod(LL a, LL b, LL mod)//快速幂模板
{
a %= mod;
LL ans = 1;
for(; b; b >>= 1,a *= a,a %= mod)
if(b & 1)
ans = ans*a%mod;
return ans%mod;
}
const LL mod = 1e9+7;
int main()
{
LL a,b;
scanf("%lld%lld", &a, &b);
printf("%lld", pow_mod(a, pow_mod(a, b-1, mod-1), mod));
return 0;
}
求数论倒数
数论倒数也称为模倒数,或者模逆元。若(abequiv 1pmod p),则称(b)是(a)的数论倒数,亦可写作(a^{-1}equiv bpmod p)。
若(p)是素数,则(a^{p-1}=a imes a^{p-2}equiv 1pmod p),故(a^{-1}equiv a^{p-2}pmod p)。
但要注意前提条件是(p)是素数。
欧拉定理
同余类、剩余系、欧拉函数
对于任意整数,我们将它模(n),结果必定为(0)到(n-1)的整数之一。那么,我们可以把所有模(n)后同余的数看成一个集合,那么我们就把整数分成了(n)个集合,我们把这样的模(n)同余的所有整数组成的集合(即上述中的任意一个集合)称为同余类,标记为({overline {a}}_{n}),假若从上下文知道模(n),则也可标记为([a])。
那么,模(n)的同余类有(n)个,我们如何表示它们呢?和并查集的思想一样:任取集合中的一个数作为集合的代表元素。我们所取的那个元素就被称为该同余类的代表数。显然,同余类中的每个元素都可以作为该同余类的代表数。
剩余系指的是模(n)同余类的代表数集合。一个完全剩余系(完系)指的是模(n)的全部同余类的代表数的集合。例如,模(3)有三个同余类([0],[1],[2]),其完系可以是({9,12+1,15+2})。如果该集合是由每个同余类的最小非负整数所组成,亦即$ {0,1,2,...,n-1}(,则称该集合为模)n(的**非负最小完全剩余系**。模)n(完整余数系统中,与模)n(互质的代表数所构成的集合,称为模)n$的简化剩余系(简系)。
与(m)互素的所有模(m)的同余类的个数记为(varphi(n)),通常称为欧拉函数。显然,(varphi(n))等于(1,2,cdots,m)中与(m)互素的个数。
若((a,m)=1),而(a_1,a_2,cdots,a_{varphi(m)})构成模(m)的一个简系,则我们可以证明(aa_1,aa_2,cdots,aa_{varphi(m)})也是模(m)的简系。
欧拉定理
若((a,n)=1),则(a^{varphi(n)}equiv 1pmod n)。(这里(nin N_+,ain Z))
证明
设(a_1,a_2,cdots,a_{varphi(n)})是模(n)的简系,则由((a,m)=1),可知(aa_1,aa_2,cdots,aa_{varphi(n)})也是模(n)的简系。因此,$$prod^{varphi(n)}{i=1}a_iequiv prod^{varphi(n)}{i=1}aa_ipmod n,$$即$$mmid (prod{varphi(n)}_{i=1}a_i)(a{varphi(n)}-1).$$又因为((a_i,m)=1),故$$a^{varphi(n)}equiv 1pmod n.$$
就先写到这儿吧,欧拉定理的应用以后再说。
参考资料
Wikipedia
主要参考了:
《初等数论》 冯志刚 著
主要参考了:
2.2 同余类与剩余系
2.3 费马小定理与欧拉定理