トップ› 九州大学› 2000年› 理系第1問

九州大学 2000年理系第1問解説

方針・初手

問題の操作（偶数の係数を $0$、奇数の係数を $1$ に置き換える）は、各次数の係数について $2$ で割った余りを考えることと同じです。したがって、2つの整式 $A(x)$ と $B(x)$ が「おきかえによって等しくなる（合同である）」ことを $A(x) \equiv B(x)$ と表すことにすると、これは「各次数の係数の偶奇が一致する」ことを意味します。整式の和や積の係数は、展開前の係数の和や積から決まるため、$A(x) \equiv B(x)$ かつ $C(x) \equiv D(x)$ ならば $A(x)C(x) \equiv B(x)D(x)$ が成り立ちます。つまり、展開の前と後どちらで係数を置き換えても結果は等しくなります。

また、任意の整式 $P(x)$ について、以下の性質が成り立ちます。

$P(0)$ の値は定数項であり、その偶奇は定数項の偶奇と一致する。
$P(1)$ の値は全係数の和であり、その偶奇は全係数の和の偶奇と一致する。

もし $P(x) \equiv Q(x)R(x)$ ならば、$P(0)$ と $Q(0)R(0)$ の偶奇、および $P(1)$ と $Q(1)R(1)$ の偶奇は一致します。この性質を利用して、可約か既約かを判定していきます。

解法1

(1)

$f(x) = x^2+x+1$ とする。 $f(x)$ が可約であると仮定すると、2つの1次以上の M 多項式の積と合同になる。$f(x)$ は2次式なので、1次の M 多項式とある1次の M 多項式の積と合同になる。最高次の係数が $1$ であることから、1次の M 多項式は $x$ と $x+1$ の2つのみである。これらを $g(x)$ とすると、$g(0)=0$（偶数）または $g(1)=2$（偶数）となるため、$g(0)$ と $g(1)$ の少なくとも一方は偶数となる。ゆえに、$f(x) \equiv g(x)R(x)$ となる整式 $R(x)$ が存在するならば、$f(0)$ と $f(1)$ の少なくとも一方は偶数とならなければならない。しかし、$f(0) = 1$（奇数）、$f(1) = 3$（奇数）であり、いずれも偶数ではないため矛盾する。したがって、$x^2+x+1$ はいかなる1次の M 多項式の積とも合同にならず、既約な M 多項式である。

(2)

各次数の M 多項式について調べる。

(i) 1次の M 多項式 1次以上の2つの M 多項式の積は2次以上となるため、1次の M 多項式はすべて既約である。よって、$x$ と $x+1$ は既約である。

(ii) 2次の M 多項式 2次式が可約ならば、(1) と同様に1次の M 多項式とある多項式の積と合同になるため、$P(0)$ か $P(1)$ の少なくとも一方が偶数になる。逆に、$P(0)$ と $P(1)$ がともに奇数となる M 多項式は既約である。 $P(0)$ が奇数となるのは、定数項が $1$ のときである。2次の M 多項式で定数項が $1$ のものは $x^2+1$ と $x^2+x+1$ である。

$P(x) = x^2+1$ のとき、$P(1) = 2$（偶数）なので可約である。
$P(x) = x^2+x+1$ のとき、$P(1) = 3$（奇数）なので (1) より既約である。

よって、2次では $x^2+x+1$ のみ既約である。

(iii) 3次の M 多項式 3次の M 多項式が可約である場合、(1次式)$\times$(2次式) または (1次式)$\times$(1次式)$\times$(1次式) の形と合同になるため、少なくとも1つの1次の M 多項式と合同な因数を持つ。よって2次の場合と同様に、$P(0)$ と $P(1)$ がともに奇数であることが既約であるための必要十分条件となる。定数項が $1$ （すなわち $P(0)$ が奇数）である3次の M 多項式は、以下の4つである。

$P(x) = x^3+1$ のとき、$P(1) = 2$（偶数）なので可約である。
$P(x) = x^3+x+1$ のとき、$P(1) = 3$（奇数）なので既約である。
$P(x) = x^3+x^2+1$ のとき、$P(1) = 3$（奇数）なので既約である。
$P(x) = x^3+x^2+x+1$ のとき、$P(1) = 4$（偶数）なので可約である。

よって、3次では $x^3+x+1$ と $x^3+x^2+1$ が既約である。

(3)

4次の M 多項式 $Q(x) = x^4+x+1$ について考える。 $Q(0) = 1$（奇数）、$Q(1) = 3$（奇数）であるから、(1)や(2)の議論と同様に $Q(x)$ は1次の M 多項式といかなる多項式の積とも合同にならない。 $Q(x)$ が可約であると仮定すると、1次の因数を持たないことから、2つの「2次の既約な M 多項式」の積と合同になるしかない。 (2) の結果より、2次の既約な M 多項式は $x^2+x+1$ のみであるから、$Q(x)$ が可約ならば $(x^2+x+1)^2$ と合同になる。

$$\begin{aligned} (x^2+x+1)^2 &= x^4 + x^2 + 1 + 2x^3 + 2x^2 + 2x \\ &= x^4 + 2x^3 + 3x^2 + 2x + 1 \end{aligned}$$

この整式の偶数の係数を $0$ で、奇数の係数を $1$ でおきかえた M 多項式は $x^4+x^2+1$ である。これは $Q(x) = x^4+x+1$ と等しくないため、$(x^2+x+1)^2$ とは合同でない。ゆえに、$Q(x)$ はいかなる1次以上の M 多項式の積とも合同にならない。したがって、$x^4+x+1$ は既約な M 多項式である。

解説

本問は、有限体（要素数が有限個の体）$\mathbb{F}_2$ 上の多項式の因数分解を題材とした問題です。$\mathbb{F}_2$ においては、係数の足し算や掛け算をすべて $2$ で割った余りの世界で処理します。「合同」を「係数の偶奇が一致する」ことと捉えれば、実数係数の多項式で因数定理を使うのと同じように、$x=0$ と $x=1$ を代入して値の偶奇を調べる手法が非常に有効です。 $n$ 次式が可約であるかの判定において、2次式や3次式であれば「必ず1次の因数を持つ」ため代入だけで判定が完結しますが、4次式になると「2次式と2次式の積」に分解される可能性も考慮しなければならない点が(3)の重要な着眼点です。