初等数论学习笔记

发表于 更新于 本文字数： 3.7k 阅读时长 ≈ 13 分钟

这个 PPT 里面前半部分内容更完善

由于时间紧迫，本文不会太详细，并且由于 OI 不重视证明，本文很多时候可能只给出证明链接。

定理太多证明太难怎么办？证什么，背结论即可

欧几里得算法

小学数学，直接跳过

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)

扩展欧几里得算法

即 exgcd，常用于求 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 的一组可行解。

首先，当 a,ba,b 不全为 00，ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 一定有解，证明见后面的裴蜀定理。

当 bb 等于 00 时，gcd⁡(a,b)=a\gcd(a,b)=a，此时 x=1,y=0x=1,y=0，显然是方程的一组特解。

而当 bb 不等于 00 时，由 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b) 可以知道：ax+by=bx′+(a mod b)y′ax+by=bx'+(a\bmod b)y'，而：

bx′+(a mod b)y=bx′+(a−⌊ab⌋×b)y′=ay′+bx′−⌊ab⌋×by′=ay′+b(x′−⌊ab⌋y′)\begin{aligned} bx'+(a\bmod b)y&=bx'+(a-\lfloor\frac{a}{b}\rfloor\times b)y'\\ &=ay'+bx'-\lfloor\frac{a}{b}\rfloor\times by'\\ &=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y') \end{aligned}

由 ax+by=ay′+b(x′−⌊ab⌋y′)ax+by=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y') 可以得到：x=y′,y=x′−⌊ab⌋y′x=y',y=x'-\lfloor\frac{a}{b}\rfloor y'。

将 x′,y′x',y' 不断代入递归求解直至 gcd⁡\gcd 为 00 再递归 x=1,y=0x=1,y=0 回去求解即可。

代码

1
2
3
4
5
6
7
8
9
10
11
void exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int tmp=x;
	x=y,y=tmp-(a/b)*y;
}

例题

P5656 【模板】二元一次不定方程 (exgcd)

对于形如 ax+by=cax+by=c 的二元一次方程，显然当且仅当 gcd⁡(a,b)∣c\gcd(a,b)\mid c 时，存在整数解。

设 d=gcd⁡(a,b),a′=a/d,b′=b/d,c′=c/dd=\gcd(a,b),a'=a/d,b'=b/d,c'=c/d，此时 gcd⁡(a′,b′)=1\gcd(a',b')=1，我们只需要求出 a′x′+b′y′=1a'x'+b'y'=1 的一组特解 x0′,y0′x_0',y_0'，原方程的其中一组解便是 x0=x0′×c,y0=y0′×cx_0=x_0'\times c,y_0=y_0'\times c。

求出特解后，该方程的通解便是：x=x0+b′t,y=y0+a′tx=x_0+b't,y=y_0+a't，其中 tt 是任意整数。

数论分块

如果你想要看严谨证明：https://www.luogu.com.cn/blog/Rong7/post-bi-ji-shuo-lun-fen-kuai

数论分块主要用于在 O(n)O(\sqrt{n}) 的时间复杂度下求形如 ∑i=1n⌊ni⌋\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor 的式子。

直接打表找规律，设 n=10n=10：

ii1122334455667788991010
⌊ni⌋\lfloor\frac{n}{i}\rfloor1010553322221111111111

可以发现 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 分别在一定的区域相等，因此只需要枚举每一个块的左边界 ll 和右边界 rr 即可。

仍然找规律，可以发现 r=⌊n⌊ni⌋⌋r=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor，有了有边界，每一个块的和就可以计算了。

代码

1
2
3
4
5
for(int l=1,r;l<=n;l=r+1) 
{
    r=n/(n/l);
    ans+=1ll*(r-l+1)*(n/l);
}

例题

UVA11526 H(n)

纯板子，跳过

P2261 【CQOI2007】余数求和

∑i=1nk mod i=∑i=1nk−⌊ki⌋×i=∑i=1nk−∑i=1n⌊ki⌋×i=n×k−∑i=1n⌊ki⌋×i\begin{aligned} \sum\limits_{i=1}^n k\bmod i&=\sum\limits_{i=1}^n k-\lfloor\frac{k}{i}\rfloor\times i\\ &=\sum\limits_{i=1}^nk-\sum\limits_{i=1}^n \lfloor\frac{k}{i}\rfloor\times i\\ &=n\times k-\sum\limits_{i=1}^n \lfloor\frac{k}{i}\rfloor\times i \end{aligned}

后面的就是板子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	ans=n*k;
	for(int l=1,r;l<=n;l=r+1)
	{
		if(k/l==0) r=n;
		else r=min(n,k/(k/l));
		ans-=(r-l+1)*(k/l)*(l+r)/2;
	}
	cout<<ans<<endl;
	return 0;
}

费马小定理

定义有两种等价的形式：

  • 若 pp 为质数，gcd⁡(a,p)=1\gcd(a,p)=1，则 ap−1≡1( mod p)a^{p-1}\equiv 1(\bmod p)
  • 对于任意整数 aa，ap≡a( mod p)a^p\equiv a (\bmod p)

这玩意似乎只是用来求逆元和进行素性测试的，个人感觉直接背下来也没什么问题。

归纳法证明

显然 1p≡1( mod p)1^p\equiv 1(\bmod p) 成立，我们假设 ap≡a( mod p)a^p\equiv a (\bmod p) 成立，那么：

(a+1)p=ap+(p1)ap−1+(p2)ap−2+⋯+(pp−1)a+1(a+1)^p=a^p+\tbinom{p}{1}a^{p-1}+\tbinom{p}{2}a^{p-2}+\cdots+\tbinom{p}{p-1}a+1

而由组合数的定义，我们知道 ∀1≤k≤p−1,(pk)≡0( mod p)\forall 1\leq k\leq p-1,\tbinom{p}{k}\equiv 0(\bmod p) 。

那么 (a+1)p≡ap+1( mod p)(a+1)^p\equiv a^p+1(\bmod p)，将 ap≡a( mod p)a^p\equiv a (\bmod p) 代入即可得到 (a+1)p≡a+1( mod p)(a+1)^p\equiv a+1(\bmod p)。

另外一种证明：https://oi-wiki.org/math/number-theory/fermat/#证明

欧拉函数

表示小于等于 nn 和 nn 互质的数的个数。写作 φ(n)\varphi(n)。

比如：φ(1)=1,φ(7)=6,φ(12)=4\varphi(1)=1,\varphi(7)=6,\varphi(12)=4

下面是它的一些性质：

  • 当 nn 是质数时，φ(n)=n−1\varphi(n)=n-1

  • 欧拉函数是积性函数，即若有 gcd⁡(a,b)=1\gcd(a,b)=1，φ(a×b)=φ(a)×φ(b)\varphi(a\times b)=\varphi(a)\times\varphi(b)

  • 由唯一分解定理，设 n=∏i=1spikin=\prod_{i=1}^sp_i^{k_i}，其中 pip_i 是质数，有 φ(n)=n×∏i=1spi−1pi\varphi(n)=n\times\prod_{i=1}^s\frac{p_i-1}{p_i}

    证明：

    φ(n)=∏i=1sφ(piki)=∏i=1s(pi−1)×piki−1=∏i=1spiki×(1−1pi)=n∏i=1s(1−1pi)\begin{aligned} \varphi(n)&=\prod_{i=1}^s\varphi(p_i^{k_i})\\ &=\prod_{i=1}^s(p_i-1)\times p_i^{k_i-1}\\ &=\prod_{i=1}^sp_i^{k_i}\times(1-\frac{1}{p_i})\\ &=n\prod_{i=1}^s(1-\frac{1}{p_i}) \end{aligned}

欧拉定理

若 gcd⁡(a,m)=1\gcd(a,m)=1，则 aφ(m)≡1( mod m)a^{\varphi(m)}\equiv1(\bmod m)

证明：https://oi-wiki.org/math/number-theory/fermat/#证明_1

扩展欧拉定理

ab≡{ab,b<φ(m)ab mod φ(m)+φ(m),b≥φ(m)( mod m)a^b\equiv \left\{ \begin{aligned} &a^b,b<\varphi(m)\\ &a^{b\bmod\varphi(m)+\varphi(m)},b\geq\varphi(m) \end{aligned} \right. (\bmod m)

证明：https://oi-wiki.org/math/number-theory/fermat/#证明_2

欧拉定理和扩展欧拉定理似乎只能用来降幂，所以说直接背也没太大问题。

例题

P5091 【模板】扩展欧拉定理

套公式即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,mod,b;
bool flag=false;
ll qpow(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
inline ll phi(ll x)
{
	ll ans=x;
	for(ll i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			ans=ans/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans=ans/x*(x-1);
	return ans;
}
int main()
{
	cin>>a>>mod;
	ll tmp=phi(mod);
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) 
	{
		b=b*10+ch-48,ch=getchar();
		if(b>tmp) b%=tmp,flag=1;
	}
	if(flag) b+=tmp;
	cout<<qpow(a,b)<<endl;
	return 0;
}

乘法逆元

如果一个线性同余方程 ax≡1( mod b)ax\equiv 1(\bmod b)，则 xx 被称作 a mod ba\bmod b 的逆元，记作 a−1a^{-1}

乘法逆元常用来解决有理数取模的问题。

例题

P2613 【模板】有理数取余

这道题就是求 bb 的逆元。

下面是几种求逆元的方法：

扩展欧几里得算法

ax≡1( mod b)ax\equiv 1(\bmod b) 与 ax+by=1ax+by=1 是等价的，因此就是求 xx 的最小正整数解。

注意需满足 gcd⁡(a,b)=1\gcd(a,b)=1

快速幂法

x≡ab−2( mod b)x\equiv a^{b-2}(\bmod b) ，用快速幂求即可。证明如下:

因为 ax≡1( mod b)ax\equiv1(\bmod b)，根据费马小定理，ax≡ab−1( mod b)ax\equiv a^{b-1}(\bmod b)，所以 x≡ab−2( mod b)x\equiv a^{b-2}(\bmod b)

注意需满足 bb 是质数。

线性求逆元

线性复杂度求出 1,2,⋯ ,n1,2,\cdots,n 中每个数关于 pp 的逆元。

首先，11 的逆元是它本身，即 1−1≡1( mod p)1^{-1}\equiv1(\bmod p)

对于递归情况 i−1i^{-1}，我们设 k=⌊pi⌋,j=p mod ik=\lfloor\frac{p}{i}\rfloor,j=p\bmod i，有 p=ki+jp=ki+j，那么：

ki+j≡0( mod p)ki+j\equiv 0 (\bmod p)

在两边同时乘 i−1×j−1i^{-1}\times j^{-1}：

kj−1+i−1≡0( mod p)i−1≡−kj−1( mod p)i−1≡−⌊pi⌋(p mod i)−1( mod p)kj^{-1}+i^{-1}\equiv 0 (\bmod p)\\ i^{-1}\equiv -kj^{-1}(\bmod p)\\ i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor(p\bmod i)^{-1}(\bmod p)

而 p mod i<ip\bmod i<i ，因此我们可以从已经计算出的答案得到 i−1i^{-1}。

代码如下：

1
2
3
inv[1]=1;
for(int i=2;i<=n;i++) 
    inv[i]=1ll*(p-p/i)*inv[p%i]%p;

例题：【模板】乘法逆元

线性求任意 nn 个数的逆元

线性复杂度求出任意给定 nn 个数（1≤ai<p1\leq a_i<p）的逆元。

首先计算 nn 个数的前缀积，记为 sis_i，计算出 sns_n 的逆元，记为 svnsv_n。

由于 svnsv_n 是前 nn 个数的逆元，我们将它乘上 ana_n 后，它就会和 ana_n 的逆元抵消，从而得到前 n−1n-1 个数的逆元 svn−1sv_{n-1}，以此类推，可以计算出所有 svisv_i，aia_i 的逆元即为 svi×si−1sv_i\times s_i-1。

1
2
3
4
5
s[0]=1;
for(int i=1;i<=n;i++) s[i]=s[i-1]*a[i]%p;
inv[n]=qpow(s[n],p-2);
for(int i=n;i>=1;i--) inv[i-1]=inv[i]*a[i]%p;
for(int i=1;i<=n;i++) inv[i]=inv[i]*s[i-1]%p;

例题：【模板】乘法逆元 2

中国剩余定理

语文不好不知道怎么描述，所以咕咕咕。建议看 OI Wiki，写得挺清楚的。

中国剩余定理 - OI Wiki

再给 xhr 的博客打个广告：CRT，中国剩余定理&P1495题解

扩展中国剩余定理

咕咕咕，之后来填坑

威尔逊定理

定义：对于质数 pp 有 (p−1)!≡−1( mod p)(p-1)!\equiv -1(\bmod p)。

直接背！

证明

首先对于 p≤5p\leq 5 的情况，直接证即可。

对于 p≥5p\geq 5，则 (p−1)!=1×(p−1)×(2×3×⋯×(p−2))(p-1)!=1\times(p-1)\times(2\times3\times\cdots\times(p-2))

我们假设 22 到 p−2p-2 中有两个数 a,ba,b 在模 pp 意义下有相同的逆元 tt，则：

at≡bt≡1( mod p)at\equiv bt\equiv 1(\bmod p)

可以得到，p∣t(a−b)p\mid t(a-b)。

又因为 a,b,t<pa,b,t<p ，故而 t∤pt\nmid p 且 p∤(a−b)p\nmid (a-b)，因此 p∤t(a−b)p\nmid t(a-b)，矛盾。

故 22 到 p−2p-2 中的每个数逆元不同。

假设 2≤k≤(p−2)2\leq k\leq(p-2) 且 kk 的逆元是它本身，则：

k2≡1( mod p)k^2\equiv 1(\bmod p)

即 p∣k2−1p\mid k^2-1，因式分解，p∣(k+1)(k−1)p\mid (k+1)(k-1)，解得 k=1k=1 或 k=p−1k=p-1 ，不在其范围中，故不存在 kk。

综上，22 到 p−2p-2 中每个数在模 pp 意义下逆元不同，且不为自己，同时也都在 22 到 p−2p-2 中，所以：

(p−1)!≡1×(p−1)×(2×3×⋯×(p−2))≡p−1≡−1( mod p)(p-1)!\equiv 1\times(p-1)\times(2\times3\times\cdots\times(p-2))\equiv p-1\equiv -1(\bmod p)

证毕。

例题

UVA1434 YAPTCHA

这道题虽然是紫题，但是很水。

原根

原根，启动！

详细证明请参考 原根 - OI Wiki

阶

若满足同余式 an≡1( mod m)a^n\equiv1(\bmod m) 的最小正整数存在，则这个 nn 被称作 aa 模 mm 的阶，记作 δm(a)\delta_m(a)。

阶有一个下面会用到的性质：

若 gcd⁡(a,n)=1\gcd(a,n)=1，且 ak≡1( mod n)a^k\equiv 1(\bmod n)，则 k∣φ(n)k\mid \varphi(n)

定义

正整数 gg 是正整数 nn 的原根，当且仅当 1≤g≤n−11\leq g \leq n-1，且 gg 模 nn 的阶为 φ(n)\varphi(n)。

什么数有原根

只有 2,4,pk,2×pk2,4,p^k,2\times p^k（pp 为奇素数）这类数才有原根。

如何求 nn 的所有原根

先找到 nn 的最小原根 gg，那么 nn 的每一个原根都形如 gkg^k 的形式，其中 kk 满足 gcd⁡(k,φ(n))=1\gcd(k,\varphi(n))=1，于是我们还可以知道其原根个数为 φ(φ(n))\varphi(\varphi(n))。

找最小原根

据说 nn 的最小原根不超过 n0.25n^{0.25} ，因此我们可以直接枚举 gg，具体方法如下：

根据定义，若 gg 是 nn 的原根，需要满足两个条件：

  • gφ(n)≡1( mod n)g^{\varphi(n)}\equiv 1(\bmod n)

  • ∀1≤k<φ(n),gk≢1( mod n)\forall 1\leq k<\varphi(n),g^k\not\equiv 1(\bmod n)

问题在于第二点，我们不可能把所有小于 φ(n)\varphi(n) 的数都枚举一遍。

这时候就会用到阶的那个性质，也就是说我们只需要检验 φ(n)\varphi(n) 的因子即可。进一步的优化，设 nn 的所有素因数为 p1,p2,⋯ ,ptp_1,p_2,\cdots,p_t，只需检验所有的 φ(n)pi\frac{\varphi(n)}{p_i}，因为它们涵盖了 φ(n)\varphi(n) 的所有因子的倍数。

细节见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6;


int prime[maxn+5],tot;
bool vis[maxn+5];
inline void pri()
{
	for(int i=2;i<=maxn;i++)
	{
		if(!vis[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++)
		{
			if(1ll*prime[j]*i>maxn) break;
			vis[prime[j]*i]=1;
			if(i%prime[j]==0) break; 
		}
	}
}

bool is[maxn+5];
inline void init() //预处理出有原根的数
{
	is[2]=is[4]=1;
	for(int i=2;i<=tot;i++)
	{
		ll x=1;
		for(int j=1;;j++)
		{
			x*=prime[i];
			if(x>maxn) break;
			is[x]=1;
			if(2*x<=maxn) is[2*x]=1;
		}
	}
}

inline ll qpow(ll x,ll y,ll mod)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}

inline int phi(int x) 
{
	int res=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			res=res/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) res=res/x*(x-1);
	return res;
}

int factor[maxn+5],num;
inline void divide(int x)
{
	num=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			factor[++num]=i;
			if(i!=x/i) factor[++num]=x/i;
		}
	}
	if(x>1) factor[++num]=x;
}

inline bool check(int a,int phin,int mod)
{
	for(int i=1;i<=num;i++)
	{
		if(qpow(a,phin/factor[i],mod)==1) return false;
	}
	return true;
}

int t,n,d,ans[maxn+5],cnt;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	pri();
	init();
	cin>>t;
	while(t--)
	{
		cnt=0;
		cin>>n>>d;
		if(!is[n])
		{
			cout<<"0\n\n";
			continue;
		}
		int phin=phi(n),g;
		divide(phin);
		for(int i=1;i<n;i++)
		{
			if(qpow(i,phin,n)==1&&check(i,phin,n))
			{
				g=i;
				break;
			}
		}
		int x=1;
		for(int i=1;i<=phin;i++)
		{
			x=1ll*x*g%n;
			if(__gcd(i,phin)==1) ans[++cnt]=x;
		}
		sort(ans+1,ans+1+cnt);
		cout<<cnt<<"\n";
		for(int i=d;i<=cnt;i+=d) cout<<ans[i]<<" ";
		cout<<"\n";
	}
	return 0;
}

代码可以过掉 P6091 【模板】原根

大步小步算法

英文名：Baby Step Giant Step，缩写 BSGS，别名拔山盖世

BSGS 是一种用来解决形如：

ax≡b( mod m)a^x\equiv b(\bmod m)

的高次同余方程的算法，时间复杂度 O(n)O(\sqrt{n})，其中 aa 与 mm 要求互质。

设 t=⌊p⌋,0≤j≤t−1t=\lfloor\sqrt{p}\rfloor,0\leq j\leq t-1，那么 xx 可以被表示为 x=i×t−jx=i\times t-j，可得 ai×t−j≡b( mod m)a^{i\times t-j}\equiv b(\bmod m)，同乘 aja^j 得：

ai×t≡b×aj( mod p)a^{i\times t}\equiv b\times a^j(\bmod p)

我们考虑枚举 0≤j≤t−10\leq j\leq t-1，将所有 b×ajb\times a^j 插入一个哈希表中，再枚举 0≤i≤t0\leq i\leq t ，查询哈希表中是否有和 ai×ta^{i\times t} 相等的值，如果有，就得出了一组 i,ji,j，由于 tt 已知，就可以求出方程的解 xx。

感觉相当暴力

例题

P3846 【模板】BSGS

板子，按上面的来就对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll n,ll mod)
{
	ll res=1;
	while(n)
	{
		if(n&1) res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
ll p,b,n;

map<ll,ll> hmap;
inline ll bsgs()
{
	ll t=sqrt(p);
	for(int i=0;i<t;i++) hmap[n*qpow(b,i,p)%p]=i;
	b=qpow(b,t,p);
	if(b==0) return n==0?1:-1;
	for(int i=0;i<=t;i++) 
	{
		ll tmp=qpow(b,i,p);
		if(hmap[tmp]&&i*t-hmap[tmp]>=0) return i*t-hmap[tmp]; 
	}
	return -1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>p>>b>>n;
	ll tmp=bsgs();
	if(tmp==-1) cout<<"no solution\n";
	else cout<<tmp<<endl;
	return 0;
}

P2485 【SDOI2011】 计算器

欧拉公式

eiθ=cos⁡θ+isin⁡θe^{i\theta}=\cos \theta+i\sin \theta

当取 θ=π\theta=\pi 时，有

eiπ=cos⁡π+isin⁡π=1e^{i\pi}=\cos \pi+i\sin\pi=1

单位根

前置知识：复数

在复数域下，满足 xn=1x^n=1 的 xx 被称为 nn 次单位根。

根据代数基本定理（nn 次复系数多项式方程在复数域内有且只有 nn 个根），nn 次单位根一共有 nn 个。

容易发现，这 nn 个单位根在恰好 nn 等分了复平面上的单位元，并且将其按照辐角大小排序后第 kk 大的根是 ei2kπne^{i\frac{2k\pi}{n}}

本原单位根

00 到 n−1n-1 次方的值能生成所有 nn 次单位根的 nn 次单位根称为 nn 次本原单位根。

显然 x1=ei2πnx_1=e^{i\frac{2\pi}{n}} 是一个本原单位根。

nn 次本原单位根记为 ωn\omega_n（这个是希腊字母 Omega）。

性质

以下性质会在 FFT 中用到。

设 nn 是一个正偶数，且 n=2mn=2m，有：

(ωnk)2=ωmkωnk+m=−ωnk(\omega_n^k)^2=\omega_m^k\\ \omega_n^{k+m}=-\omega_n^k

未完待续

咕咕咕