[latexpage]
Soal Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg$(p(x)) < 3$, deg$(q(x)) < 2$, dan
\begin{align*}
p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1.
\end{align*}
Selidiki apakah $p(x)^2 + q(x)$ irredusibel di $GF_2[x]$.
Pembahasan
Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg$(p(x)) < 3$, deg$(q(x)) < 2$, dan
\begin{align*}
p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1.
\end{align*}
Misalkan $p(x) = ax^2 + bx + c$ dan $q(x) = mx + n$; $a, b, c, m, n \in GF_2$.
Substitusikan $p(x) = ax^2 + bx + c$ dan $q(x) = mx + n$ ke persamaan $p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1$, diperoleh
\begin{align*}
(ax^2 + bx + c)&(1 + x + x^3) + (mx + n)(1 + x + x^2 + x^4) = 1\\
&\iff ax^2 + bx + c + ax^3 + bx^2 + cx + ax^5 + bx^4 + cx^3 + mx + n + mx^2 + nx + mx^3 + nx^2 + mx^5 + nx^4 = 1\\
&\iff (a + m)x^5 + (b + n)x^4 + (a + c + m)x^3 + (a + b + m + n)x^2 + (b + c + m + n)x + (c + n) = 1.
\end{align*}
Didapatkan sistem persamaan linear di $GF_2$ sebagai berikut.
$a + m = 0, \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (1)$
$b + n = 0, \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (2)$
$a + c + m = 0, \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (3)$
$a + b + m + n = 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (4)$
$b + c + m + n = 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (5)$
$c + n = 1. \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (6)$
Dari $(3) + (1)$, diperoleh $c = 0. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (7)$
Dari $(6) + (7)$, diperoleh $n = 1. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (8)$
Dari $(2) + (8)$, diperoleh $b = 1. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (9)$
Dari $(5) + (7) + (8) + (9)$, diperoleh $m = 0. \; \qquad \qquad \qquad \qquad \qquad \ldots (10)$
Dari $(1) + (10)$, diperoleh $a = 0.$
Akibatnya, $p(x) = x$ dan $q(x) = 1$, sehingga $p(x)^2 + q(x) = x^2 + 1$.
Perhatikan bahwa, jika $x = 1$, maka $p(1)^2 + q(1) = 1^2 + 1 = 0$.
Dengan demikian, $p(x)^2 + q(x) \boxed{\text{redusibel}}$ di $GF_2[x]$.
Versi 2
Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg$(p(x)) < 3$, deg$(q(x)) < 2$, dan
\begin{align*}
p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1.
\end{align*}
Untuk memenuhi deg$(p(x)) < 3$ dan deg$(q(x)) < 2$, dimisalkan
\begin{align*}
&p(x)= ax^2+bx+c;
&q(x)= mx+n.
\end{align*}
Selanjutnya, dilakukan subtitusi sebagai berikut.
\begin{align*}
p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) &= 1 \\
(ax^2+bx+c)(1+x+x^3)+(mx+n)(1+x+x^2+x^4) &=1 \\
(ax^2+ax^3+ax^5+bx+bx^2+bx^4+c+cx+cx^3) \\+ (mx+mx^2+mx^3+mx^5+n+nx+nx^2+nx^4)&=1\\
ax^5+bx^4+ax^3+cx^3+ax^2+bx^2+bx+cx+c\\+mx^5+nx^4+mx^3+mx^2+nx^2+mx+nx+n&=1 \\
(a+m)x^5+(b+n)x^4+(a+c+m)x^3 \\+(a+b+m+n)x^2+(b+c+m+n)x+(c+n)&=1
\end{align*}
Kemudian, diperoleh sistem persamaan linear di $GF_2$ sebagai berikut.
\begin{align}
a+m&=0 \\
b+n&=0 \\
a+c+m&=0 \\
a+b+m+n&=0 \\
b+c+m+n&=0 \\
c+n&=1
\end{align}
Berdasarkan $(1)$: $m=a$. \\
Berdasarkan $(2)$: $n=b$. \\
Subtitusi $m=a$ ke $(3)$ dan diperoleh:
\begin{align*}
a+c+a&=0\\2a+c&=0\\c&=0
\end{align*}
Subtitusi $n=b$ ke $(6)$ dan diperoleh:
\begin{align*}
c+n&=1 \\ c&=1+n.
\end{align*}
Karena $c=0$ maka $n=1$ dan karena $n=b$ maka $n=b=1$. \\
Kemudian dari $(4)$ diperoleh
\begin{align*}
a+1+0+1&=0 \\a&=0
\end{align*}
Kemudian dilakukan verifikasi ke $(4)$ dengan
\begin{equation*}
a = 0;\quad b = 1;\quad c = 0;\quad m = 0;\quad n = 1
\end{equation*}
\begin{equation*}
0 + 1 + 0 + 1 = 0
\end{equation*}
Diperoleh solusi untuk $p(x)$ dan $q(x)$ sebagai berikut.
\begin{align*}
p(x)&=ax^2+bx+c\\
&=(0)x^2+(1)x+0\\
&=x \\
q(x)&=mx+n \\
&=(0)x+1 \\
&=1
\end{align*}
Selanjutnya akan diselidiki apakah $p(x)^2+q(x)$ irreducible di $GF_2[x]$.
\begin{align*}
p(x)^2+q(x)=x^2+1
\end{align*}
Apabila $p(x)^2+q(x)$ irreducible di $GF_2[x]$, maka $p(x)^2+q(x)$ tidak memiliki akar di $GF_2$. Dilakukan pengujian sebagai berikut.
Jika $x=0$ : $0^2+1=1$
Jika $x=1$ : $1^2+1=1+1=0$.
Diperoleh bahwa $x=1$ adalah akar dari $x^2+1$. Artinya:
\begin{align*}
x^2+1=(x+1)(x+1)=(x+1)^2
\end{align*}
Dengan demikian, diperoleh kesimpulan bahwa $p(x)^2 + q(x) \boxed{\text{reducible}}$ di $GF_2[x]$.
Video Penjelasan:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]