从「有没有逆元」到抽象结构

上一讲的问题是：给定 $a$ 与 $n$，是否存在 $b$ 使 $ab\equiv1\pmod n$？答案由最大公因数决定：$\gcd(a,n)=1$ 时有逆元，否则没有。这个结论是用扩展欧几里得算法得到的。

本讲换一个角度看同一件事：把「可逆」这件事升级成一整套代数结构。一旦建立群论的语言，许多看起来互不相关的定理——Lagrange 定理、费马小定理、欧拉定理——会变成同一个证明的不同写法。

时间轴

群的定义

一个群是一个集合 $G$ 配上一个二元运算 $*$，满足四条公理：

1. 封闭性：$a,b\in G\Rightarrow a*b\in G$。
2. 结合律：$(a*b)*c=a*(b*c)$ 对一切 $a,b,c\in G$ 成立。
3. 单位元：存在 $e\in G$，使 $e*a=a*e=a$ 对一切 $a$ 成立。
4. 逆元：对每个 $a\in G$，存在 $a^{-1}\in G$，使 $a^{-1}*a=a*a^{-1}=e$。

如果还满足交换律 $a*b=b*a$，就称 $G$ 为阿贝尔群（交换群）。

注意公理里没有要求「逆元唯一」「单位元唯一」——这些可以由公理推出。课程没有在这里证明，但这是群论的第一批练习。

例子与非例子

为什么 $\mathbb Z_n\setminus\{0\}$ 在乘法下是群当且仅当 $n$ 是素数

若 $n$ 为素数，则是群。 封闭性来自模乘法的定义：两个余数相乘后再取余数，仍是余数。结合律继承自整数乘法。单位元是 $1$。唯一不平凡的是逆元：由上一讲的引理，当 $\gcd(a,n)=1$ 时 $a$ 有逆元；若 $n$ 是素数且 $a\in\{1,\dots,n-1\}$，则 $\gcd(a,n)=1$，所以每个非零元素都可逆。

若 $n$ 为合数，则不是群。 取 $n=pq$（$p,q>1$），则 $p\in\mathbb Z_n\setminus\{0\}$ 且 $\gcd(p,n)=p\ne1$。由同一引理的逆否命题，$p$ 没有乘法逆元，所以封闭的逆元公理失败。

这个例子说明：「是不是群」不只取决于集合，还取决于配了什么运算。

藏在里面的群

合数 $n$ 时，$\mathbb Z_n\setminus\{0\}$ 不是群，但其中有一个子集是群：

$$\mathbb Z_n^*=\{a\in\mathbb Z_n:\gcd(a,n)=1\}.$$

它对乘法封闭（两个与 $n$ 互素的数相乘仍与 $n$ 互素），单位元是 $1$，每个元素由引理保证有逆元，而逆元也与 $n$ 互素。所以 $\mathbb Z_n^*$ 是群。这个群在后面讲 RSA 时会反复出现。

群的阶与两个计数

有限群 $G$ 的阶记作 $|G|$，就是元素个数。

• $|\mathbb Z_p\setminus\{0\}|=p-1$（$p$ 素数）。
• $|\mathbb Z_{pq}^*|=(p-1)(q-1)$（$p\ne q$ 为素数）。

第二个用容斥：$1$ 到 $pq-1$ 共 $pq-1$ 个数，要减掉与 $pq$ 不互素的。不互素意味着被 $p$ 或 $q$ 整除。$q$ 的倍数有 $p-1$ 个（$q,2q,\dots,(p-1)q$），$p$ 的倍数有 $q-1$ 个，而 $pq$ 的倍数在范围内不存在。于是

$$|\mathbb Z_{pq}^*|=(pq-1)-(p-1)-(q-1)=pq-p-q+1=(p-1)(q-1).$$

这个数就是欧拉函数 $\varphi(pq)$。

子群

设 $H\subseteq G$。若 $H$ 在同一个运算下也构成群，就称 $H$ 是 $G$ 的子群。

关键是「更强的封闭性」：对 $a,b\in H$，不仅 $a*b\in G$（这由 $G$ 的封闭性自动成立），而且必须 $a*b\in H$；同样，$a^{-1}$ 也必须落在 $H$ 里。在 $H$ 内部做运算、求逆，永远不需要跑到 $G$ 的其余部分去。

例子。 $G=\mathbb Z_7\setminus\{0\}$，$|G|=6$。取 $H=\{1,2,4\}$。验证：$1\cdot2=2$，$1\cdot4=4$，$2\cdot4=8\equiv1$，都在 $H$ 内；$2^{-1}=4$，$4^{-1}=2$，$1^{-1}=1$。

更省力的看法：$H$ 正好是 $2$ 的幂次取模 $7$：

$$2^0=1,\qquad 2^1=2,\qquad 2^2=4,\qquad 2^3=8\equiv1.$$

幂次相乘等于指数相加，所以封闭性自动成立；$2^3=1$ 保证逆元存在（$2^1\cdot2^2=1$）。这是构造子群最常用的方式：取某个元素的全部幂。

Lagrange 定理

定理。 若 $G$ 是有限群，$H\le G$ 是子群，则 $|H|$ 整除 $|G|$。

这条定理的威力在于：它只用了群的四条公理，却对子群的可能大小给出了很强的限制。$|G|=6$ 时，子群的阶只能是 $1,2,3,6$；阶为 $4$ 或 $5$ 的子群根本不可能存在。

左陪集

对 $x\in G$，定义

$$xH=\{xh:h\in H\}.$$

这是把 $H$ 整体「平移」$x$ 得到的集合，称为 $x$ 的左陪集。若 $x\in H$，则 $xH=H$；若 $x\notin H$，则得到 $H$ 的一个平移副本。

证明的两步

计划。 证明 $G$ 可以写成若干个左陪集的不交并：

$$G=x_1H\;\dot\cup\;x_2H\;\dot\cup\cdots\dot\cup\;x_kH ,$$

其中每个陪集都与 $H$ 等大。于是 $|G|=k|H|$，整除性得证。

具体做法是贪心：从尚未覆盖的元素中任取一个作为 $x_1$，取走 $x_1H$；再从剩余元素中任取 $x_2$，取走 $x_2H$；如此继续。

第一步：每个陪集与 $H$ 等势。 定义映射 $h\mapsto xh$。它是单射：若 $xh_1=xh_2$，左乘 $x^{-1}$ 并用结合律，

$$x^{-1}(xh_1)=x^{-1}(xh_2) \;\Longrightarrow\; (x^{-1}x)h_1=(x^{-1}x)h_2 \;\Longrightarrow\; eh_1=eh_2 \;\Longrightarrow\; h_1=h_2 .$$

它是满射：陪集的定义就是所有 $xh$。所以 $|xH|=|H|$。这个论证用了逆元、结合律和单位元——群的公理在这里全部出场。

第二步：两个不同的陪集不相交。 设 $x_iH$ 与 $x_jH$ 有公共元素，即存在 $h_1,h_2\in H$ 使

$$x_ih_1=x_jh_2 .$$

右乘 $h_2^{-1}$：

$$x_j=x_ih_1h_2^{-1}.$$

因为 $H$ 是子群，$h_2^{-1}\in H$，再由 $H$ 的封闭性 $h_1h_2^{-1}\in H$。所以 $x_j\in x_iH$。

但 $x_j$ 是贪心过程中「尚未被覆盖」时选出的元素，而 $x_iH$ 已经被取走，覆盖了 $x_j$——矛盾。因此不同陪集不可能相交。

两步合起来：$G$ 被切成 $k$ 个互不相交、大小都是 $|H|$ 的块，故 $|G|=k|H|$，即 $|H|\mid|G|$。

费马小定理

定理。 若 $p$ 是素数，$p\nmid a$，则

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

推论。 $a^{p-2}$ 是 $a$ 模 $p$ 的乘法逆元：$a^{p-2}\cdot a=a^{p-1}\equiv1$。这是除扩展欧几里得之外的第二种求逆元方法，只需幂运算。

证明

设 $k$ 是最小的正整数使 $a^k\equiv1\pmod p$。

$k$ 存在。 考虑 $a^1,a^2,a^3,\dots$ 模 $p$ 的余数。余数只有 $p$ 种可能，而序列无限长，由鸽巢原理必有两个指数 $i<j$ 使

$$a^i\equiv a^j\pmod p .$$

因为 $p$ 是素数且 $p\nmid a$，$a$ 可逆，两边乘以 $a^{-i}$ 得

$$a^{j-i}\equiv1\pmod p .$$

取 $k=j-i$ 即可。这一步的关键是可逆性，而可逆性来自 $p$ 是素数。

幂次构成子群。 集合 $H=\{a^0,a^1,\dots,a^{k-1}\}$ 在乘法下封闭（指数相加，超过 $k$ 就减去 $k$），单位元是 $a^0=1$，逆元是 $a^{k-m}$。所以 $H$ 是子群，且 $|H|=k$——$k$ 的定义保证 $a^0,\dots,a^{k-1}$ 互不相同。

用 Lagrange 收尾。 $H\le\mathbb Z_p\setminus\{0\}$，而 $|\mathbb Z_p\setminus\{0\}|=p-1$。由 Lagrange 定理，$k\mid p-1$，设 $p-1=ck$。于是

$$a^{p-1}=a^{ck}=(a^k)^c\equiv1^c\equiv1\pmod p .$$

证明结束。注意整个论证只用了两件事：$a$ 可逆（保证 $k$ 存在）与 Lagrange 定理（保证 $k\mid p-1$）。

另一种证明：项链计数

费马小定理等价于 $p\mid a^p-a$（两边乘 $a$）。取 $a=2$、$p=5$ 做具体说明。

用红蓝两种珠子串成长度 $5$ 的项链（首尾相接），共有 $2^5=32$ 条串。把串首尾粘起来、旋转视为同一条项链。一条非单色项链旋转一次会得到 $5$ 条不同的串，因为 $5$ 是素数，非单色串没有非平凡的旋转对称；单色项链只有全红、全蓝两条，每条只对应 $1$ 条串。于是非单色串有 $32-2=30$ 条，被分成 $30/5=6$ 组。所以 $5\mid 2^5-2$。

一般地，$a$ 种珠子、长度 $p$ 的串有 $a^p$ 条，其中 $a$ 条是单色的，剩下 $a^p-a$ 条按每 $p$ 条一组分组，因此 $p\mid a^p-a$。这是同一个定理的纯组合证明。

欧拉定理

定理。 设 $m=pq$，$p\ne q$ 为素数，$\gcd(a,m)=1$，则

$$a^{(p-1)(q-1)}\equiv1\pmod m .$$

证明与费马小定理逐字相同，只需替换两处：

• 用 $\gcd(a,m)=1$ 保证 $a$ 在模 $m$ 下可逆，从而由鸽巢原理得到 $k$；
• 用 $|H|=k$ 与 Lagrange 定理，得到 $k\mid|\mathbb Z_m^*|=(p-1)(q-1)$。

所以指数从 $p-1$ 变成 $(p-1)(q-1)$，并不是新定理，而是同一证明中群的阶变了。这正是抽象的价值：两个看似不同的恒等式，在群的语言里是一个命题。

域与多项式根数（为后面铺垫）

域是带两个运算的集合 $F$：$(F,+)$ 是阿贝尔群（单位元 $0$），$(F\setminus\{0\},\cdot)$ 也是阿贝尔群（单位元 $1$），且满足分配律 $a(b+c)=ab+ac$。

定理（陈述）。 系数取自域 $F$ 的 $d$ 次多项式，在 $F$ 中最多有 $d$ 个根。

这解释了为什么「$d$ 次多项式最多 $d$ 个根」不是实数独有的性质，而是域的公理推出来的。后面的秘密共享方案正是利用这一点：把秘密藏在多项式的常数项里，用有限域上的求值点来分发份额。

本节结论

• 群 = 封闭 + 结合 + 单位元 + 逆元；再加交换律就是阿贝尔群。
• $\mathbb Z_n\setminus\{0\}$ 在乘法下是群，当且仅当 $n$ 是素数；合数时 $\mathbb Z_n^*$ 才是群。
• $|\mathbb Z_p\setminus\{0\}|=p-1$，$|\mathbb Z_{pq}^*|=(p-1)(q-1)$。
• Lagrange 定理：$|H|$ 整除 $|G|$；证明靠左陪集的分割。
• 费马小定理与欧拉定理是同一个证明，差别只在群的大小。
• $a^{p-2}$ 就是 $a$ 模 $p$ 的逆元。

理解检验

1. 证明：$\mathbb Z_n\setminus\{0\}$ 在乘法下是群当且仅当 $n$ 是素数。

参考答案：$n$ 素数时，封闭性、结合律、单位元 $1$ 都直接成立；对任意 $a\in\{1,\dots,n-1\}$，$\gcd(a,n)=1$，由扩欧引理存在 $b$ 使 $ab\equiv1$，故每个元素可逆。$n$ 合数时，写 $n=pq$ 且 $1<p,q<n$，则 $p$ 与 $n$ 不互素，由引理的逆否命题 $p$ 不可逆，逆元公理失败。

2. 计算 $|\mathbb Z_{pq}^*|$，并说明每一步计数的理由。

参考答案：候选集合是 $1,\dots,pq-1$，共 $pq-1$ 个。与 $pq$ 不互素的数恰是被 $p$ 或 $q$ 整除的数。$q$ 的倍数有 $q,2q,\dots,(p-1)q$ 共 $p-1$ 个；$p$ 的倍数有 $p,2p,\dots,(q-1)p$ 共 $q-1$ 个；两者没有交集，因为 $pq$ 不在范围内。故

$$|\mathbb Z_{pq}^*|=(pq-1)-(p-1)-(q-1)=(p-1)(q-1).$$

3. 证明每个左陪集 $xH$ 与 $H$ 等势。

参考答案：考虑映射 $\varphi:H\to xH$，$\varphi(h)=xh$。若 $\varphi(h_1)=\varphi(h_2)$，左乘 $x^{-1}$ 并由结合律得 $(x^{-1}x)h_1=(x^{-1}x)h_2$，即 $h_1=h_2$，所以是单射。按定义 $xH$ 的每个元素都形如 $xh$，所以是满射。故 $|xH|=|H|$。这里用到逆元、结合律、单位元三条公理。

4. 用 Lagrange 定理证明费马小定理，并指出「$k$ 存在」为什么需要鸽巢原理。

参考答案：设 $k$ 是最小的正整数使 $a^k\equiv1\pmod p$。鸽巢原理给出 $i<j$ 使 $a^i\equiv a^j$；因为 $p$ 素数且 $p\nmid a$，$a$ 可逆，两边乘 $a^{-i}$ 得 $a^{j-i}\equiv1$，所以 $k=j-i$ 存在。令 $H=\{a^0,\dots,a^{k-1}\}$，它对乘法封闭、含单位元、逆元为 $a^{k-m}$，是 $\mathbb Z_p\setminus\{0\}$ 的子群，且 $|H|=k$。由 Lagrange，$k\mid p-1$，写 $p-1=ck$，则 $a^{p-1}=(a^k)^c\equiv1$。

5. 一个群有 $6$ 个元素，能否有阶为 $4$ 的子群？阶为 $3$ 的呢？

参考答案：阶为 $4$ 的子群不可能，因为 $4\nmid6$，违反 Lagrange 定理。阶为 $3$ 的子群可能，因为 $3\mid6$（例如 $\mathbb Z_7\setminus\{0\}$ 中的 $\{1,2,4\}$ 是阶 $3$ 子群）。注意 Lagrange 定理只给出必要条件：$d\mid|G|$ 不保证一定存在阶为 $d$ 的子群。

与前后课的关系

上一讲用扩展欧几里得解决「求逆元」；本讲把可逆元素组织成群，用 Lagrange 定理一次推出费马与欧拉定理。下一讲离开代数，进入线性规划，但对偶理论会在后面以「零和博弈」的形式重新出现——那是群论之外的另一种结构。再往后讲到密码学时，$\mathbb Z_n^*$ 的阶 $(p-1)(q-1)$ 会成为 RSA 的全部秘密所在。

From "does an inverse exist?" to an abstract structure

The previous lecture asked: given $a$ and $n$, is there a $b$ with $ab\equiv1\pmod n$? The answer is decided by the greatest common divisor: such a $b$ exists exactly when $\gcd(a,n)=1$, and it can be found with the extended Euclidean algorithm.

This lecture looks at the same fact from a different angle: promote invertibility into a whole algebraic structure. Once the language of groups is in place, several theorems that look unrelated — Lagrange's theorem, Fermat's little theorem, Euler's theorem — become different spellings of one proof.

Timeline

Definition of a group

A group is a set $G$ with a binary operation $*$ satisfying four axioms:

1. Closure: $a,b\in G\Rightarrow a*b\in G$.
2. Associativity: $(a*b)*c=a*(b*c)$ for all $a,b,c\in G$.
3. Identity: there is $e\in G$ with $e*a=a*e=a$ for all $a$.
4. Inverse: for every $a\in G$ there is $a^{-1}\in G$ with $a^{-1}*a=a*a^{-1}=e$.

If in addition $a*b=b*a$ for all $a,b$, the group is abelian (commutative).

The axioms do not state that the identity or the inverse is unique — both follow from the axioms, and proving that is one of the first exercises in group theory.

Examples and non-examples

Why $\mathbb Z_n\setminus\{0\}$ is a group exactly when $n$ is prime

If $n$ is prime, it is a group. Closure follows from the definition of modular multiplication: a product of two residues, reduced again, is a residue. Associativity is inherited from integer multiplication. The identity is $1$. The only nontrivial axiom is the inverse: by the lemma from last lecture, $a$ has an inverse whenever $\gcd(a,n)=1$. For prime $n$ and $a\in\{1,\dots,n-1\}$ we have $\gcd(a,n)=1$, so every nonzero element is invertible.

If $n$ is composite, it is not a group. Write $n=pq$ with $p,q>1$. Then $p\in\mathbb Z_n\setminus\{0\}$ and $\gcd(p,n)=p\ne1$. By the contrapositive of the same lemma, $p$ has no multiplicative inverse, so the inverse axiom fails.

The lesson: being a group depends not only on the set but on the operation attached to it.

The group hiding inside

When $n$ is composite, $\mathbb Z_n\setminus\{0\}$ is not a group, but a subset of it is:

$$\mathbb Z_n^*=\{a\in\mathbb Z_n:\gcd(a,n)=1\}.$$

It is closed under multiplication (a product of two numbers coprime to $n$ is coprime to $n$), has identity $1$, and every element is invertible by the lemma; the inverse is also coprime to $n$. So $\mathbb Z_n^*$ is a group. It will reappear when we discuss RSA.

Order, and two counts

The order of a finite group $G$, written $|G|$, is its number of elements.

• $|\mathbb Z_p\setminus\{0\}|=p-1$ for prime $p$.
• $|\mathbb Z_{pq}^*|=(p-1)(q-1)$ for distinct primes $p,q$.

The second count is inclusion–exclusion. Start with the $pq-1$ numbers $1,\dots,pq-1$ and remove those not coprime to $pq$, i.e. multiples of $p$ or of $q$. The multiples of $q$ are $q,2q,\dots,(p-1)q$, giving $p-1$ of them; the multiples of $p$ are $p,2p,\dots,(q-1)p$, giving $q-1$. There is no overlap, because $pq$ is out of range. Hence

$$|\mathbb Z_{pq}^*|=(pq-1)-(p-1)-(q-1)=pq-p-q+1=(p-1)(q-1).$$

This number is Euler's totient $\varphi(pq)$.

Subgroups

Let $H\subseteq G$. If $H$ is itself a group under the same operation, it is a subgroup of $G$.

The key is a stronger closure: for $a,b\in H$ we need $a*b\in H$, not merely $a*b\in G$ (the latter is automatic). Likewise $a^{-1}$ must lie in $H$. Inside $H$ you never have to step outside $H$ to multiply or invert.

Example. Let $G=\mathbb Z_7\setminus\{0\}$, so $|G|=6$, and take $H=\{1,2,4\}$. Check: $1\cdot2=2$, $1\cdot4=4$, $2\cdot4=8\equiv1$, all in $H$; and $2^{-1}=4$, $4^{-1}=2$, $1^{-1}=1$.

A cleaner way to see it: $H$ is exactly the set of powers of $2$ modulo $7$:

$$2^0=1,\qquad 2^1=2,\qquad 2^2=4,\qquad 2^3=8\equiv1.$$

Multiplying powers adds exponents, so closure is automatic; $2^3=1$ supplies the inverses ($2^1\cdot2^2=1$). This is the standard way to build a subgroup: take all powers of one element.

Lagrange's theorem

Theorem. If $G$ is a finite group and $H\le G$ is a subgroup, then $|H|$ divides $|G|$.

Its power is out of proportion to its hypotheses: from four axioms it constrains which subgroup sizes can exist at all. If $|G|=6$, a subgroup can only have order $1,2,3$ or $6$; orders $4$ or $5$ are impossible.

Left cosets

For $x\in G$, define

$$xH=\{xh:h\in H\}.$$

This is $H$ translated by $x$, called a left coset. If $x\in H$ then $xH=H$; otherwise it is a shifted copy of $H$.

The two-step proof

Plan. Write $G$ as a disjoint union of left cosets,

$$G=x_1H\;\dot\cup\;x_2H\;\dot\cup\cdots\dot\cup\;x_kH ,$$

with every coset the same size as $H$. Then $|G|=k|H|$, which gives divisibility.

The cosets are produced greedily: pick any uncovered element as $x_1$ and remove $x_1H$; pick any still-uncovered element as $x_2$ and remove $x_2H$; continue.

Step 1: every coset has the same size as $H$. Consider $h\mapsto xh$. It is injective: if $xh_1=xh_2$, left-multiply by $x^{-1}$ and use associativity,

$$x^{-1}(xh_1)=x^{-1}(xh_2) \;\Longrightarrow\; (x^{-1}x)h_1=(x^{-1}x)h_2 \;\Longrightarrow\; eh_1=eh_2 \;\Longrightarrow\; h_1=h_2 .$$

It is surjective by definition of $xH$. Hence $|xH|=|H|$. This argument uses the inverse, associativity and the identity — all of the group axioms appear here.

Step 2: distinct cosets are disjoint. Suppose $x_iH$ and $x_jH$ share an element, so

$$x_ih_1=x_jh_2$$

for some $h_1,h_2\in H$. Right-multiply by $h_2^{-1}$:

$$x_j=x_ih_1h_2^{-1}.$$

Since $H$ is a subgroup, $h_2^{-1}\in H$ and, by closure, $h_1h_2^{-1}\in H$. Therefore $x_j\in x_iH$.

But $x_j$ was chosen as an element not yet covered, while $x_iH$ had already been removed and covers $x_j$ — a contradiction. So distinct cosets cannot intersect.

Together: $G$ is partitioned into $k$ disjoint blocks of size $|H|$, so $|G|=k|H|$ and $|H|\mid|G|$.

Fermat's little theorem

Theorem. If $p$ is prime and $p\nmid a$, then

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

Corollary. $a^{p-2}$ is the multiplicative inverse of $a$ mod $p$, since $a^{p-2}\cdot a=a^{p-1}\equiv1$. This gives a second way to invert, by exponentiation instead of the extended Euclidean algorithm.

Proof

Let $k$ be the smallest positive integer with $a^k\equiv1\pmod p$.

$k$ exists. Consider the residues of $a^1,a^2,a^3,\dots$ modulo $p$. There are only $p$ possible residues but infinitely many powers, so by the pigeonhole principle there are $i<j$ with

$$a^i\equiv a^j\pmod p .$$

Because $p$ is prime and $p\nmid a$, $a$ is invertible; multiply by $a^{-i}$:

$$a^{j-i}\equiv1\pmod p .$$

So $k=j-i$ works. The invertibility of $a$ — which comes from $p$ being prime — is what makes this step valid.

The powers form a subgroup. Let $H=\{a^0,a^1,\dots,a^{k-1}\}$. It is closed under multiplication (add exponents, reduce modulo $k$), contains the identity $a^0=1$, and the inverse of $a^m$ is $a^{k-m}$. Hence $H$ is a subgroup with $|H|=k$, since minimality of $k$ makes $a^0,\dots,a^{k-1}$ distinct.

Finish with Lagrange. $H\le\mathbb Z_p\setminus\{0\}$ and $|\mathbb Z_p\setminus\{0\}|=p-1$, so $k\mid p-1$. Write $p-1=ck$. Then

$$a^{p-1}=a^{ck}=(a^k)^c\equiv1^c\equiv1\pmod p .$$

Only two ingredients are used: invertibility of $a$ (so $k$ exists) and Lagrange's theorem (so $k\mid p-1$).

A second proof: counting necklaces

Fermat's little theorem is equivalent to $p\mid a^p-a$ (multiply both sides by $a$). Take $a=2$, $p=5$.

String $5$ beads, each red or blue, and join the ends to form a necklace; rotations count as the same necklace. There are $2^5=32$ strings. A non-monochromatic necklace comes from exactly $5$ different strings, because $5$ is prime and a non-constant string has no nontrivial rotational symmetry. The only monochromatic necklaces are all-red and all-blue, each coming from a single string. So $32-2=30$ strings split into $30/5=6$ groups, proving $5\mid2^5-2$.

In general, with $a$ bead colours and length $p$, there are $a^p$ strings, $a$ of them monochromatic, and the remaining $a^p-a$ group into blocks of $p$. Hence $p\mid a^p-a$ — the same theorem, proved combinatorially.

Euler's theorem

Theorem. Let $m=pq$ with distinct primes $p,q$, and suppose $\gcd(a,m)=1$. Then

$$a^{(p-1)(q-1)}\equiv1\pmod m .$$

The proof is the same as for Fermat's little theorem with two substitutions:

• $\gcd(a,m)=1$ makes $a$ invertible mod $m$, so the pigeonhole argument produces $k$;
• Lagrange applied to $H$ gives $k\mid|\mathbb Z_m^*|=(p-1)(q-1)$.

The exponent changes from $p-1$ to $(p-1)(q-1)$ not because the theorem is new, but because the order of the ambient group changed. That is the payoff of abstraction: two seemingly different identities are one statement in the language of groups.

Fields and the number of roots (groundwork)

A field is a set $F$ with two operations such that $(F,+)$ is an abelian group with identity $0$, $(F\setminus\{0\},\cdot)$ is an abelian group with identity $1$, and distributivity $a(b+c)=ab+ac$ holds.

Theorem (stated). A polynomial of degree $d$ with coefficients in a field $F$ has at most $d$ roots in $F$.

So "a degree-$d$ polynomial has at most $d$ roots" is not special to the reals; it follows from the field axioms. The secret-sharing scheme discussed later exploits exactly this: hide the secret in the constant term and hand out evaluations at points of a finite field.

What this lecture establishes

• A group is closure, associativity, identity and inverse; adding commutativity gives an abelian group.
• $\mathbb Z_n\setminus\{0\}$ is a group under multiplication iff $n$ is prime; for composite $n$ the group is $\mathbb Z_n^*$.
• $|\mathbb Z_p\setminus\{0\}|=p-1$ and $|\mathbb Z_{pq}^*|=(p-1)(q-1)$.
• Lagrange's theorem: $|H|$ divides $|G|$, proved by partitioning into left cosets.
• Fermat's little theorem and Euler's theorem are one proof; only the group order differs.
• $a^{p-2}$ is the inverse of $a$ modulo $p$.

Comprehension check

1. Prove that $\mathbb Z_n\setminus\{0\}$ is a group under multiplication if and only if $n$ is prime.

Reference answer: If $n$ is prime, closure, associativity and the identity $1$ are immediate; for any $a\in\{1,\dots,n-1\}$ we have $\gcd(a,n)=1$, so the extended-Euclid lemma gives $b$ with $ab\equiv1$, hence every element is invertible. If $n$ is composite, write $n=pq$ with $1<p,q<n$; then $p$ is not coprime to $n$, so by the contrapositive of the lemma $p$ is not invertible and the inverse axiom fails.

2. Compute $|\mathbb Z_{pq}^*|$ and justify each counting step.

Reference answer: The candidates are $1,\dots,pq-1$, giving $pq-1$ numbers. Those not coprime to $pq$ are precisely the multiples of $p$ or of $q$. The multiples of $q$ are $q,2q,\dots,(p-1)q$, so $p-1$ of them; the multiples of $p$ are $p,2p,\dots,(q-1)p$, so $q-1$. They are disjoint because $pq$ is out of range. Hence

$$|\mathbb Z_{pq}^*|=(pq-1)-(p-1)-(q-1)=(p-1)(q-1).$$

3. Prove that every left coset $xH$ has the same cardinality as $H$.

Reference answer: Consider $\varphi:H\to xH$, $\varphi(h)=xh$. If $\varphi(h_1)=\varphi(h_2)$, left-multiplying by $x^{-1}$ and using associativity gives $(x^{-1}x)h_1=(x^{-1}x)h_2$, i.e. $h_1=h_2$; so $\varphi$ is injective. It is surjective by the definition of $xH$. Hence $|xH|=|H|$. The proof uses the inverse, associativity and the identity.

4. Prove Fermat's little theorem using Lagrange's theorem, and explain why the existence of $k$ needs the pigeonhole principle.

Reference answer: Let $k$ be the least positive integer with $a^k\equiv1\pmod p$. Pigeonhole gives $i<j$ with $a^i\equiv a^j$; since $p$ is prime and $p\nmid a$, $a$ is invertible, so multiplying by $a^{-i}$ yields $a^{j-i}\equiv1$, and $k=j-i$ exists. Let $H=\{a^0,\dots,a^{k-1}\}$; it is closed under multiplication, contains the identity and has inverses $a^{k-m}$, so it is a subgroup of $\mathbb Z_p\setminus\{0\}$ of order $k$. Lagrange gives $k\mid p-1$; writing $p-1=ck$ gives $a^{p-1}=(a^k)^c\equiv1$.

5. A group has $6$ elements. Can it have a subgroup of order $4$? Of order $3$?

Reference answer: No subgroup of order $4$, since $4\nmid6$, contradicting Lagrange. A subgroup of order $3$ is possible since $3\mid6$ (for instance $\{1,2,4\}$ inside $\mathbb Z_7\setminus\{0\}$). Lagrange gives only a necessary condition: $d\mid|G|$ does not guarantee that a subgroup of order $d$ exists.

Relation to neighbouring lectures

The previous lecture solved "find the inverse" with the extended Euclidean algorithm; this lecture organises the invertible elements into a group and derives Fermat and Euler from Lagrange's theorem in one stroke. The next lecture leaves algebra for linear programming, but duality will return in the guise of zero-sum games — another structure altogether. Later, in cryptography, the order $(p-1)(q-1)$ of $\mathbb Z_n^*$ becomes the whole secret behind RSA.