整域せいいきintegral domain・体たいfield・有限体ゆうげんたいfinite field 基本きほん演習えんしゅう

integral domains整域せいいき, fields体たい, and finite fields有限体ゆうげんたい: basic exercises

1対応たいおうする講義こうぎ

1Corresponding lectures

2取とり組くむ順序じゅんじょ

「整域せいいき・零因子れいいんし・多項式環たこうしきかん」の後あとは問題もんだい1・4に取とり組くめる。「体たいの基本きほん」の後あとに問題もんだい2・3と証明演習しょうめいえんしゅうへ進すすみ、「有限体ゆうげんたいの入口いりぐち」の後あとに問題もんだい5を行おこなう。証明演習しょうめいえんしゅうは本文ほんぶんでは問題もんだい5の後あとに置おいているが、問題もんだい5には依存いぞんしない。このページの prerequisites は全問題ぜんもんだいに取とり組くむための最終到達点さいしゅうとうたつてんを表あらわす。

2Suggested order

After “Integral domains, zero divisors, and polynomial rings,” complete Problems 1 and 4. After “Field basics,” continue with Problems 2–3 and the proof exercise. After “Introduction to finite fields,” complete Problem 5. Although the proof exercise appears after Problem 5 on this page, it does not depend on Problem 5. The page prerequisites describe what is needed to complete the whole page.

3関連かんれん演習えんしゅう

3Related exercises

4問題もんだい1：零因子れいいんしを見みつける

$$\mathbb{Z}/8\mathbb{Z}$$\mathbb Z/8\mathbb Z で零因子れいいんしを一ひとつ見みつけよ。

4Problem 1: find a zero divisor零因子れいいんし

Find one zero divisor零因子れいいんし in $$\mathbb{Z}/8\mathbb{Z}$$\mathbb Z/8\mathbb Z.

4.1解答かいとう

$$\left[2\right]$$[2] は零因子れいいんしである。実際じっさい、

であり、$$\left[2\right]\ne \left[0\right]$$[2]\ne[0]、$$\left[4\right]\ne \left[0\right]$$[4]\ne[0] である。

4.1Answer

$$\left[2\right]$$[2] is a zero divisor零因子れいいんし. Indeed,

and $$\left[2\right]\ne \left[0\right]$$[2]\ne[0], $$\left[4\right]\ne \left[0\right]$$[4]\ne[0].

4.2解説かいせつ

零因子れいいんしは、0 でない元げんelementどうしの積せきproductを 0 にしてしまう元げんelementである。

4.2Explanation

A zero divisor零因子れいいんし is an element that makes the product of two nonzero elements become 0.

5問題もんだい2：体たいfieldか判定はんていする

$$\mathbb{Z}/7\mathbb{Z}$$\mathbb Z/7\mathbb Z は体たいfieldか。

5Problem 2: decide whether it is a field体たい

Is $$\mathbb{Z}/7\mathbb{Z}$$\mathbb Z/7\mathbb Z a field体たい?

5.1解答かいとう

体たいfieldである。7 は素数そすうprime numberなので、0 でない任意にんいの $$\left[a\right]$$[a] について $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,7)=1$$\gcd(a,7)=1 である。ベズーの等式Bezout identityにより、ある整数せいすう $$u,v$$u,v が存在そんざいして

となる。したがって剰余類じょうよるいでは $$\left[a\right]\left[u\right]=\left[1\right]$$[a][u]=[1] であり、乗法逆元じょうほうぎゃくげんmultiplicative inverseが存在そんざいする。また、$$\mathbb{Z}/7\mathbb{Z}$$\mathbb Z/7\mathbb Z は剰余類じょうよるいの加法かほうと乗法じょうほうについて可換環かかんかんであり、$$7\nmid 1$$7\nmid1 なので $$\left[0\right]\ne \left[1\right]$$[0]\ne[1] である。よって体たいの定義ていぎの全条件ぜんじょうけんを満みたす。

5.1Answer

Yes. Since 7 is prime, for every nonzero $$\left[a\right]$$[a] we have $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,7)=1$$\gcd(a,7)=1. By the Bezout identityベズーの等式, there exist integers $$u,v$$u,v such that

Therefore, in residue classes, $$\left[a\right]\left[u\right]=\left[1\right]$$[a][u]=[1], so a multiplicative inverse乗法逆元じょうほうぎゃくげん exists. Moreover, $$\mathbb{Z}/7\mathbb{Z}$$\mathbb Z/7\mathbb Z is a commutative ring under residue-class addition and multiplication, and $$7\nmid 1$$7\nmid1 gives $$\left[0\right]\ne \left[1\right]$$[0]\ne[1]. Thus all conditions in the definition of a field are satisfied.

5.2解説かいせつ

$$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z が体たいfieldになるのは、$$n$$n が素数そすうprime numberのときである。

5.2Explanation

The ring $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z is a field体たい exactly when $$n$$n is prime.

6問題もんだい3：体たいfieldでない例れいを説明せつめいする

$$\mathbb{Z}/9\mathbb{Z}$$\mathbb Z/9\mathbb Z が体たいfieldでない理由りゆうを説明せつめいせよ。

6Problem 3: explain a non-field体たい example

Explain why $$\mathbb{Z}/9\mathbb{Z}$$\mathbb Z/9\mathbb Z is not a field体たい.

6.1解答かいとう

$$\left[3\right]\ne \left[0\right]$$[3]\ne[0] だが、

である。したがって零因子れいいんしがあるので体たいfieldではない。

6.1Answer

Although $$\left[3\right]\ne \left[0\right]$$[3]\ne[0],

Thus there is a zero divisor零因子れいいんし, so it is not a field体たい.

6.2解説かいせつ

体たいfieldには零因子れいいんしがない。一般いっぱんに $$n=ab$$n=ab、$$1<a,b<n$$1<a,b<n と分解ぶんかいできる合成数ごうせいすう $$n$$n では、$$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z の中なかで

となり、しかも $$\left[a\right]\ne \left[0\right]$$[a]\ne[0]、$$\left[b\right]\ne \left[0\right]$$[b]\ne[0] である。したがって合成数ごうせいすう法ほうの剰余じょうよ環かんでは、合成数ごうせいすうの因子いんしから零因子れいいんしが生しょうじる。

6.2Explanation

A field体たい has no zero divisors零因子れいいんし. In general, if a composite number $$n$$n factors as $$n=ab$$n=ab with $$1<a,b<n$$1<a,b<n, then in $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z,

while $$\left[a\right]\ne \left[0\right]$$[a]\ne[0] and $$\left[b\right]\ne \left[0\right]$$[b]\ne[0]. Thus, in a residue ring modulo a composite number, zero divisors零因子れいいんし arise from factors of the composite number.

7問題もんだい4：多項式たこうしきの積せきと次数じすう

$$f\left(x\right)=2x^2+1$$f(x)=2x^2+1、$$g\left(x\right)=3x-4$$g(x)=3x-4 を $$\mathbb{Z}\left[x\right]$$\mathbb Z[x] の元げんとする。$$f\left(x\right)g\left(x\right)$$f(x)g(x) を計算けいさんし、最高次係数さいこうじけいすうと次数じすうを求もとめよ。また、$$\text{[PARSE ERROR: Undefined("Command("deg")")]}\left(fg\right)=\text{[PARSE ERROR: Undefined("Command("deg")")]}f+\text{[PARSE ERROR: Undefined("Command("deg")")]}g$$\deg(fg)=\deg f+\deg g を確認かくにんせよ。

7Problem 4: products and degrees of polynomials

Let $$f\left(x\right)=2x^2+1$$f(x)=2x^2+1 and $$g\left(x\right)=3x-4$$g(x)=3x-4 be elements of $$\mathbb{Z}\left[x\right]$$\mathbb Z[x]. Compute $$f\left(x\right)g\left(x\right)$$f(x)g(x), find its leading coefficient and degree, and verify $$\text{[PARSE ERROR: Undefined("Command("deg")")]}\left(fg\right)=\text{[PARSE ERROR: Undefined("Command("deg")")]}f+\text{[PARSE ERROR: Undefined("Command("deg")")]}g$$\deg(fg)=\deg f+\deg g.

7.1解答かいとう

である。最高次係数さいこうじけいすうは 6、次数じすうは 3 である。また、$$\text{[PARSE ERROR: Undefined("Command("deg")")]}f=2$$\deg f=2、$$\text{[PARSE ERROR: Undefined("Command("deg")")]}g=1$$\deg g=1 なので

を確認かくにんできる。

7.1Answer

The leading coefficient is 6 and the degree is 3. Since $$\text{[PARSE ERROR: Undefined("Command("deg")")]}f=2$$\deg f=2 and $$\text{[PARSE ERROR: Undefined("Command("deg")")]}g=1$$\deg g=1,

7.2解説かいせつ

$$\mathbb{Z}$$\mathbb Z は整域せいいきなので、0 でない最高次係数さいこうじけいすう $$2$$2 と $$3$$3 の積せき $$6$$6 は 0 にならない。このことが積せきの最高次さいこうじの項こうが消きえないことを保証ほしょうしている。

7.2Explanation

Because $$\mathbb{Z}$$\mathbb Z is an integral domain, the product 6 of the nonzero leading coefficients 2 and 3 is nonzero. This prevents the highest-degree term of the product from disappearing.

8問題もんだい5：4 元げんの有限体ゆうげんたい

$$F_4=F_2\left[x\right]/(x^2+x+1)$$\mathbb F_4=\mathbb F_2[x]/(x^2+x+1) とし、$$\alpha =\left[x\right]$$\alpha=[x] と書かく。$${\alpha }^2=\alpha +1$$\alpha^2=\alpha+1 と $$1+1=0$$1+1=0 を使つかって、0 でない元げん $$1,\alpha ,\alpha +1$$1,\alpha,\alpha+1 の乗法表じょうほうひょうを完成かんせいさせよ。さらに、その表ひょうから各元かくげんの乗法逆元じょうほうぎゃくげんを読よみ取とれ。

8Problem 5: the four-element finite field

Let $$F_4=F_2\left[x\right]/(x^2+x+1)$$\mathbb F_4=\mathbb F_2[x]/(x^2+x+1) and write $$\alpha =\left[x\right]$$\alpha=[x]. Using $${\alpha }^2=\alpha +1$$\alpha^2=\alpha+1 and $$1+1=0$$1+1=0, complete the multiplication table for the nonzero elements $$1,\alpha ,\alpha +1$$1,\alpha,\alpha+1. Then read the multiplicative inverse of each element from the table.

8.1解答かいとう

単位元たんいげん $$1$$1 を掛かけた積せきは元げんを変かえない。残のこる積せきは

および

である。ここで標数ひょうすう 2 より $$2\alpha =0$$2\alpha=0、$$1+1=0$$1+1=0 を使つかった。乗法じょうほうの可換性かかんせいも使つかうと、表ひょうは

となる。各行かくぎょうで積せきが $$1$$1 になる列れつを読よめば、

である。

8.1Answer

Multiplication by the identity $$1$$1 leaves every element unchanged. The remaining products are

Also,

where we used $$2\alpha =0$$2\alpha=0 and $$1+1=0$$1+1=0 in characteristic 2. Together with commutativity, these calculations give

In each row, the column whose product is $$1$$1 gives the inverse. Therefore

8.2解説かいせつ

$$\mathbb{Z}/4\mathbb{Z}$$\mathbb Z/4\mathbb Z では $$[2{]}^2=0$$[2]^2=0 だが、$$F_4$$\mathbb F_4 の 0 でない元げん $$1,\alpha ,\alpha +1$$1,\alpha,\alpha+1 はすべて逆元ぎゃくげんを持もつ。この違ちがいが、元げんの個数こすうだけでは体たいかどうかを決きめられないことを示しめす。

8.2Explanation

In $$\mathbb{Z}/4\mathbb{Z}$$\mathbb Z/4\mathbb Z, $$[2{]}^2=0$$[2]^2=0, whereas every nonzero element $$1,\alpha ,\alpha +1$$1,\alpha,\alpha+1 of $$F_4$$\mathbb F_4 has an inverse. Thus the number of elements alone does not determine whether a ring is a field.

9証明しょうめい演習えんしゅう：有限整域ゆうげんせいいきが体たいfieldになること

9Proof exercise: every finite integral domain整域せいいき is a field体たい

9.1問題もんだい

有限ゆうげんな整域せいいきintegral domain $R$R は体たいfieldであることを証明しょうめいせよ。

9.1Problem

Prove that a finite integral domain整域せいいき $$R$$R is a field体たい.

9.2解答かいとう

$a\in R$a\in R、$a\ne 0$a\ne0 を取とる。写像しゃぞう ${\mu }_a:R\to R$\mu_a:R\to R を ${\mu }_a\left(x\right)=ax$\mu_a(x)=ax で定義ていぎする。${\mu }_a\left(x\right)={\mu }_a\left(y\right)$\mu_a(x)=\mu_a(y) なら $ax=ay$ax=ay である。$R$R は整域せいいきintegral domainなので消去法則しょうきょほうそくより $x=y$x=y である。したがって ${\mu }_a$\mu_a は単射たんしゃである。

$R$R は有限集合ゆうげんしゅうごうなので、$R$R から $R$R への単射たんしゃは全射ぜんしゃである。よって $1\in R$1\in R に対たいして、ある $x\in R$x\in R が存在そんざいして $ax=1$ax=1 である。つまり $a$a は逆元ぎゃくげんinverse elementを持もつ。$$a$$a は任意にんいの 0 でない元げんであり、整域せいいき $$R$$R は $$0\ne 1$$0\ne1 の可換環かかんかんなので、$$R$$R は体たいである。

9.2Answer

Take $$a\in R$$a\in R with $$a\ne 0$$a\ne0. Define the map $${\mu }_a:R\to R$$\mu_a:R\to R by $${\mu }_a\left(x\right)=ax$$\mu_a(x)=ax. If $${\mu }_a\left(x\right)={\mu }_a\left(y\right)$$\mu_a(x)=\mu_a(y), then $$ax=ay$$ax=ay. Since $$R$$R is an integral domain整域せいいき, cancellation gives $$x=y$$x=y. Therefore $${\mu }_a$$\mu_a is injective単射たんしゃ.

Because $$R$$R is finite, every injective単射たんしゃ map from $$R$$R to $$R$$R is surjective全射ぜんしゃ. Hence for $$1\in R$$1\in R, there exists $$x\in R$$x\in R such that $$ax=1$$ax=1. Thus $$a$$a has an inverse. Since $$a$$a was an arbitrary nonzero element and the integral domain $$R$$R is a commutative ring with $$0\ne 1$$0\ne1, the ring $$R$$R is a field.

9.3解説かいせつ

有限性ゆうげんせいは単射たんしゃから全射ぜんしゃを導みちびくために使つかう。無限むげんの整域せいいきintegral domainでは、この議論ぎろんはそのままでは使つかえない。

有限集合ゆうげんしゅうごうでは、単射たんしゃなら像ぞうの元げん数すうが入力にゅうりょくの元げん数すうと同おなじである。入力にゅうりょくと目標もくひょうが同おなじ有限集合ゆうげんしゅうごうなので、像ぞうは目標もくひょう全体ぜんたいになり、全射ぜんしゃである。

9.3Explanation

Finiteness is used to derive surjectivity from injectivity. In an infinite integral domain整域せいいき, this argument cannot be used as it stands.

For a finite set, injectivity means that the image has the same number of elements as the input. Since the input and target are the same finite set here, the image must be the whole target, so the map is surjective.