群的定义
若非空集合 \(G\) 和定义在 \(G\) 上的二元运算 \(?\) 构成的代数结构 \((G,?)\), 满足:
封闭性:\(\forall a,b\in G\), 有 \(a?b\in G\).
结合律:\(\forall a,b,c\in G\), 有 \((a?b)?c=a?(b?c)\).
单位元:\(\exists e\in G\), 满足 \(\forall a\in G\) 有 \(a?e=a\).
逆元:\(\forall a\in G\),\(\exists b\in G\) 使得 \(a?b=e\), 记 \(a^{-1}=b\).
则代数结构 \((G,?)\) 是一个群 (group).
常见的群有: 整数, 有理理数, 实数加法群; 模 \(n\) 意义下的加法群; 模 \(n\) 意义下与 \(n\) 互质的数构成的乘法群; 置换群, 群的元素是一个双射 \(f\), 运算为映射的复合.
拉格朗日定理
对于群 \((G,?)\), 若有 \(G'\subset G\) 且 \((G',?)\) 也是群, 则称 \((G',?)\) 是 \((G,?)\) 的子群, 且 \(|G|\) 是 \(|G'|\) 的倍数.
证明:
记 \(G_a\) 表示集合 \(G\) 的陪集 \(\{x?a|x\in G\}\), 那么易知 \(|G_a|=|G|\).
对于 \(a,b\in G\), 若有 \(G'_a\cap G'_b \neq \emptyset\), 则 \(\exists x,y\in G'\) 满足 \(x?a=y?b ? a=x^{-1}?y?b\).
那么 \(\forall z\in G'\), 有 \(z?a=z?(x^{-1}?y?b)=(z?x^{-1}?y)?b\). 易知 \(z?x^{-1}?y \in G'\), 所以 \(G'_a\) 中的每一个元素都存在于 \(G'_b\) 中, 即 \(G'_a=G'_b\).
于是可知 \(G'\) 的陪集之间只有两种关系, 互不相交或完全相同. 而由于 \(e\in G'\), 所以 \(G'\) 的所有陪集的并就是 \(G\). 又由于陪集的大小等于原集合, 所以 \(|G|\) 是 \(|G'|\) 的倍数.
由拉格朗日定理可以推出欧拉定理 \(a^{\varphi(m)} \equiv 1 \pmod m\).
证明:
设集合 \(S=\{a_1,a_2,...,a_{\varphi(n)}\}\), 其中 \(gcd(a_i,n)=1\).\(S\) 与模乘法形成的代数结构 \((S,\times)\) 是群.
那么设 \(S_i=\{1,a_i,a_i^2,a_i^3...\}\), 易知 \((S_i,\times)\) 是 \((S,\times)\) 的子群, 即 \(|S_i||\varphi(n)\). 而 \(a_i^{|S_i|}\equiv 1\), 所以 \(a_i^{\varphi(n)}\equiv 1\).
...
来源: http://www.bubuko.com/infodetail-2590760.html