4

抽象代数习题(21--23) -- 整数和数论基础

 2 years ago
source link: https://z-rui.github.io/post/2022/01/abstract-algebra-21/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

抽象代数习题(21–23) – 整数和数论基础

抽象代数习题(21–23) – 整数和数论基础

Thu Jan 27, 2022

《抽象代数》第二十一章到第二十三章主要研究整数的性质，因此和初等数论有比较大的重叠。我把它们的习题放在同一篇。

第二十一章讲的是一种最常见的整环：整数环 ℤ。整数环具备以下公理：

  • 有序性：两个整数 a 和 b 比较大小，结果一定是 a < b, a = b, a > b 三者之一。并且不等号满足通常的传递性、同向可加性和正数可乘性。
  • 良序性 (well-ordering property)：正整数集的非空子集必有最小元素。这个性质看起来是常识，并且在前面章节的许多证明中已经使用过了。由它还可以导出带余除法和数学归纳法原理。

事实上，满足这些性质的整环全都同构于 ℤ。可见整数环是一类非常特别的环。

B. 有序整环的更多性质

设 A 是有序整环。证明下列命题对于任意 a, b, c ∈ A 都成立。

B.1 a² + b² ≥ 2ab

证明 有序整环中，任意元素的平方总是非负的。因此有 (a-b)² ≥ 0。

于是 a² - 2ab + b² ≥ 0。两边加上 2ab 即得要证的不等式成立。

B.3 a² + b² + c² ≥ ab + bc + ac

引理

  1. 如果 a ≥ b 且 c ≥ d，那么 a + c ≥ b + d。可以根据习题 A.1 和 A.2 得到（略）。
  2. 如果 a + a ≥ b + b，那么 a ≥ b。用反证法易证。

证明 仿照 B.1 可得三个不等式

  1. a² + b² ≥ 2ab
  2. b² + c² ≥ 2bc
  3. a² + c² ≥ 2ac

根据引理 1，可以将三个不等式的两边分别相加，得 (a² + b² + c²) + (a² + b² + c²) ≥ (ab + bc + ac) + (ab + bc + ac)。 根据引理 2，得 a² + b² + c² ≥ ab + bc + ac。

B.5 当 a,b > 1 时，a + b < ab + 1

证明 由已知条件得 a - 1 > 0, b - 1 > 0。因此 (a-1)(b-1) > 0。 即 ab - a - b + 1 > 0。两边加上 (a + b) 得 ab + 1 > a + b，即 a + b < ab + 1。

E. 绝对值

对于任意有序整环，定义绝对值 |a| 为 |a|={aa≥0−aa<0 使用这个定义证明下列命题。

E.5 |a+b|≤|a|+|b|

证明一 不失一般性，设 |a|≤|b|。分类讨论：

  1. a>0,b>0，则 a=|a|,b=|b|,a+b>0。
  2. a>0,b<0，则 a=|a|,b=−|b|,a+b<0。
  3. a<0,b>0，则 a=−|a|,b=|b|,a+b>0。
  4. a<0,b<0，则 a=−|a|,b=−|b|,a+b<0。

因为 −|a|≤|a|，两边加上 |b| 得 |b|−|a|≤|a|+|b|。

  • 对于 1、4，有|a+b|=|a|+|b|；
  • 对于 2、3，有 |a+b|=|b|−|a|≤|a|+|b|。

综上所述，不论哪种情况总有 |a+b|≤|a|+|b|。

证明二 当 b≥0 时，|a|≤b 当且仅当 −b≤a≤b（习题 E.4，证略）。

在上式中用做代换 a↦a+b 和 b↦|a|+|b| 得 |a+b|≤|a|+|b|⟺−(|a|+|b|)≤a+b≤|a|+|b| 右边的不等式的成立的，因为 −|a|≤a≤|a| 且 −|b|≤b≤|b|，根据同向不等式可以相加即得。

因此，要证明的不等式成立。

E.8 |a|−|b|≤|a−b|

证明一 如果 |a|≤|b|，则 |a|−|b|≤0≤|a−b|。

下面只考虑 |a|>|b| 的情况。分类讨论：

  1. a>0,b>0，则 a=|a|,b=|b|,a−b>0。
  2. a>0,b<0，则 a=|a|,b=−|b|,a−b>0。
  3. a<0,b>0，则 a=−|a|,b=|b|,a−b<0。
  4. a<0,b<0，则 a=−|a|,b=−|b|,a−b<0。
  • 对于 1、3，有|a−b|=|a|+|b|≥|a|−|b|；
  • 对于 2、4，有 |a−b|=|a|−|b|。

综上所述，不论哪种情况总有 |a−b|≥|a|−|b|，所以要证的不等式成立。

证明二

在 E.5 的不等式中做代换 a↦a−b 得 |a|≤|a−b|+|b| 两边加上 −|b| 得 |a|−|b|≤|a−b| 证明完毕。

F. 带余除法问题

证明 1–3，其中 k, m, n, q, r 表示整数。

F.2 设 n > 0 且 k > 0。如果 q 是 m 除以 n 的商，且 q₁ 是 q 除以 k 的商，那么 q₁ 是 m 除以 nk 的商。

证明 根据已知条件有

  1. m = nq + r
  2. q = q₁k + r₁

其中的量都是整数，且 0 ≤ r < n，0 ≤ r₁ < k。消去 q 得

  • m = n(q₁k + r₁) + r = q₁(nk) + (nr₁+r)

因为 r₁ < k，所以 k - r₁ > 0。又因为整数集中，大于 0 的最小元素是 1，所以 k - r₁ ≥ 1。于是有 r₁ ≤ k-1。 又 n > 0，所以 nr₁ ≤ nk(k-1)。两边加上 r 得 nr₁+r ≤ nk - (n-r)。因为 r < n，所以 -(n-r) < 0，因此 nr₁+r ≤ nk - (n-r) < nk。显然又有 nr₁+r ≥ 0，所以 nr₁+r 是 m 除以 nk 得余数。根据带余除法结果的唯一性可知 q₁ 是 m 除以 nk 的商。

分解质因数

第二十二章讲的是整数的分解质因数。这一章的主要内容是初等数论的基础知识，包括：

  • 数的整除、因子、互质；最大公约数；质数和合数
  • Bézout 引理、欧几里得引理1、算术基本定理

B. 最大公约数的性质

证明下列命题对任意整数 a, b, c 都成立。

B.1 如果 a > 0 且 a | b，那么 gcd(a, b) = a。

证明

  1. a | a 且 a | b。
  2. 设 u 是整数且 u | a 且 u | b，那么 u | a。

以上两条符合最大公约数的定义，且 a > 0，因此 gcd(a, b) = a。

B.6 如果 gcd(ab, c) = 1，则 gcd(a, c) = 1 且 gcd(b, c) = 1。

证明 设 gcd(a, c) = g。根据最大公约数的定义可知 g | a。从而 g | ab。

对于 gcd(ab, c) = 1，根据最大公约数的定义可知：

  • 设 u 是整数且 u | ab 且 u | c，那么 u | 1。

取 u = g，则因为 g | ab，所以 g | 1。能整除 1 的正整数只有 1，所以 g = 1。

同理可证 gcd(b, c) = 1。

C. 互质整数的性质

证明下列各命题对任意整数 a, b, c, d, r, s 都成立。

C.1 如果存在整数 r, s 使得 ra + sb = 1，则 a 和 b 互质。

证明 根据 Bézout 引理，a 和 b 的线性组合都是 gcd(a, b) 的倍数。根据已知条件，gcd(a, b) | 1 ，所以只可能是 gcd(a, b) = 1。因此 a 和 b 互质。

C.2 如果 gcd(a, c) = 1 且 c | ab，那么 c | b。

证明 根据 Bézout 引理，存在整数 r, s 使得方程 ra + sc = 1 成立。两边乘以 b 得 rab + scb = b。因为 c | ab，所以存在整数 m 使得 ab = mc，于是 rmc + scb = b，即 (rm + sb)c = b。这说明 c | b。

C.3 如果 a | d 且 c | d，并且 gcd(a, c) = 1，那么 ac | d。

证明 根据 Bézout 引理，存在整数 r, s 使得方程 ra + sc = 1 成立。两边乘以 d 得 rad + scd = d。设 d = ma= nc，其中 m, n 是整数。代入得 ranc + scma = d，即 (rn + sm)ac = d。这说明 ac | d。

D. 最大公约数和互质整数的更多性质

证明下列命题对任意整数 a, b, c, d, r, s 都成立。

D.3 设 d = gcd(a,b)。对任意整数 x，d | x 当且仅当 x 是 a 和 b 的线性组合。

证明

（必要性）设 x = nd，其中 n 是整数。根据 Bézout 引理，存在整数 r, s 使得方程 ra + sb = d 成立。两边乘以 n 得 (rn)a + (sn)b = dn = x。这表明 x 是 a 和 b 的线性组合。

（充分性）根据 Bézout 引理，任何 a 和 b 的线性组合都是 d 的倍数。

E. 最大公约数的一个性质

设 a, b 是整数。证明 1–2。

E.1 设 a 是偶数，b 是奇数，或者反过来。那么 gcd(a, b) = gcd(a+b, a-b)。

证明 设 gcd(a, b) = g，则 g | a 且 g | b。于是 g | (a+b) 且 g | (a-b)。

设 gcd(a+b, a-b) = g'，则 g | g'。 此外，根据 Bézout 引理，存在整数 r, s 使得方程 ra + sb = g 成立。 那么 (r+s)(a+b) + (r-s)(a-b) = 2g。但是 a+b 和 a-b 都是奇数，所以一定有 r+s 和 r-s 都是偶数。

设 r' = (r+s)/2, s' = (r-s)/2，则有 r'(a+b) + s'(a-b) = g。 根据 D.3 知 g' | g。于是只可能是 g' = g。

E.2 设 a 和 b 都是奇数。那么 2gcd(a, b) = gcd(a+b, a-b)。

证明 类似 E.1 的推理。但此时 a+b 和 a-b 都是偶数。

设 a' = (a+b)/2, b' = (a-b)/2，则有 (r+s)a' + (r-s)b' = g。根据 D.3 知 gcd(a', b') | g。 从而有 g' = gcd(2a', 2b') = 2gcd(a', b') | 2g。

因为 a 和 b 都是奇数，所以 g 是奇数。但 g' 是偶数，所以 g' 不可能等于 g。因此只可能 g' = 2g。

E.3 如果 a 和 b 都是偶数，解释为什么上述两种结论都有可能。

答 推理过程类似 E.2，但是 g 和 g' 都是偶数，所以不能断言 g' ≠ g。因此 g' = g 和 g' = 2g 都有可能。

G. ℤ 中的理想

证明下列命题。

说明 此题似应排除平凡理想（对应 n = 0, ±1）的情况。按照参考资料的定义，⟨0⟩ 是素理想，但 ⟨1⟩ 不是素理想。

G.1 ⟨n⟩ 是素理想当且仅当 n 是素数。

证明 只讨论 n ≥ 2 的情况。

（必要性）假设 n 是合数，那么存在 1 < p < n 和 1 < q < n 使得 n = pq。因为 pq = n ∈ ⟨n⟩，根据素理想的定义有 p ∈ ⟨n⟩ 或 q ∈ ⟨n⟩。这和 n 是 ⟨n⟩ 中的最小正元矛盾。所以假设不成立，n 是素数。

（充分性）设 a, b ∈ ℤ 且 ab ∈ ⟨n⟩。那么存在 k ∈ ℤ 使得 ab = kn。即 n | ab。根据欧几里得引理，n | a 或者 n | b。于是 a ∈ ⟨n⟩ 或者 b ∈ ⟨n⟩。

G.2 任意素理想都是极大理想。

证明 设素理想 I = ⟨p⟩。根据 G.1 可知 p 是素数。

设 J 是 ℤ 的理想，且 I ⊊ J。那么，存在 a ∈ J 但 a ∉ I。

a ∉ I 意味着 p ∤ a。因为 p 的约数只有 1 和 p，所以 gcd(a, p) = 1。

根据 Bézout 引理，方程 ra + sp = 1 有整数解。因为 a ∈ J 且 p ∈ I ⊆ J，所以 ra ∈ J 且 sp ∈ J。由此可知 1 ∈ J。

于是对于任意的 x ∈ ℤ 有 x = 1x ∈ J。这表明 J = A。因此 I 是极大理想。

G.3 对于任意素数 p，ℤp 是域。

证明 由 G.1 知 ⟨p⟩ 是素理想。由 G.2 知 ⟨p⟩ 是极大理想。根据第十九章证明的命题“如果 J 是极大理想则 A/J 是域”，ℤp = ℤ/⟨p⟩ 是域。

G.5 每个 ℤ 的同态像都同构于某个 ℤn。

证明 设 f: ℤ → A，且它的核是 K。则 K 是 ℤ 的理想。 而 ℤ 的理想都是主理想，即 K = ⟨n⟩，其中 n 是整数。

根据同态基本定理，有 f(ℤ) ≅ ℤ/K = ℤn。这就是所要证明的。

G.6 设 G 是群且 a,b ∈ G。则 S = { n ∈ Z : abn = bna } 是 ℤ 的理想。

证明 显然 ab⁰ = b⁰a，所以 0 ∈ S。

设 x, y ∈ S。那么 abx = bxa，即 bx = a-1bxa。 同理有 by = a-1bya，求逆得 b-y = a-1b-ya。 于是 bx-y = a-1bx-ya，即 abx-y = bx-ya。这表明 (x-y) ∈ S，即 S 对减法封闭。

设 x ∈ S，则 bx = a-1bxa。对于任意 k ∈ ℤ，有 bkx = (bx)k = a-1bkxa，即 abkx = bkxa。这表明 xk = kx ∈ S，即 S 在 ℤ 中吸收乘法。

综上所述，S 是 ℤ 的理想。

第二十三章是可选章节，包含了初等数论的基础内容：

  • Fermat 定理、Euler 定理（它们是 Lagrange 定理在模 n 整数环中的特例）
  • 线性同余方程（组）
  • 中国剩余定理

习题部分额外引入了如下内容： Wilson 定理、二次剩余和原根。

A. 解同余方程

A.4 求解下列二次同余方程。（如果没有解，写“无解”。）

(f) 3x2−6x+6≡0(mod15)

解 或3x2−6x+6≡0(mod15)x2−2x+2≡0(mod5)x2−2x−3≡0(mod5)(x−3)(x+1)≡0(mod5)x≡3 或 x≡−1(mod5)

A.6 解下列丢番图1方程。（如果没有解，写“无解”。）

(d) 30x2+24y=18。

解 原方程等价于 5x2+4x=3。以 4 为模（注意 5≡1）得同余方程 x2≡3(mod4) 而在 Z4 中，平方等于 3 的数是不存在的，所以方程无解。

D. 同余的更多性质

证明下列命题对任意整数 a, b, c 和正整数 m, n 成立。

D.6 如果 ab ≡ 1 (mod c)，ac ≡ 1 (mod b)，且 bc ≡ 1 (mod a) ，那么 ab + bc + ac ≡ 1 (mod abc)。

根据已知条件可知存在整数 x, y, z 使得

  • ab - 1 = xc
  • bc - 1 = ya
  • ac - 1 = zb

三式相乘得 (ab-1)(bc-1)(ac-1) = (xyz)(abc)。

两边对 abc 取模。注意到左边的展开式中，任意两个带字母的项相乘总是含有因子 abc，所以和 0 同余。于是得 ab + bc + ac - 1 ≡ 0 (mod abc)。两边加 1 就得到要证的同余式。

E. Fermat 定理的结论

证明 2–6。

E.4 设 p 和 q 是不同的质数，则 pq-1 + qp-1≡ 1 (mod pq)。

证明 根据 Fermat 定理，当 p ≠ q 时有 pq-1 ≡ 1 (mod q)。所以存在整数 x 使得 pq-1 - 1 = xq。同理可证存在整数 y 使得 qp-1 - 1 = yp。

两式相乘得 (pq-1-1)(qp-1-1) = xypq。两边对 pq 取模，得 -pq-1 -qp-1 + 1 ≡ 0 (mod pq)。移项就得到要证的同余式。

E.6 设 p 和 q 是不同的质数。

  1. 如果 (p-1) | m 且 (q-1) | m，那么 am ≡ 1 (mod pq) 对任意满足 p∤a 且 q∤a 的整数 a 成立。
  2. 如果 (p-1) | m 且 (q-1) | m，那么 am+1 ≡ a (mod pq) 对任意整数 a 都成立。

证明(1) 当 p∤a 时，p 和 a 互质。根据 Fermat 定理有 am ≡ 1 (mod p)。于是存在整数 x 使得 am-1 = xp。同理可证存在整数 y 使得 am-1 = yq。

由 xp = yq 知 p | yq。但 p∤q，根据欧几里得引理知 p | y，即存在整数 z 使得 y = zp。

于是 am-1 = zpq。两边对 pq 取模得 am-1 ≡ 0 (mod pq)。移项就得到要证的同余式。

证明(2) 分类讨论：

  • 如果 p 和 q 均不整除 a，由 (1) 得 am ≡ 1 (mod pq)。两边乘 a 得 am+1 ≡ a (mod pq)。
  • 如果 p 和 q 中有且只有一个整除 a，不失一般性，设 p | a 且 q∤a。那么 a = kp，其中 k 是整数。根据 Fermat 定理有 am ≡ 1 (mod q)。因此存在整数 t 使得 am - 1 = tq。和 a = kp 相乘得 am+1 - a = ktpq。两边对 pq 取模，得 am+1 - a ≡ 0 (mod pq)。移项得 am+1 ≡ a (mod pq)。
  • 如果 p 和 q 均整除 a，那么 pq | a。所以 am+1 ≡ 0 ≡ a (mod pq)。

综上所述，要证的同余式总是成立。

F. Euler 定理的结论

F.8 如果 gcd(m,n)=1，证明 nϕ(m)+mϕ(n)≡1(modmn)。

证明 同 E.4。将其中的 Fermat 定理改为 Euler 定理即可。

G. Wilson 定理和相关结论

在任意整环中，如果 x2=1，那么 x2−1=(x+1)(x−1)=0；于是 x=±1。 因此，任意元素 x≠±1 都不可能是自己的乘法逆元。 由此得到一个结论：在 Zp 中，整数 2¯,3¯,…,p−2― 可以两两配对，每个元素都和自己的乘法逆元组成一对。

证明下列命题。

G.1 在 Zp 中，2¯⋅3¯⋯p−2―=1。

证明 可以把因子两两配对，每对由互逆的两个元素构成，从而乘积等于 1。因此所有因子的乘积等于 1。

G.2 (p−2)!≡1(modp) 对任意质数 p 都成立。

证明 容易验证当 p=2,3 时该同余式成立。当 p>3 时，由 G.1 立即得到。

G.3 (p−1)!+1≡0(modp) 对任意质数 p 都成立。这被称为 Wilson 定理。

证明 将 G.2 的同余式和 p−1≡−1(modp) 相乘再移项即可得到。

G.4 对于任意合数 n≠4，有 (n−1)!≡0(modn)。

证明 要证明该同余式，只需证明 n∣(n−1)! 即可。

因为 n 是合数，所以 n=ab，其中 1<a≤b<n。

  • 如果 a<b，那么 (n−1)!=(n−1)(n−2)⋯b⋯a⋯1 能被 ab 整除。
  • 如果 a=b，那么 n=a2。根据合数 n≠4 可知 a>2。因此 a<2a<a2=n。于是 (n−1)!=(n−1)(n−2)⋯(2a)⋯a⋯1 能被 a2 整除。

综上所述，(n−1)! 总能被 n 整除，因此命题得证。

G.9 对于任意质数 p>2，方程 x2≡−1(modp) 有解当且仅当 p≢3(mod4)。

证明 大于 2 的质数都是奇数。所以除以 4 的余数只可能是 1 或 3。分两个方面证明。

  1. 当 p≡1(mod4) 时方程有解。

因为 p−1≡−1p−2≡−2⋮p+22≡−p−12(modp) 全部相乘，并考虑此时 (p−1)/2 是偶数，得 (p−1)(p−2)⋯p+22≡(−1)p−12p−12⋯2⋅1=(p−12)!(modp) 于是 (p−1)!≡[(p−12)!]2(modp) 由 Wilson 定理知 (p−1)!≡−1(modp)，因此 [(p−12)!]2≡−1(modp) 这表明 x=(p−12)! 是方程 x2≡−1 的一个解。

  1. 当 p≡3(mod4) 时方程无解。

这时 (p−1)/2 是奇数。将方程两边求 (p−1)/2 次幂，得 xp−1≡−1(modp)。

  • 如果 p∣x，显然有 xp−1≡0(modp)；矛盾。
  • 如果 p∤x，根据 Fermat 定理，应当有 xp−1≡1(modp)；矛盾。

无论如何都得到矛盾，因此方程不可能有解。

H. 二次剩余

对于整数 a，如果存在整数 x 使得 x2≡a(modm)，则称为模 n 的二次剩余 (quadratic residue)。这等于说 a¯ 在 Zm 中是一个平方元素。如果 a 不是模 m 的二次剩余，则称 a 为模 m 的二次非剩余 (quadratic nonresidue)。二次剩余对于求解二次同余方程、研究平方数的和，等等，有重要作用。这里，我们考察模任意素数 p>2 的二次剩余。

设 h:Zp∗→Zp∗ 定义为 h(a¯)=a¯2。

[说明：Zp∗={1¯,2¯,…,p−1―} 是 Zp 中所有非零元素和乘法运算构成的群。]

H.1 证明 h 是同态且核为 {±1}。

证明 显然 Zp∗ 是 Abel 群。设 x,y∈Zp∗，则 h(xy)=(xy)2=x2y2=h(x)h(y) 因此 h 是同态。令 [h(x)]2=1。因为在 Zp 中满足 x2=1 的只有 x=±1，它们都在 Zp∗ 中，所以方程的解集是 {±1}，这也就是 h 的核。

H.2 h 的值域含有 (p−1)/2 个元素。证明：值域 R 是 Zp∗ 的子群且含有两个陪集。一个陪集包含所有剩余，另一个包含所有非剩余。

证明 显然 R 是 Zp∗ 的非空子集。

设 y1,y2∈R，则存在 x1,x2∈Zp∗ 使得 y1=x12,y2=x22。 因此 y1y2=(x1x2)2=h(x1x2)∈R。这说明 R 对乘法封闭。

又 R 是有限集，所以根据非空和对乘法封闭就可以判定（第五章习题 D.5）它是 Zp∗ 的子群。因为 Zp∗ 是 Abel 群，因此 R 是正规子群。

因为 R=R1 是一个陪集，而 |R|=(p−1)/2, |Zp∗|=p−1，所以陪集的个数为 (Zp∗:R)=p−1(p−1)/2=2。根据定义，R 中有且只有表示为 x2（其中 x∈Zp∗）的元素，即所有的二次剩余。所以另一个陪集中有且只有二次非剩余。

Legendre 符号定义如下： 如果且是模的剩余如果且是模的非剩余如果(ap)={+1如果 p∤a 且 a 是模 p 的剩余−1如果 p∤a 且 a 是模 p 的非剩余0如果 p∣a

H.3 参考 H.2，把 R 的两个陪集命名为 1 和 −1。那么 Zp∗/R={1,−1}。解释为什么对每个不是 p 的倍数的整数 a 都有 (ap)=Ra¯

说明 原书中似有排版错误（它将 Ra¯ 写成 h(a¯)；那样的话不成立）。

答 根据 H.2，包含所有剩余的陪集是 R，将它命名为 1；设包含所有非剩余的陪集是 Rn¯，其中 n¯ 是某个非剩余，将它命名为 −1。那么 是剩余是非剩余Ra¯={1a¯ 是剩余−1a¯ 是非剩余 当 p∤a 时，a¯∈Zp∗。对照 Legendre 符号的定义可知 (ap)=Ra¯。

另外说明，陪集之间的乘法满足如下运算规则： 1⋅1=1(−1)⋅1=1⋅(−1)=R(1⋅n¯)=−1(−1)⋅(−1)=R(n¯2)=1

H.4 求 (1723); (329); (511); (813); (223)。

解 计算得 (1723)=−1,(329)=−1,(511)=1,(813)=−1,(223)=1

H.5 求证：如果 a≡b(modp)，则 (ap)=(bp)。特别地，(a+kpp)=(ap)。

证明 在 Zp∗ 中，a¯=b¯。于是 Ra¯=Rb¯。根据 H.3 可知 (ap)=(bp)。代入 b=a+kp 即得特例。

H.6 求证： 当时，(a)(ap)(bp)=(abp)(b)当 p∤a 时，(a2p)=1

说明 原书中有排版错误，第二个等式右边的 1 是我凭猜测补上的。

证明 在 Zp∗ 中有 ab―=a¯b¯。因为 Ra¯⋅Rb¯=R(a¯b¯)=Rab―，根据 H.3 可知 (ap)(bp)=(abp)。 当 p∤a 时，(ap)=±1。于是 (a2p)=(ap)2=1。

H.7 求证：(−1p)={+1p≡1(mod4)−1p≡3(mod4)

证明 参见 G.9。结合二次剩余的定义即可得到结论。

用于计算 (ap) 的最重要的规则是二次互反律 (law of quadratic reciprocity)，它断言对于任意不相等的素数 p,q>2，有 如果不然(pq)={−(qp)如果 p≡q≡3(mod4)−(qp)不然 （其证明可以在任何一本数论教科书中找到，例如 W. J. LeVeque 的 Fundamentals of Number Theory。）

H.8 用 H.5–H.7 以及二次互反律计算： (30101)(10151)(1541)(1459)(379401) 14 是不是模 59 的二次剩余？

注 不能对含 2 的 Legendre 符号套用二次互反律的公式，否则计算结果不一定正确。可以使用 H.5 做加减法来避开因子 2。事实上，如果使用和一个 Legendre 符号有关的定理（二次互反律的第二补充）： 如果不然(2p)={+1如果 p≡±1(mod8)−1不然 则可以使计算更简便。对于本题，仅对第一个计算式使用 H.5 方法避开因子 2 作为示范，其余的使用以上补充条件。

解

  1. (30101)=(2101)(3101)(5101)=1，其中
    • (2101)=(−99101)=(−1101)(32101)(11101)=−1，其中
      • (−1101)=1（使用 H.7）
      • (32101)=1（使用 H.6(b)）
      • (10111)=(211)=(−911)=(−111)(3211)=−1（使用 H.7、H.6(b)）
    • (3101)=(1013)=(23)=−1
    • (5101)=(1015)=(15)=1
  2. (10151)=(2151)(5151)=1，其中
    • (2151)=1（第二补充）
    • (5151)=(1515)=(15)=1
  3. (1541)=(341)(541)=−1，其中
    • (341)=(413)=(23)=−1
    • (541)=(415)=(15)=1
  4. (1459)=(259)(759)=−1，其中
    • (259)=−1（第二补充）
    • (759)=−(597)=−(37)=(73)=(13)=1
  5. (379401)=(401379)=(22379)=(2379)(11379)=1，其中
    • (2379)=−1（第二补充）
    • (11379)=−(37911)=−(511)=−(115)=−(15)=−1

根据 (4) 可知 14 不是模 59 的二次剩余。

回忆 Vn 表示 Zn 中所有可逆元素构成的乘法群2。 如果 Vn 恰好是循环群，例如 Vn=⟨m⟩，那么任意整数 a≡m 称为 n 的原根 (primitive root)。

I.1 证明 a 是 n 的原根当且仅当 a¯ 在 Vn 中的阶是 ϕ(n)。

证明 乘法群 Vn 的阶是 ϕ(n)。a¯ 是 Vn 的生成元的充分必要条件是 ord⁡(a¯)=|Vn|=ϕ(n)（第十一章习题 C.5）。

I.2 证明每个素数 p 都有原根。

证明 因为 ℤp 是域。根据第三十三章定理 1，域的所有非零元素和乘法运算构成的群是循环群。那么循环群 ℤp* 的生成元就是原根。

注 这题用到了后面章节的定理；我自己并不能想出“域的所有非零元素和乘法运算构成循环群”的证明。

I.3 寻找下列整数的原根（如果不存在，请指出）： 6, 10, 12, 14, 15。

解

  • ℤ6* = {1, 5} = ⟨5⟩。所以 5 是 6 的原根。
  • ℤ10* = {1, 3, 7, 9} = ⟨3⟩ = ⟨7⟩。所以 3 和 7 是 10 的原根。
  • ℤ12* = {1, 5, 7, 11}。所有元素的阶均不超过 2，所以不存在生成元。因此 12 没有原根。
  • ℤ14* = {1, 3, 5, 9, 11, 13} = ⟨3⟩ = ⟨5⟩。所以 3 和 5 是 14 的原根。
  • ℤ15* = {1, 2, 4, 7, 8, 11, 13, 14}。所有元素的阶均不超过 4，所以不存在生成元。因此 15 没有原根。

I.4 假设 a 是 m 的原根。求证：如果 b 是和 m 互质的整数，那么 b≡ak(modm) 对某个 k≥1 成立。

证明 a 是 m 的原根意味着 Vm=⟨a¯⟩。当 b 和 m 互质时有 b¯∈Vm。因为 a¯ 是生成元，所以存在正整数 k 使得 b¯=a¯k=ak―。这意味着 b≡ak(modm)。

I.5 设 m 有原根，且 n 和 ϕ(m) 互质（假定 n>0）。证明：如果 a 和 m 互质，则 xn≡a(modm) 有解。

证明 设原根为 g，则 Vm=⟨g¯⟩。因为 a 和 m 互质，所以 a¯∈Vm。根据生成元定义，存在正整数 k 使得 a¯=g¯k。

因为 gcd(n,ϕ(m))=1，根据 Bézout 引理，方程 rn+sϕ(m)=k 有整数解。

于是有 a¯=g¯rn+sϕ(m)=(g¯r)n(g¯ϕ(m))s=(g¯r)n，因为 ord⁡(g)=ϕ(m)。设 x¯=g¯r，则有 a¯=x¯n。这表明存在整数 x 是 xn≡a(modm) 的解。

I.6 设 p>2 是质数。证明：p 的每个原根都是模 p 的二次非剩余。

证明 用反证法。设 g 是 p 的原根。假设 g 是模 p 的二次剩余，那么 (gp)=1，于是 (gnp)=(gp)n=1。这意味着 Zp∗ 中的所有元素都是二次剩余。这是不可能的，因为我们已经知道 Zp∗ 中恰有一半的元素是二次剩余（习题 H.2）。所以假设不成立，原命题成立。

I.7 形如 p=2m+1 的质数 p 称为 Fermat 质数。设 p 是一个 Fermat 质数。证明每个模 p 的二次非剩余都是 p 的原根。

证明 根据 I.2 知 Zp∗={1¯,2¯,…,2m―}=⟨g¯⟩ 是循环群，其中 g¯ 是某个生成元。那么，g¯ 的阶是 2m。

设 a 是模 p 的二次非剩余。则 a¯∈Zp∗ 是二次非剩余。根据生成元定义，存在正整数 r 使得 a¯=g¯r。这里 r 只能是奇数，否则 a¯=(g¯r/2)2 就是二次剩余。

设 a¯ 的阶为 n，根据 Lagrange 定理，有 n∣2m。根据阶的定义，有 a¯n=g¯nr=1¯。于是 nr 一定是 g 的阶的倍数，也即 2m∣nr。但是 r 是奇数，所以只可能是 2m∣n。这意味着 n=2m，即 a¯ 的阶等于 Zp∗ 的阶，所以 a¯ 是生成元。

因此，二次非剩余 a 是模 p 的原根。

  1. 欧几里得、丢番图是约定俗成的译名。它们的希腊文名字是 Ευκλειδης 和 Διόφαντος。 ↩︎

  2. 另一种常见的记法是 (Z/nZ)×。 ↩︎


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK