本文是“一些”系列的最后一篇。

本文内容：费马小定理及其证明，【题目】因子和，裴蜀定理，德摩根定理，欧拉定理及其证明，威尔逊定理。

费马小定理及其证明

对于整数 $a$ 和质数 $p$ ，若 $(a,p)=1$ ，则有：

a^{p-1}\equiv1\pmod p

注： $(a,p)$ 指 $a$ 和 $p$ 的最大公约数。

证明如下。

#1

若 $a$ ， $b$ ， $c$ 为任意整数， $m$ 为正整数，且 $(m,c)=1$ ，则当 $ac\equiv bc \pmod m$ 时，有 $a\equiv b \pmod m$ 。就是说 $c$ 和 $m$ 互质就能约掉。

证明：

\begin{aligned} & ac\equiv bc \pmod m \\\\ \implies & m \mid c(a-b) \\\\ \implies & m \mid a-b \tag{1}\\\\ \implies & a\equiv b \pmod m \end{aligned}

$(1)$ ：因为 $(m,c)=1$ ，故 $m$ 和 $c$ 没有公因子。所以可以下推。

$\LaTeX$ ：

\begin{aligned}
& ac\equiv bc \pmod m \\\\
\implies & m \mid c(a-b) \\\\
\implies & m \mid a-b \tag{1}\\\\
\implies & a\equiv b \pmod m
\end{aligned}

#2

设 $m$ 是一个整数且 $m>1$ ， $b$ 是一个整数且 $(m,b)=1$ 。如果 $\{a_1,a_2,\dots,a_m\}$ 是模 $m$ 的一个完全剩余系，则 $\{ba_1,ba_2,\dots,ba_m\}$ 也构成模 $m$ 的一个完全剩余系。

证明：

假设 $i\not=j$ ，且 $(m,b)=1$ ， $ba_i\equiv ba_j\pmod m$ 。

根据引理 #1 则有 $a_i\equiv a_j\pmod m$ 。根据完全剩余系的定义可知这是不可能的，假设不成立。

#3

构造 $p$ 的完全剩余系：

P=\{0,1,\dots,p-1\}

因为 $(a,p)=1$ ，由 #2 可得：

A=\{0,a,\dots,a(p-1)\}

也是 $p$ 的完全剩余系。

$P$ 集合中的 $0$ 和 $A$ 集合中的 $0$ 对应，删去 $0$ 。则 $P$ 所有元素相乘和 $A$ 所有元素相乘对 $p$ 同余：

\begin{aligned} & 1\times2\times\dots\times(p-1)\equiv a\times2a\times\dots\times a(p-1)\pmod p \\\\ \implies & (p-1)!\equiv(p-1)!\times a^{p-1}\pmod p \\\\ \implies & 1\equiv a^{p-1}\pmod p \tag{2}\\\\ \end{aligned}

$(2)$ ：因为 $((p-1)!,p)=1$ ，故根据 #1 可以下推。

证毕。

【题目】因子和

输入两个整数 $a$ 和 $b$ ，求 $a^b$ 的因子和 $\bmod 9901$ 。 $1\le a\le5\times10^7$ ， $0 \leq b \leq 5 \times 10^7$ 。

$\LaTeX$ ：1\le a\le5\times10^7

解：

\begin{aligned} a^b &= (p_1^{c_1}p_2^{c_2}\dots p_k^{c_k})^b \tag{3} \\\\ &= p_1^{c_1b}p_2^{c_2b}\dots p_k^{c_kb} \\\\ ans &= \prod_{i=1}^{k} (1+p_i+p_i^2+\dots+p_i^{c_ib}) \bmod 9901 \\\\ &= \prod_{i=1}^{k} 1\times \dfrac{p_i^{c_ib}-1}{p_i-1} \bmod 9901 \tag{4} \end{aligned}

$(3)$ ：唯一分解。

$(4)$ ：等比数列求和。若对于第 $i$ 项， $p_i-1\equiv0\pmod p$ ，则 $p_i\equiv1\pmod p$ ，式子应为 $1\times(n+1)\bmod p$ 。否则仍是本式。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=10000000+10,mod=9901;
	ll a,b,k[N],p[N],cnt=0,ans=1;
	ll pow(ll a,ll b)
	{
		ll ret=1;
		while(b)
		{
			if(b%2==1) ret=ret*a%mod;
			b/=2; a=a*a%mod;
		}
		return ret;
	}
	ll inv(ll a)
	{
		return pow(a,mod-2);
	}
	ll getSum(ll a,ll q,ll n)
	{
		ll ret=a;
		ret=ret*pow(q,n)%mod;
		ret=((ret-a)%mod+mod)%mod;
		ret=ret*inv(q-1)%mod;
		return ret;
	}
	void factor()
	{
		ll n=a,tol;
		for(ll i=2;i<=n;i++)
		{
			if(n%i) continue;
			k[++cnt]=i; tol=0;
			while(n%i==0)
			{
				n/=i; tol++;
			}
			p[cnt]=tol*b;
		}
		if(n>1) {k[++cnt]=n;p[cnt]=b;}
		
		/*for(ll i=1;i<=cnt;i++)
		{
			printf("factor: %lld  num: %lld\n",k[i],p[i]);
		}*/
		return;
	}
	void main()
	{
		scanf("%lld%lld",&a,&b);
		factor();
		for(ll i=1;i<=cnt;i++)
		{
			if((k[i]-1)%mod==0) ans=(ans*(p[i]+1))%mod;
			else ans=(ans*getSum(1,k[i],p[i]+1))%mod;
			//printf("%lld\n",ans);
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

/*
Sum of DengBiShuLie

a + aq + aq^2 + ... + aq^(n-1) = Sn
aq + aq^2 + aq^3 + ... + aq^n = Sn*q
Sn + aq^n - a = Sn*q
Sn = (aq^n-a)/(q-1)
*/

/*
a=k1^p1+k2^p2+...+kn^pn
sum: (1+k1+k1^2+...+k1^p1)*...*(1+kn+kn^2+...+kn^pn)

a^b = sum^b = (1+k1^b+k1^2b+...+k1^p1b)*...*(1+kn^b+kn^2b+...+kn^pnb)

If 9901 | q-1 , then q=1 (mod 9901).
Then sum_i = pi+1.

Else use DBSL.
*/

裴蜀定理

$ax+by=c$ ， $a,b\in N^*,x,y,c\in Z$ 成立的充要条件是 $(a,b)\mid c$ 。

exgcd 求解的是方程 $ax+by=\gcd(a,b)$ 的一组解。

德摩根定理

设 $A_1,A_2,\dots,A_n$ 为有限集，则有：

\begin{aligned} |A_1\cup A_2\cup\dots\cup A_n| = &\sum_{i=1}^n |A_i|-\sum_{i=1}^n\sum_{j>i} |A_i\cap A_j| \\\\ &+\sum_{i=1}^n\sum_{j>i}\sum_{k>j} |A_i\cap A_j\cap A_k| \\\\ &-\dots+(-1)^{n-1}|A_1\cap A_2\cap\dots\cap A_n| \end{aligned}

欧拉定理及其证明

设 $m,a\in N^*$ ，且 $(a,m)=1$ ，则有：

a^{\varphi(m)}\equiv1\pmod m

$\LaTeX$ ：a^{\varphi(m)}\equiv1\pmod m

$\varphi(n)$ 是一个数论函数，表示在 $[1,n-1]$ 上与 $n$ 互质的整数的个数。如果 $p$ 是素数，显然 $\varphi(p)=p-1$ 。所以费马小定理是欧拉定理的一个特殊情况。

它反映了这样一个式子：

a^{b\text{ mod }\varphi(m)+k\varphi(m)}\equiv a^{b\text{ mod }\varphi(m)}\equiv a^b\pmod m

这个式子成立的条件是： $(a,m)=1$ 。

证明：

#1

若 $a\equiv b\pmod m$ ， $c\equiv d\pmod m$ ，则 $ac\equiv bd\pmod m$ 。

证明：

\begin{aligned} & a\equiv b\pmod m ,c\equiv d\pmod m \\\\ \implies & m \mid a-b,m \mid c-d \\\\ \implies & pm=a-b,qm=c-d\\\\ \implies & pm+b=a,qm+d=c\\\\ \implies & ac=(pm+b)(qm+d)\\\\ \implies & ac=pqm^2+pdm+qbm+bd\\\\ \implies & ac\equiv bd\pmod m \end{aligned}

#2

使用类似于证明费马小定理的方法，利用既约剩余系的概念证明即可。~~显然，易证，易得~~。

RSA 加密算法利用了此定理。

威尔逊定理

当且仅当 $p$ 为素数时， $(p-1)!\equiv-1\pmod p$ 。这里的 $!$ 表示阶乘。

补充：

若 $p=4$ ， $(p-1)!\bmod p=2$ 。
若 $p$ 为其他合数，则 $(p-1)!\bmod p=0$ .

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/ad8a55acd81a/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 数论一些唯一分解

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

一些数论证明或杂论-2