2. 数论基础

模算术（Modular Arithmetic）是数论的一个分支，a 与 b 模 n 同余：\(a \equiv b \mod n\),表示 a-b = kn, k 为大于等于 1 的整数。 a 与 b 的关系称同余关系，n 叫做模数。

\(a+b \equiv c \mod p\): 如果 a 和 b 是任意的整数，p 是一个正整数，c 是一个非负整数，且 (a+b)÷p 的余数等于 c÷p 的余数.

对于模数 n，与 a 同余的所有整数集合成为同余类 Congruence class，用 \(\bar a_{n}\) 表示。模数要是整数的原因是为了保证模运算的良好性质，如唯一性、封闭性、消去律等

贝祖等式/定理

对于任意两个大于 1 的正整数 a 和 b，它们的最大公约数（GCD）与最小公倍数（LCM）的乘积等于这两个数的乘积。即：\(GCD(a,b) * LCM (a,b) = a * b\)

模算术的性质

模运算满足：反身性，对称性，传递性，加法性，减法性，乘法性，除法性，幂运算性

如果 a≡b (mod q) 且 c≡d (mod q)

加法性：a+c≡b+d (mod q)
减法性：a-c≡b-d (mod q)
乘法性：a×c≡b×d (mod q)。
除法性：如果 a≡b(mod n) 且 c 和 n 互素，那么 a/c ≡ b/c(mod n)。
幂运算性：如果 a≡b(mod n)，那么对于任意的正整数 k，都有 \(a^k≡b^k(mod n)\)。
消去律：如果 \(ac \equiv bc \mod n，c \ne 0, and gcd(c,n) = 1\), 则有 \(a \equiv b \mod n\)

模运算的逆运算：找到一个整数 b，使得 \(ab \equiv 1 \mod n\)，其中 a 和 n 是已知的整数。这个整数 b 就叫做 a 关于 n 的模逆元。

剩余类 (Residue class)

设 n > 0, 对于每个整数 a，定义：\([a] = \{x| x \equiv a \mod n\}\), [a] 是模 n 同余于 a 的所有整数的集合, 称 [a] 为 a 模 n 的同余类, a 是 the class representative

In other words, [𝑎] is the set of all integers that are congruent to 𝑎 modulo n. We call [𝑎] the residue class of 𝑎 modulo 𝑚. The integer a is called the class representative.

I/(n): 模 n 的所有同余类的集合，We denote the set of all residue classes modulo n by I/(n). 例如: \(I/(4) = { [0]_4, [1]_4, [2]_4, [3]_4}\) 和 \(I/(n) = { [0]_n, [1]_n, [2]_n, ... ,[n-1]_n}\)

注意: I/(n) 是集合(同余类)的集合

简化剩余类(reduced residue class)是 m 的剩余系中与 m 互素的数构成的子集

Since we can’t cancel numbers that aren’t prime to the modulus, we sometimes want to omit these numbers from our complete residue system, and consider only representatives from the various congruence classes that are relatively prime to m. This is called a reduced residue system mod m.

Z/nZ

The set of congruence classes mod n is called the set of integers modulo n, and denoted Z/nZ.

Many authors write Zn for Z/nZ, but this conflicts with other notation in number theory. (Some people just write Z/n.)

Warning: the elements of Z/nZ are congruence classes, not integers. Each element is a set of integers. For example, \(Z/4Z = \{[0]_4, [1]_4, [2]_4, [3]_4\}\). This is not a subset of Z.

费马小定理

假如 a 是一个整数 , p 是一个质数，且 gcd(a, p) = 1, 那么 \(a^{p-1} \equiv 1 \mod p\)

证明: 如果 p 为质数，那么一定有 residue class=\(\{[1]_p,[2]_p,[3]_p,[4]_p,[5]_p,…,[p-1]_p\}\)，因为互质，所以需要 p-1 步遍历所有的点，就是在 p-1 步的时候回到原位置，所以\(a^{p-1} \equiv 1 \mod p\)。

欧拉定理

对于正整数 n，欧拉函数（Euler's function）是小于 n 的正整数中与 n 互质的数的个数。通常表示为 \(\varphi(n)\). 其有对应的计算函数（复杂略过），三个常用性质：

如果 n 为质数，\(\varphi(n) = n-1\)
如果 m, n 互质，则 \(\varphi(mn) = \varphi(m)\varphi(n)\)
如果 p 是一个质数，k 是大于等于 1 的正整数，则 \(\varphi(p^k) = p^{k-1}\varphi(p) = p^{k-1}*(p-1)\)

模 n 的(本)原根 prime root、primitive root、primitive element

a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. In formula, \(m \equiv g^i mod n\), \(m \in \{m|gcd(m,n) = 1\}\)

对于模数 n 的每个互质数 a，都存在一个整数 k 满足：\(g^k \equiv a \mod n\), 称 g 为模 n 的原根。g, as a primitive root modulo n, is also called the generator of the multiplicative group of integers modulo n.

不是每个数都有原根，只有当 n 等于 2,4,p^k,2pk, 其中 p 为奇质数时，n 才有原根。所以对应群论，并不是所有的有限 n 阶群在模 n 算数下都可以形成循环群。[^1]

对于 n 为素数的情况，For prime n, g is a primitive root of prime n if and only if the results of g^i mod n is distinct and congruent to [1,n-1], which is congruent to n, i in [1, phi(n)=n-1]. that is \(g^1, g^2,...g^{n-1}\) are distinct and equals to [1,n-1].

Why prime root is called generator？

The relevant (and cool) fact is this: if 𝑔 is a primitive root modulo 𝑛 (so that 𝑔 has multiplicative order 𝜙(𝑛) modulo 𝑛), then every integer in the world that is relatively prime to 𝑛 is congruent modulo 𝑛 to some power of 𝑔. In other words, the powers of 𝑔 "generate" the entire set of reduced residue classes modulo 𝑛. (In terms of groups: the multiplicative group of reduced residue classes modulo 𝑛 is cyclic, and 𝑔 is a generator for that cyclic group.)

原根生成了所有与 n 互素的数的集合，也就是简化剩余类，简化剩余类的元素可以组成乘法群，从而原根就是生成元,而且是循环群的生成元，也就是可以通过原根一个元素生成整个循环群。

群的生成元

a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination (under the group operation) of finitely many elements of the subset and their inverses.

Generating set of a group 生成元集合 (g_1,...,g_n) 是群元素的集合，对于循环群来说，一个生成元便可生成整个群，该生成元即为模 n 的原根。对于其他非循环的有限群来说，存在生成元，但不存在可以单独生成整个群的一个生成元。通过生成元集合生成有限群。

A set of generators (g_1,...,g_n) is a set of group elements that can be used to generate all the elements in the group through repeated application of the generators and their inverses. Cyclic groups can be generated as powers of a single generator, but for all other groups, you'll need more than one generator.

参考资料

6. Primitive Roots - YouTube