关于原根判定的若干证明

其实这个证法是从 zhx 的讲稿中看+结合我自己 yy 出来的……其实这个做法的来源是拉格朗日定理,改天学了之后说不定我会有什么新的认识……

引理1 \,\,\,\, 如果 G = <a> ,称 G 为循环群,若 G 为有限循环群,可知当 |G| = \infty 时, G 与整数加群 \mathbb{Z} 同构,当 |G| \ne \infty 时, ord(a)=|G|

设在质数 \text{mod } p 意义下进行加法和乘法, 那么乘法群 G=\{1,2, \cdots ,p-1 \} 是一个循环群。设 aG 的生成元 (<a>=G),易知 ord(a) = |G| = \varphi(p)

引理2 \,\,\,\, 由欧拉定理可知 \forall a \in G \,,\,ord(a)|\varphi(p)

引理3 \,\,\,\,k=ord(a) \,\,\,(a \in G) ,则 a^k=e , a^{k+i}=a^i

引理4 \,\,\,\, 设原根为 a ,对于\forall 1\leqslant i \leqslant p-1 , \exists x >0 \text{ s.t. } a^x=i \,\, (\text{ mod } p)

引理5 \,\,\,\, 设原根为 a , 仅有 a^{t\varphi(p)}=e ,其中 t \in \mathbb{N}_+

原根判断:a 为原根的充要条件是:对于所有 p 的质因子 d ,都有 a^{\frac{\varphi(p)}{d}} \ne 1

证明:

ord(a)=k

k=\varphi(p) ,则 a 是循环群的生成元,可知 a 为原根,并且 a^{\frac{\varphi(p)}{d}} \ne 1

k < \varphi(p) 时,据引理 2 可知 ord(a)| \varphi(p)

t = \frac{\varphi(p)}{k} , 显然 t>1

dt 任一质因子,显然有 \frac{\varphi(p)}{t}|\frac{\varphi(p)}{d} ,据引理 3 可知 a^{\frac{\varphi(p)}{d}}=1 ,由引理 4 可知 a 显然不是一个原根。

于是胡言乱语地证明完了。

[HNOI2008] Cards

这应该是最传(麻)统(烦)的做法

首先题目里面有句话说

输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

这话啥意思?意思就是置换群大小 |G| = m+1 (自己到自己也算一个)

(并且(除幺元置换之外)没有不动点,这个性质直接导致了那个组合数的解法)

上文的大概证明可以找找洛谷上的题解

不过我们还是可以这么做:

找每个置换 g_i 的循环节,然后DP出不动点的个数。

最后算一下方案就好了, 直接硬上 Burnside

 

从小学开始的数数

Introduction

\sigma 是一个从集合 \mathbb{A}=\{ 1,2,\cdots,n \} 到自身的一一映射 , 那么可以称 \sigma 为置换 ,  形如

\sigma =\left( \begin{matrix} 1& 2& 3& \cdots& n \\ a_1& a_2& a_3& \cdots& a_n \end{matrix} \right)

(其中 \{a_i\} 是一个排列)

P.S. 置换可以做乘法,比如 \left( \begin{array}{c} a \\ b \end{array} \right) \cdot \left( \begin{array}{c} b \\ c \end{array} \right) =\left( \begin{array}{c} a \\ c \end{array} \right)

置换+群论

置换群 ?

置换群 (G,\cdot) (我就直接记作 G 了…) 是一个置换的群. 也即一个带有 (其实严格说叫做装备 equip) 二元运算的置换的集合 , 并满足群的四个性质:

  1. \text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G
  2. \text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)
  3. \text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a
  4. \text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e

(所有的群存在唯一逆元和唯一幺元 , 具体的证明在一个叫做 “OI实用群论” 的文里)

染色问题与等价

定义 在一个群上 , x 为对集合 \mathbb{A} 元素的着色方案 , \mathbb{C} 为所有着色方案的集合 ;

定义 如果 \exists g_i \in G 使得 g_i \cdot x = y , 称作 x,y 等价.

Burnside Lemma

要解决的问题就是在给定置换群 G 和着色方案集合 \mathbb{C} 的情况下, 求出有多少种本质不同的着色方案 (也就是两两不等价).

定义 \mathbb{C}(f) 为在置换 g_i \in G 的作用下不变的染色方案的集合. 集合中的元素(这里的元素是染色方案)又称该置换下的不动点.

N(G,\mathbb{A})= \frac{1}{|G|}\sum_{ g \in G } |\mathbb{C}(g)|

(等价类数目为各集合不动点数目的均值)

Pólya Theorem

G 为对 n 个对象的置换群 , 每个对象可以用 m 种颜色染色 , 等价类数目是 :

N(G,\mathbb{C}) = \frac{1}{|G|} \sum_{ i = 1 }^{|G|} m^{c(g_i)}

其中 c(g_i) g_i \in G 的轮换 (循环节) 的个数 .

(说到轮换 , 突然想到曾经写过一个挺好玩的文)

这就意味着如果染色 x \in \mathbb{C} g_i \in G 的作用下不变 , 那么每个轮换中的元素必须染同种颜色 .

Important conclusions

第一个结论是循环移位的。

通过(循环)移位形成的置换,假设一个 n 个对象的置换,循环移位 k 位,轮换数为 \gcd(n,k)

第二个结论是图上置换群的。

对于 n 个点的无向有色完全图,点的置换有 n 个元素,对于每一个大小设为 a 的轮换,这个轮换对应的完全子图的边的轮换 \frac{a}{2} 个,对于两个大小为 a,b   的轮换,ab 之间的边所形成的置换,它的轮换有 \gcd(a,b) 个。

证明的话 我们先证后面那条,考虑一条边的颜色 c(x,y) 其中 xy 属于不同的轮换 ( 轮换大小分别为 n,m ) ,考虑边的轮换都要同色,这样我们保证的是 \forall k , c(x,y) = c(x+k \mathrm{ mod } n , y+k \mathrm { mod } m)

那么每个点其实都一样了。用类似结论 [1] 的证法可以发现是 \gcd(n,m)

而且你会发现因为一共 ab 条边,所以说每个循环节大小是 \mathrm{lcm}(n,m) 的。

然后前面那条是类似的。。(不负责任)

前面那条的话,一个  好理解的证法是枚举一个点,发现这个点所在的对称轴把轮换这个环分成两半了。然后对于对称的一半,这些点与 1 的边会转会来,然后只需要考虑一半的点就好了-0-

– END –

[咕咕]OI实用群论

\text{群}\left( G,\cdot \right)

\text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G

\text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)

\text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a

\text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e

 

\text{所有行列式非零的}n\text{阶方阵是一个群}

\text{群中的单位元唯一}.

\text{证明:\ }

\text{设有两个单位元}e_1,e_2

e_1=e_1e_2=e_2.\ \blacksquare

\text{群中的逆元唯一}

\text{证明:}

\text{设}a\text{有两个逆元}b,c

b=b\cdot \left( a\cdot c \right) =\left( b\cdot a \right) \cdot c=c.\ \blacksquare

 

\text{周期:\ }a\text{的周期是}o\left( a \right)

o\left( a \right) \text{表示最小正整数,\ 使得}a^{o\left( a \right)}=e

 

\left( ab \right) ^{-1}=a^{-1}b^{-1}

 

\text{子群:}

\text{若}\left( G,\cdot \right) ,\ H\subseteq G,\ \text{且}\left( H,\cdot \right) \text{是群,\ 称在运算}\cdot \text{下}H\text{是}G\text{的子群,\ 用}H\leqslant G\text{表示}.

 

\text{生成子群}

\text{集合}S\text{的生成子群用}<s>\text{表示}.

 

\text{右傍集:}

\text{如果}H\leqslant G,\ \text{对于}a\in G,\ \text{定义集合}Ha=\left\{ x\in G\ |\ \exists h\in H,ha=x \right\}

 

Ha=Hb\text{当且仅当}ab^{-1}\in H

\text{若}Ha=Hb,\ ea\in Ha,\ \text{即}a\in Hb,\ \text{那么}\exists h\in H,\ a=hb,\ ab^{-1}=h.

\text{若}ab^{-1}\in H,\

ha=ha\left( bb^{-1} \right) =h'b\in Hb,\ \text{因此}Ha\subseteq Hb.

hb=hb\left( a^{-1}a \right) =h\left( ab^{-1} \right) ^{-1}a\in Ha,\ \text{因此}Hb\subseteq Ha

\text{因此}Ha=Hb.\ \blacksquare

 

\text{若}Ha\ne Hb,\ \text{那么}Ha\cap Hb=\varnothing

\text{证明:\ }

\text{假设}x\in Ha\cap Hb,\ \text{则}\exists h_1,h_2\in H,\ h_1a=h_2b=x,\

\text{那么}a=h_{1}^{-1}h_2b,\ ab^{-1}=h_{1}^{-1}h_2\in H,\ Ha=Hb,\ \text{矛盾}.\blacksquare

 

\text{傍集是无交集的,\ 每个傍集都是和}H\text{一样大的,\ 即|}H|=|Ha|

 

\text{由于}\forall g\in G,\ g\in Hg,\ \text{所以}G\text{中每个元素都在某个傍集中}.

\text{用}\left[ G:H \right] \text{表示不同的傍集数,\ 则|}G|=|H|\cdot \left[ G:H \right]

|H|\text{是|}G|\text{的约数}.

 

\text{若}a\in G,\text{则}o\left( a \right) \ |\ |G|

\text{证明:\ 考虑}a\text{的生成子群}<a>=\left\{ a,a^2,a^3\cdots a^{o\left( a \right)} \right\}

 

|Ha|=|H|

\Rightarrow \text{如果}h_1\ne h_2,\ \text{那么}h_1a\ne h_2a

\text{证明:\ 若}h_1a=h_2a,\ h_1aa^{-1}=h_2aa^{-1},\ h_1=h_2\text{矛盾}

\therefore \text{对于不同的}h,\ ha\text{互不相同,\ 因此|}Ha|=|H|.\ \blacksquare

 

\text{P.S.费马小定理的另一个证明}

\text{考虑质数}p\text{和群}G=\left\{ \text{1,2,}\cdots p-1 \right\} ,\ \text{群的运算定义为mod\ }p\text{意义下的乘法}.

\forall a\in G,\ a^{o\left( a \right)}=e;\ o\left( a \right) |\left( p-1 \right)

\therefore a^{p-1}=\text{1.\ }\blacksquare

\text{欧拉定理证明}

\text{考虑}n\in N^+,\ \text{考虑群}G=\left\{ x\ |1\leqslant x\leqslant n,\ gcd\left( x,n \right) =1 \right\}

|G|=\varphi \left( n \right) ,\ o\left( a \right) \ |\ |G|

\therefore \forall a\in G,a^{\varphi \left( n \right)}=\text{1\ }\left( \text{mod\ }n \right) .\ \blacksquare

 

\text{给定}a,b,\ o\left( a \right) =m,o\left( b \right) =n,\ ab=ba

\text{证明:\ 若}\left( m,n \right) =\text{1,\ 则}\exists g\in G,\ \text{s.t.\ }o\left( g \right) =mn

g=a\cdot b,\ \left( ab \right) ^{mn}=e,\ \text{设}o\left( g \right) =k\leqslant mn

\text{若}\left( ab \right) ^k=e,\text{那么}a^{nk}=\left( ab \right) ^{nk}=e,\ \text{可知}m|nk

\text{同理}n|mk.

\because \left( m,n \right) =1

\therefore m|k,\ n|k,\ mn|k,\ k=mn.\ \blacksquare

 

\text{证明:\ }\exists g\in G,\ \text{s.t.\ }o\left( g \right) =\text{lcm}\left( m,n \right)

m=\prod_{i=1}^s{t_{i}^{p_i}},\ n=\prod_{i=1}^s{t_{i}^{q_i}}

\text{通过交换各个}a_i\text{的顺序,\ 总能存在}0\leqslant l\leqslant s,\ \text{s.t}.

\forall i\leqslant l,\ p_i\leqslant q_i;\ \forall i>l,\ p_i\geqslant q_i

\text{令}c=a^u,\ u=\prod_{i=1}^l{t_{i}^{p_i}};\ d=b^v,\ v=\prod_{i=l+1}^s{t_{i}^{q_i}}

o\left( cd \right) =\text{lcm}\left( m,n \right)

\text{由于}o\left( c \right) =\frac{m}{u}=v;\ o\left( d \right) =\frac{n}{v}=u

\text{那么gcd}\left( o\left( c \right) ,o\left( d \right) \right) =\text{1,\ 又}cd=dc,\ \text{由}\left( 1 \right) \text{可得}o\left( cd \right) =o\left( c \right) o\left( d \right) =\text{lcm}\left( c,d \right) .\ \blacksquare

 

\text{如果}G=<a>,\ \text{称}G\text{为循环群}.

\text{若}G\text{为有限循环群,\ 则}o\left( a \right) =|G|

 

\text{令}k=o\left( a \right) ,\ \text{则}a^k=e,\ \text{那么}a^{k+i}=a^i

 

\left\{ a^1,\ a^2,\ \cdots ,\ a^k \right\} ,\ \text{这当中的数两两不同}

\text{反证:\ 设}1\leqslant x\leqslant y\leqslant k,\ a^x=a^y,\ \text{那么}a^{y-x}=e,\ \text{矛盾.\ }

 

\text{e.g.\ mod\ 7意义下的乘法下,}\left\{ \text{1,2,3,4,5,}6 \right\} \text{是循环群}.

 

G\text{是循环群当且仅当|}G|\text{是最小的}m\in N^+,\ \text{使得}\forall g\in G,\ g^m=e

\text{证明:}

\text{若}G=<a>\text{是循环群,\ 则}o\left( a \right) =|G|,\ \therefore m\geqslant |G|

\text{又}\because \forall g\in G,g^{|G|}=e,\ \therefore m=|G|

\text{若}m=|G|

\text{如果}\exists a\in G,\ \text{s.t.\ }o\left( a \right) =|G|,\ \text{那么}G=<a>

\text{否则,\ }\forall g\in G,\ o\left( g \right) <|G|

\text{设周期最大的元素为}a,\ o\left( a \right) =t

\therefore \forall g\in G,\ \text{由上述性质可得}o\left( g \right) |t

\text{那么}t\text{满足}\forall g\in G,g^t=e,\ m\leqslant t,\ \text{矛盾.\ }\blacksquare

 

\text{半群:\ 满足封闭性和结合律}

\text{交换群:\ 满足交换律的群}

\text{环:\ }\left( R,+,\cdot \right) ,\ \text{其中}\left( R,+ \right) \text{是交换群,\ }\left( R,\cdot \right) \text{是半群}

\text{e.g.\ }\mathbb{Z}\ \mathbb{R}\left[ \text{x} \right] \

\text{域:\ }\left( F,+,\cdot \right) ,\ \text{其中}\left( F,+ \right) \text{是交换群,\ }\left( F\backslash \left\{ 0 \right\} ,\cdot \right) \text{是交换群}

\text{e.g.\ }\mathbb{Q}\ \mathbb{R}\ \mathbb{C}

 

\text{代数基本定理:\ 在域}F\text{中,\ }n\text{次非零多项式}f\left( x \right) \text{至多有}n\text{个不同的根}.

\text{证明留作习题}.

 

\text{任意一个域的乘法群的有限子群}G\text{一定是循环}.

\text{证明:}

\text{令}m\text{是最小的正整数,\ 使得}\forall g\in G,\ g^m=e

\text{首先}\forall g\in G,\ g^{|G|}=e,\ m\leqslant |G|

\text{考虑多项式}x^m-e,\ G\text{中元素都是这个多项式的根;}

\text{由代数基本定理,\ |}G|\leqslant m

\therefore m=|G|

\text{由循环群性质得,\ }G\text{是循环群.\ }\blacksquare

 

\text{考虑质数}p,\ \text{在对}p\text{取模的意义下进行加法和乘法,\ 那么}G=\left\{ \text{0,1,2,}\cdots ,p-1 \right\} \text{是一个域}

\text{乘法群}G\backslash \left\{ 0 \right\} \text{是循环群}

\text{循环群的生成元叫做原根}.

\text{生成元:\ 设}a\text{为群}G\text{的生成元,\ 则}G=<a>.

 

\text{对于原根}a,\ \forall 1\leqslant i\leqslant p-\text{1,\ }\exists x>\text{0,\ }a^x=i\ \left( \text{mod\ }p \right)

 

\text{一个循环群}G,\ \text{设}p-1=|G|,\ \text{其中}p\text{为质数}.

\text{设}a\text{为生成元,}

G=\left\{ a,a^2,a^3,\cdots ,a^{p-1} \right\}

\text{那么}a^{p-1}=e;

\text{如果}g\text{是原根,\ 当且仅当}o\left( g \right) =p-1.

\text{设}g=a^t,\ \text{那么}o\left( g \right) \text{为最小的}s\text{使得}\left( p-1 \right) |st

 

o\left( g \right) =p-\text{1当且仅当gcd}\left( t,p-1 \right) =1

\because \left( p-1 \right) |st,\ \text{且}t|st

\therefore st\text{是}t\text{和}p-\text{1的公倍数}

\text{若gcd}\left( p-\text{1,}t \right) =\text{1,\ 那么lcm}\left( p-\text{1,}t \right) =t\left( p-1 \right)

\text{由于}st\text{是}t\text{和}p-\text{1的公倍数,\ 因此}s=p-1

\text{若gcd}\left( p-\text{1,}t \right) \ne \text{1,\ 设gcd}\left( p-\text{1,}t \right) =d,\ \text{则}d>1

\text{取}s=\frac{p-1}{d},\ \text{则}st=\left( p-1 \right) \frac{t}{d}

 

|G|\text{中原根的数量为}\varphi \left( p-1 \right)

\text{找原根:\ 由于}\varphi \left( p-1 \right) \text{较大,\ 暴力枚举2,3,}\cdots \text{并判断}.

\text{判断:\ 只需判断是否存在比}p-\text{1小的数}x\text{使得}a^x=1

\text{枚举}p-\text{1的所有质因子}d,\text{判断}a^{\frac{p-1}{d}}\text{是否为}1

\text{如果都不是,\ 那么}a\text{就是原根}.

\because \text{假设}o\left( a \right) =k,\ \text{假设}k<p-\text{1,\ 那么}k|p-1

\text{证明:}

\text{由于}a^{\text{gcd}\left( k,p-1 \right)}=\text{1,\ 所以}k|p-\text{1.\ }\blacksquare

\text{令}t=\frac{p-1}{k},\ \text{那么}t>1

\text{令}d\text{是}t\text{中任一质因子,\ }\frac{p-1}{t}|\frac{p-1}{d},\ \text{那么}a^{\frac{p-1}{d}}=1

 

\text{离散对数}

\text{记}G\text{的原根是}a,\ \text{由于}\forall g\in G,\ \exists t,a^t=g,\ \text{那么}t=\log _ag

 

\left( \text{BSGS} \right) \text{令}q=\lceil \sqrt{p} \rceil

\text{求出}S=\left\{ a^0,a^1,\cdots ,a^q \right\}

T=\left\{ a^0,a^q,a^{2q},\cdots a^{q^2} \right\}

\forall a^x=g,\ \text{因为}x=kq+l,\ 0\leqslant k,l\leqslant q

\text{那么}g=a^{kq}a^l

\text{可以写成}g=st,s\in S,t\in T

 

\text{枚举}s\in S,\ \text{需要的}t\text{就是}s^{-1}g.

\text{对}T\text{建哈希表,\ 查找}s^{-1}g\text{在}T\text{内是否存在}.

O\left( \sqrt{p} \right) \text{求一个离散对数}x.

通过移位形成的置换群的轮换数

有这样一个结论,n个元素的置换群通过移k位形成的置换数是 \gcd(n, k)
例如 n = 6, k = 2 的置换群的置换数是 \gcd(6, 2) = 2

0 1 2 3 4 5
2 3 4 5 0 1

形成的置换是 [2, 4, 0][3, 5, 1]

考虑一下为什么是这样的,一个直观的入手点就是尝试几个例子,然后分析一下置换是怎样形成的,清楚了这个自然也就明白了置换数会是多少。

  • 假设我们移位 k,并且从 \rm base 位置开始寻找置换,那么置换将会是 (kx + \mathrm{base} )\mod n \; (x \in \mathbb{N} ) 得到的数字。

例如 n = 9, k = 6

0 1 2 3 4 5 6 7 8
6 7 8 0 1 2 3 4 5

\rm{base} = 0 位置对应开始

\begin{array}{c} 6 \times 1 \mod 9 = 6 \\ 6 \times 2 \mod 9 = 3 \\ 6 \times 3 \mod 9 = 0 \\ \end{array}

\rm{base} = 1 位置对应开始


\begin{array}{c} (6 \times 1 + 1) \mod 9 = 7 \\ (6 \times 2 + 1) \mod 9 = 4 \\ (6 \times 3 + 1) \mod 9 = 1 \\ \end{array}

\rm{base} = 2 位置对应开始

\begin{array}{c} (6 \times 1 + 2) \mod 9 = 8 \\ (6 \times 2 + 2) \mod 9 = 5 \\ (6 \times 3 + 2) \mod 9 = 2 \\ \end{array}

对于这个例子观察发现,形成的置换貌似就是\mathrm{mod}\; \gcd(n,k) 的同余类。

看看这是不是正确的,前面的分析过程使我们将置换转换为 (kx + \mathrm{base} ) \mod n 这样的一个式子, 也就是说这个式子的结果根据 \rm base 的不同为什么会形成\mathrm{mod}\; \gcd(n,k) 的同余类。

我们在这里让 \mathrm{base} < n ,于是我们有:

(kx + \mathrm{base}) \;\mathrm{mod}\; n = kx \;\mathrm{mod}\; n + \mathrm{base}

这样我们可以只分析 kx \mod n 这一部分。

我们让 kx \;\mathrm{mod}\; n \equiv ky \;\mathrm{mod}\; n

所以 k \cdot (y-x) \;\mathrm{mod}\; n = 0

x = 0 时,ky \;\mathrm{mod}\; n = 0 ,这就意味着我们要证明满足此式子的 y > 0\min x\frac{n}{gcd(n,k)}

我们假设 x < \frac{n}{gcd(n, k)} 且满足上式时,kx | n,而且显然 kx | m ,那么 kx 就是 nk 的最小公倍数 。

但是 kx < k \cdot \frac{n}{gcd(n,k)} ,右边才是最小公倍数,所以当 x < \frac{n}{gcd(n, k)} 时,不满足 k \cdot (y-x) \;\mathrm{mod}\; n = 0

所以满足上式的 \min x=\frac{n}{gcd(n,k)}。这也就是轮换的个数是 \frac{n}{gcd(n,k)}