费马小定理

描述

若$p$为素数，$a\in Z$，则有$a^p\equiv a\pmod p$。如果$p\nmid a$，则有$a^{p-1}\equiv 1\pmod p$。

证明

费马小定理的证法有很多，此处介绍3种

证法一

摘自：《初等数论》冯志刚著，有改动

此处用归纳法证明。

当$a=1$时，原命题显然成立。

设$a=n$时命题成立，即$n^p\equiv n\pmod p$，故$n^p-n\equiv 0\pmod p$。

考虑二项式系数$C^k_p=\frac{p!}{k!(p-k)!}$，若$k$不为$p$或$0$，由于分子有质数$p$，但分母不含$p$，故分子的$p$能保留，不被约分而除去，即$C^k_p$恒为$p$的倍数。

故有

\[(n+1)^p-(n+1)=n^p+C^1_pn^{p-1}+\cdots+C^{p-1}_pn-n\equiv n^p-n\equiv 0\pmod p
\]

所以对于任意$a\in N_+$，有$p\mid (a^p-a)$，故有$a^p\equiv a\pmod p$。

证法二

摘自： Wikipedia，有改动

与证法一类似，先证明当$p$是质数时$C^k_p$恒为$p$的倍数。

然后就可以得到

\[(b+1)^p\equiv b^p+1\equiv (b-1)^p+1+1 \equiv (b-1)^{p}+1+1\equiv (b-2)^{p}+1+1+1\equiv (b-2)^{p}+1+1+1\equiv (b-3)^{p}+1+1+1+1\equiv (b-3)^{p}+1+1+1+1\equiv \dots\equiv {\begin{matrix}\underbrace {1+1+\dots +1+1}\\b+1\end{matrix}}\equiv b+1\pmod p
\]

当$b=a-1$时，可得$a^p\equiv a\pmod 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)!\equiv a\times 2a\times 3a\times\cdots\times (p-1)a\pmod p
\]

也即：

\[(p-1)! ≡ (p-1)! * a^{p-1}\pmod p
\]

两边同时除以$(p-1)!$，就得到了我们的最终结论：

\[1 ≡ a^{p-1}\pmod p
\]

应用

例题：LJJ算数

原题链接

在我的洛谷博客上查看

题目描述

LJJ刚上完了一节课！这节课是数学课！他知道了加减属于一级运算，乘除属于二级运算，幂则属于三级运算，而幂的优先级>乘除的优先级>加减的优先级（这是几年级的数学课）。但是，从上一套试卷+上一题中，我们知道了LJJ是一个总是突发奇想并且智商不够的人（也就是说他又想出一个问题给你咯）。他发明了一种四级运算，我们姑且用符号#来表示（找不到别的符号了）。我们知道$a\times b=a+a+a+\cdots+a$（加b次），$a^b=a\times a\times a\times a\times \cdots \times 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%的数据，$a\le1000,b\le1000$

对于50%的数据，$a\le 10^{16},b\le 10000$

对于100%的数据，$a\le 10^{16},b\le 10^{16}$

题解

由费马小定理，得

\[a^k\equiv \frac{a^k}{a^{p-1}}=a^{k-(p-1)}\pmod p
\]

由此递归式，易知

\[a\# b=((((a)^a)^a)\cdots)^a=a^{a^{b-1}}\equiv a^{a^{b-1}\mod {p-1}}\pmod p
\]

于是用两次快速幂+取模即可。

代码

#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;

}

求数论倒数

数论倒数也称为模倒数，或者模逆元。若$ab\equiv 1\pmod p$，则称$b$是$a$的数论倒数，亦可写作$a^{-1}\equiv b\pmod p$。

若$p$是素数，则$a^{p-1}=a\times a^{p-2}\equiv 1\pmod 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 1\pmod n$。（这里$n\in N_+,a\in 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_i\equiv \prod^{\varphi(n)}{i=1}aa_i\pmod n,$$即$$m\mid (\prod^{{\varphi(n)}_{i=1}a_i)(a}{\varphi(n)}-1).$$又因为$(a_i,m)=1$，故$$a^{\varphi(n)}\equiv 1\pmod n.$$

就先写到这儿吧，欧拉定理的应用以后再说。

参考资料

Wikipedia

主要参考了：

Fermat's little theorem

Euler's theorem

同余

《初等数论》冯志刚著

主要参考了：

2.2 同余类与剩余系

2.3 费马小定理与欧拉定理

巴特西

学习：费马小定理 & 欧拉定理

费马小定理

描述

证明

证法一

证法二

证法三

应用

例题：LJJ算数

题目描述

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

说明

题解

代码

求数论倒数

欧拉定理

同余类、剩余系、欧拉函数

欧拉定理

证明

参考资料

Wikipedia

《初等数论》冯志刚著

Matrix67的博客——数论部分第一节：素数与素性测试

最新文章

热门文章

巴特西

学习：费马小定理 & 欧拉定理

费马小定理

描述

证明

证法一

证法二

证法三

应用

例题：LJJ算数

题目描述

输入格式：

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

说明

题解

代码

求数论倒数

欧拉定理

同余类、剩余系、欧拉函数

欧拉定理

证明

参考资料

Wikipedia

《初等数论》 冯志刚 著

Matrix67的博客——数论部分第一节：素数与素性测试

最新文章

热门文章

《初等数论》冯志刚著