[咕咕]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.

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据