[latexpage]

Soal Let $GF_{2^4}$, proof that $f(x) = x^4 + x + 1$ is the minimum function.

Pembahasan

Lapangan \( GF_{2^4} \) adalah lapangan hingga yang memiliki \( 2^4 = 16 \) elemen. Lapangan ini merupakan ekstensi dari lapangan dasar \( GF(2) \), yang terdiri dari dua elemen: \{0, 1\}.

Untuk membangun \( GF(2^4) \), kita memerlukan sebuah polinomial tak tereduksi (irreducible polynomial) derajat 4 atas \( GF(2) \). Jika \( f(x) \) adalah polinomial seperti itu, maka:
\[GF(2^4) \cong GF(2)[x]/(f(x))\] read more

[latexpage]

Soal 

Diberikan lapangan hingga dengan banyak anggota 8 yang dikontruksikan dari irreducible polynomial $f(x) = x^{3} + x^{2} + 1$ atas $GF(2)$:

1. Buktikan bahwa $f(x)$ irreducible pada $GF(2)[x]$
2. Jika $\alpha$ merupakan akar dari $f(X)$, cari elemen-elemen lapangan polinomialnya
3. Konstruksikan tabel Zech’s log untuk lapangan tersebut

Pembahasan

Diberikan $f(x) = x^{3} + x^{2} + 1$ atas $GF_{2}$
\begin{enumerate}[(a)]
\item \textbf{Cara 1}: Andaikan $f(x)$ reducible atas $GF_{2}[x]$, artinya terdapat $x^2+ax+b, x+c \in GF_{2}[x]$ yang memenuhi
\begin{align*}
f(x) &= (x^2 + ax + b)(x + c) \\
&= x^3 + (a + c)x^2 + (ac + b)x + bc \\
& = x^3 + x^2 + 1
\end{align*}
Akibatnya, diperoleh persamaan-persamaan berikut
\begin{align*}
a+c=1\:& \ldots(1) \\
ac+b=0\:& \ldots(2) \\
bc = 1\:& \ldots(3)
\end{align*}
Diperhatikan bahwa dari persamaan $(3)$ yaitu $bc = 1$, diperoleh $b = c = 1$. Selanjutnya, $b=c=1$ disubstitusikan ke persamaan $(1)$, diperoleh
\begin{alignat*}{2}
\qquad&
a + c&= 1 \\
\iff& a + 1 &= 1\\
\iff& a=0
\end{alignat*}
Kemudian substitusikan $a=0$ dan $b=c=1$ ke persamaan $(2)$, diperoleh
\begin{align*}
ac + b &= 0\cdot1 + 1\\
&=1 \\
& \ne 0
\end{align*}
Oleh karena $ac + b = 1 \ne 0$, maka terjadi kontradiksi. Pengandaian diingkar, jadi $f(x) = x^{3} + x^{2} + 1$ irreducible pada $GF_{2}[x]$. read more

[latexpage]

Soal Diberikan lapangan hingga $F_8$ yang dikonstruksikan dari polinomial irredusibel $f(x) = 1 + x + x^3$ atas $GF_2[x]$. Diketahui bahwa $\alpha$ merupakan elemen primitif dari $F_8$. Tunjukkan bahwa $\alpha^5$ juga merupakan elemen primitif dari $F_8$.

Pembahasan

Diberikan lapangan hingga $F_8$ yang dikonstruksikan dari polinomial irredusibel $f(x) = 1 + x + x^3$ atas $GF_2[x]$. Diketahui bahwa $\alpha$ merupakan elemen primitif dari $F_8$. Akan ditunjukkan bahwa $\alpha^5$ juga merupakan elemen primitif dari $F_8$.
Diketahui bahwa $\alpha$ merupakan elemen primitif, sehingga $1 + \alpha + \alpha^3=0$.
Artinya $\mathbb{F}_8 \setminus \{0\} = \{\alpha^0 = 1, \alpha, \alpha^2, \ldots, \alpha^6\}$, dengan
\begin{align*}
\alpha^{0}&=1\\
\alpha^1&=\alpha\\
\alpha^2&=\alpha^2\\
\alpha^3&=\alpha+1\\
\alpha^4&=\alpha^2+\alpha\\
\alpha^5&=\alpha^2+\alpha+1\\
\alpha^6&=\alpha^2+1 .
\end{align*}
Untuk sebarang bilangan bulat positif $k$, dapat dipandang bahwa $\alpha^k=\alpha^{7s+b}$ dengan $7s+b=k$ dan $0\leq b <7$. Dalam hal ini
\begin{align*}
\alpha^k=\alpha^{7s+b}=\alpha^{7s}\alpha^{b}=1\alpha^b=\alpha^b.
\end{align*}
Diperoleh
\begin{align*}
(\alpha^5)^{0}&=\alpha^0=1\\
(\alpha^5)^{1}&=\alpha^5\\
(\alpha^5)^{2}&=\alpha^{10}=\alpha^3\\
(\alpha^5)^{3}&=\alpha^{15}=\alpha\\
(\alpha^5)^{4}&=\alpha^{20}=\alpha^6\\
(\alpha^5)^{5}&=\alpha^{25}=\alpha^4\\
(\alpha^5)^{6}&=\alpha^{30}=\alpha^2
\end{align*}
Dengan demikian, $\alpha^5$ merupakan $\boxed{\text{elemen primitif}}$ dari $F_8$. read more

[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$. read more

[latexpage]

Soal Diberikan sistem persamaan linear di $GF_{11}$ sebagai berikut.
\begin{align*}
2x_1 + 7x_2 + x_3 – 6x_4 = 0, \\
5x_1 – 10x_2 – x_3 + 3x_4 = -1, \\
x_1 – 8x_2 + 4x_3 + 8x_4 = 3, \\
9x_1 + 6x_2 – 9x_3 + x_4 = -8.
\end{align*}
Tentukan nilai dari $5x_1 – 2x_2 + 11x_3 – 5x_4$.

Pembahasan

Diberikan sistem persamaan linear di $GF_{11}$ sebagai berikut.
\begin{align*}
2x_1 + 7x_2 + x_3 – 6x_4 = 0, \\
5x_1 – 10x_2 – x_3 + 3x_4 = -1, \\
x_1 – 8x_2 + 4x_3 + 8x_4 = 3, \\
9x_1 + 6x_2 – 9x_3 + x_4 = -8.
\end{align*}
Perhatikan bahwa, sistem persamaan tersebut dapat diubah menjadi
$2x_1 + 7x_2 + x_3 + 5x_4 = 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (1)$
$5x_1 + x_2 + 10x_3 + 3x_4 = 10, \qquad \qquad \qquad \qquad \qquad \qquad \quad \qquad \ldots (2)$
$ x_1 + 3x_2 + 4x_3 + 8x_4 = 3, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (3)$
$9x_1 + 6x_2 + 2x_3 + x_4 = 3. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (4)$
Dari $(1) + (2) + (3) + (4)$, diperoleh persamaan $(5)$:
\begin{align*} & \qquad
\quad 17x_1 + 17x_2 + 17x_3 + 17x_4 = 16 \\
&\iff 6x_1 + 6x_2 + 6x_3 + 6x_4 = 5 \\
&\iff 3x_1 + 3x_2 + 3x_3 + 3x_4 = 8 \\
&\iff x_1 + x_2 + x_3 + x_4 = 10.
\end{align*}
Dari $(1) – (5)$, diperoleh $x_1 + 6x_2 + 4x_4 = 1. \qquad \qquad \qquad \qquad \ldots (6)$
Dari $(2) – (5)$, diperoleh $4x_1 + 9x_3 + 2x_4 = 0. \qquad \qquad \qquad \qquad \ldots (7)$
Dari $(3) – (5)$, diperoleh $2x_2 + 3x_3 + 7x_4 = 4. \qquad \qquad \qquad \qquad \ldots (8)$
Dari $(4) – (5)$, diperoleh $8x_1 + 5x_2 + x_3 = 4. \; \qquad \qquad \qquad \qquad \ldots (9)$
Dari $(6) – (7) – (8) + (9)$, diperoleh
\begin{align*} & \qquad
\quad 5x_1 + 9x_2 + 6x_4 = 1 \\
&\iff 5x_1 – 2x_2 + 11x_3 – 5x_4 = 1.
\end{align*}
Jadi, nilai dari $5x_1 – 2x_2 + 11x_3 – 5x_4$ adalah $\boxed{1}$. read more

[latexpage]

Soal Suppose that $R$ is an integral domain with identity. Suppose that $I$ and $J$ are ideals in $R$ and that $I=\langle b \rangle$, where $b \in R$. Prove that $I+J=R$ if and only if $b+J$ is a unit in the ring $R/J$.

Pembahasan

Diberikan $R$ daerah integral dengan identitas, $I$ dan $J$ ideal di $R$, serta $I = \langle b \rangle$ untuk suatu $b \in R$.

$(\Longrightarrow)$ Diberikan $I+J=R$. Oleh karena $1_R \in R$, terdapat elemen $i \in I$ dan $j \in J$ sehingga $i+j=1_R$. Oleh sebab $I = \langle b \rangle$, maka dapat dituliskan $i=rb$ untuk suatu $r \in R$. Akibatnya $rb+j=1_R$. Diperhatikan bahwa $rb+J=rb+j +J$ Selanjutnya, diperoleh
\begin{align*}
1_R+J = rb+j+J=rb + J = (r+J)(b+J)
\end{align*}
Oleh sebab $1_{R/J}= 1_R+J$ dan $R$ ring komutatif, didapat
$(r+J)(b+J)=1_{R/J} \quad \text{dan} \quad (b+J)(r+J)=br+J=rb+J=1_{R/J}$.
Dari hasil di atas, diperoleh bahwa $b+J$ merupakan elemen unit di ring $R/J$. read more

[latexpage]

Soal Misalkan $S = \{1, 2, 3\}$ dan $P(S)$ adalah himpunan kuasa dari $S$. Didefinisikan dua operasi biner pada $P(S)$ sebagai berikut:
Untuk setiap $A, B \in P(S)$,
\[
A + B = (A \cup B) – (A \cap B), \quad A \cdot B = A \cap B.
\]
Tunjukkan bahwa $(P(S), +, \cdot)$ merupakan sebuah ring komutatif.

Pembahasan

1. $P(S) = \{\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\} .$Diambil sebarang $X,Y \in P(S)$. Artinya, $X,Y \subseteq S$. Diperoleh
   \begin{align*}
   X+Y=(X \cup Y) – (X \cap Y) \subseteq S.
   \end{align*}
2. Diambil sebarang $X,Y,Z \in P(S)$. Berlaku
   \begin{align*}
   (X+Y)+Z&= ((X \cup Y) – (X \cap Y)) + Z\\
   &= [((X \cup Y) – (X \cap Y)) \cup Z]\\
   &\hspace{0.7cm}-[((X \cup Y) – (X \cap Y)) \cap Z]\\
   &=[((X \cup Y) \cap (X \cap Y)^C) \cup Z]\\
   &\hspace{0.7cm}-[((X \cup Y) \cap (X \cap Y)^C) \cap Z]\\
   &=[(X \cup Y \cup Z) \cap ((X \cap Y)^C \cup Z)]\\
   &\hspace{0.7cm}-[((X \cup Y) \cap (X \cap Y)^C) \cap Z]\\
   &=[(X\cup Y\cup Z)\cap (X^C\cup Y^C\cup Z)]\\
   &\hspace{0.7cm}-[(X\cup Y)\cap (X^C\cup Y^C)\cap Z]\\
   &=[( (X\cap Y^C)\cup (X\cap Z)\cup(Y\cap X^C)\cup\\
   &\hspace{0.7cm} (Y\cap Z)\cup (Z\cap X^C)\cup (Z\cap Y^C)\cup Z)\cap \\
   &\hspace{0.7cm}-\{\}\\
   &\hspace{0.7cm}-[((X\cup Y)\cap (X^C\cup Y^C))\cap Z]\\
   &\hspace{0.7cm}….\\
   &=[(X \cup ((Y \cup Z) \cap (Y \cap Z)^C))]\\
   &\hspace{0.7cm}- [X \cap ((Y \cup Z) \cap (Y \cap Z)^C)]\\
   &=[(X \cup ((Y \cup Z) – (Y \cap Z)))]\\
   &\hspace{0.7cm}- [X \cap ((Y \cup Z) – (Y \cap Z))]\\
   &=X+((Y \cup Z) – (Y \cap Z))\\
   &=X+(Y+Z)
   \end{align*}
3. Terdapat $\{\} \in P(S)$, sehingga untuk setiap $X \in P(S)$, berlaku
   \begin{align*}
   \{\} + X=(\{\} \cup X)-(\{\}\cap X)=X-\{\}=X\cap P(S)=X , \\
   X + \{\} =(X \cup \{\} )-(X \cap \{\})=X-\{\}=X\cap P(S)=X.
   \end{align*}
4. Untuk setiap $X\in P(S)$, terdapat $X^{-1}=X\in P(S)$ sehingga berlaku
   \begin{align*}
   X+X^{-1}&=X+X\\
   &=(X\cup X)-(X\cap X)\\
   &=(X\cup X)\cap(X^C\cup X^C)\\
   &=X\cap X^C\\
   &=\{\}
   \end{align*}
   dan
   \begin{align*}
   X^{-1}+X&=X+X=\{\}
   \end{align*}
   Untuk setiap $X,Y\in P(S)$, berlaku
   \begin{align*}
   X+Y&=(X\cup Y)-(X\cap Y)\\
   &=(Y\cup X)-(Y\cap X)\\
   &=Y+X .\\
   \end{align*}

Jadi, $(P(S),+)$ merupakan grup komutatif.
Untuk menunjukkan sebuah ring komutatif, dapat dilihat dari tabel Cayley.

Video Penjelasan:

[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt] read more

File Tayangan

[latexpage]

Soal: Buktikan $4 \times 2^n | a^{2^n}-1$, untuk setiap a bilangan ganjil dan $n \in \mathbb{N}$.

Pembahasan:

Karena $a$ bilangan ganjil, maka $a$ dapat dinyatakan $2p-1$, $\forall p \in \mathbb{N}$. Maka Soal dapat ditulis menjadi $2^{n+2} | (2p-1)^{2^n}-1$.

Pertama-tama akan ditunjukkan $(2p-1)^{2^k}+1$ adalah bilangan genap.
Bukti : $\forall k \in \mathbb{N}$, $2^k$ selalu genap sehingga $\forall p \in \mathbb{N}$ $(2p-1)^{2^k}$ Selalu ganjil. Jadi dapat disimpulkan $(2p-1)^{2^k}+1$ bilangan genap, dinyatakan dalam $2y$. read more

[latexpage]

Soal: Buatlah algoritma mengurutkan berhingga banyak bilangan bulat.

Pembahasan:

Berikut adalah algoritma dalam format LaTeX untuk mengurutkan sebuah himpunan bilangan bulat:

\begin{algorithm}[H] \caption{Mengurutkan Himpunan Bilangan Bulat}

\begin{algorithmic}[1]

\Procedure{Sort}{$A$}\Comment{$A$: himpunan bilangan bulat}

\State $n \gets$ panjang($A$) \For{$i \gets 1$ to $n-1$} \For{$j \gets 1$ to $n-i$}

\If{$A[j] > A[j+1]$} \State Tukar($A[j]$, $A[j+1]$) \EndIf \EndFor \EndFor

\EndProcedure read more

[latexpage]

Soal: Buatlah algoritma penyelesaian persamaan kuadrat.

Pembahasan:

Berikut ini adalah algoritma tersebut dalam format LaTeX.

\begin{algorithm}[H] \caption{Algoritma Penyelesaian Persamaan Kuadrat}

\begin{algorithmic}[1]

\Procedure{SolveQuadratic}{$a, b, c$}

\State $D \gets b^2 – 4ac$ \If{$D > 0$}

\State $x_1 \gets \frac{-b + \sqrt{D}}{2a}$ \State $x_2 \gets \frac{-b – \sqrt{D}}{2a}$

\State \textbf{Output}: “Persamaan kuadrat memiliki dua akar yang berbeda: $x_1 =$” $x_1$ dan “$x_2 =$” $x_2$ read more