KPK dan FPB

[latexpage]

Masih ingat dengan KPK dan FPB?

KPK (Kelipatan Persekutuan Terkecil) dan FPB (Faktor Tersekutuan Terbesar) merupakan salah satu hal yang dipelajari waktu kita menempuh sekolah dasar (SD). Pada saat SD, terkadang kita diminta untuk menghitung KPK dan FPB dari bilangan 24 dan 36. Soal seperti itu dulu bukan soal yang mudah namun sekarang dengan mudah kita bisa menjawab bahwa KPK dan FPB dari 24 dan 36 berturut-turut adalah 72 dan 12. Bagaimana menentukan KPK dan FPB dari $2020^{2020}+20$ dengan $20^{2020}+20$ ? Apakah cukup mudah atau malah cukup sulit?

Untuk menjawab pertanyaan di atas, pada artikel ini akan diberikan pembahasan mengenai KPK dan FPB secara lebih detail dibandingkan pada waktu sekolah dasar.

 Sifat Dasar

Diberikan bilangan asli $m$ dan $n$.

1. Bilangan asli terbesar $d$ sedemikian hingga $d$ habis membagi $m$ dan $n$ disebut faktor persekutuan terbesar (FPB atau GCD) dari $m$ dan $n$. Dinotasikan dengan $d = \gcd(m,n)$.
2. Bilangan asli terbesar $l$ sedemikian hingga $m$ dan $n$ habis membagi $l$ disebut Kelipatan Persekutuan Terkecil (KPK atau LCM) dari $m$ dan $n$. Dinotasikan dengan $l = \lcm(m,n)$.

Bilangan asli $m$ dan $n$ dikatakan relatif prima atau koprima jika $\gcd(m,n) = 1$. Berikut adalah teorema untuk menghitung nilai FPB dan KPK yang telah kita kenal sejak SD menggunakan faktorisasi kanonik.

Teorema 1

[box]

Diberikan bilangan asli $m$ dan $n$. Jika $m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ dan $n = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}$ di mana $p_1,p_2,\ldots,p_k$ merupakan bilangan prima berbeda dan $\alpha_i, \beta_i$ merupakan bilangan bulat non-negatif untuk $i=1,2,\ldots,k$, maka
\begin{align*}
\gcd(m,n) &= p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)} \\
\lcm(m,n) &= p_1^{\max(\alpha_1,\beta_1)} p_2^{\max(\alpha_2,\beta_2)} \cdots p_k^{\max(\alpha_k,\beta_k)}
\end{align*}

[/box]

Berikut adalah salah satu akibat langsung dari sifat sebelumnya.

Akibat 1

[box]

Diberikan bilangan asli $m$ dan $n$. Berlaku
\[\gcd(m,n) \cdot \lcm(m,n) = mn\]

[/box]

[learn_more caption=”Bukti:” state=”open”]

Misalkan $m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ dan $n = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}$ di mana $p_1,p_2,\ldots,p_k$ merupakan bilangan prima berbeda dan $\alpha_i, \beta_i$ merupakan bilangan bulat non-negatif untuk $i=1,2,\ldots,k$. Perhatikan bahwa untuk sebarang bilangan real $x,y$, dipunyai $x+y = \max(x,y) + \min(x,y)$. Akibatnya
\begin{align*}
\gcd(m,n) \cdot \lcm(m,n) &= p_1^{\min(\alpha_1,\beta_1) + \max(\alpha_1,\beta_1)}p_2^{\min(\alpha_2,\beta_2)+\max(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)+\max(\alpha_k,\beta_k)} \\
&= p_1^{\alpha_1+\beta_1} p_2^{\alpha_2+\beta_2} \cdots p_k^{\alpha_k+\beta_k} \\
&= mn
\end{align*}

[/learn_more]

Teorema 2

[box] Diberikan bilangan asli $m$ dan $n$. Misalkan $d = \gcd(m,n)$ dan $l = \lcm(m,n)$.

1. 1. Jika $m = dm_1$ dan $n = dn_1$ untuk suatu bilangan asli $m_1,n_1$, maka $\gcd(m_1,n_1) = 1$.
   2. Jika $l = mm_2$ dan $n = nn_2$ untuk suatu bilangan asli $m_2,n_2$, maka $\gcd(m_2,n_2) = 1$. [/box]

[learn_more caption=”Bukti:” state=”open”]

Misalkan $\gcd(m_1,n_1) = r$. Andaikan $r > 1$. Karena $r$ habis membagi $m_1$ dan $n_1$, maka $m_1 = rm_0$ dan $n_1 = rn_0$ untuk suatu bilangan asli $m_0,n_0$. Akibatnya, $m = drm_0$ dan $n = drn_0$ sehingga $dr$ habis membagi $m$ dan $n$ yang merupakan suatu kontradiksi sebab $dr > d$ dan $d = \gcd(m,n)$. Cara yang serupa dapat digunakan untuk membuktikan poin 2. Rincian pembuktian diserahkan kepada pembaca.

[/learn_more]

Teorema 3

Diberikan bilangan asli $m$ dan $n$. Misalkan $d = \gcd(m,n)$ dan $l = \lcm(m,n)$.

1. Jika $d’$ habis membagi $m$ dan $n$, maka $d’ \mid d$.
2. Jika $m$ dan $n$ habis membagi $l’$, maka $l \mid l’$.

[learn_more caption=”Bukti:” state=”open”]

Misalkan $m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, n = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}$ dan $d’ = p_1^{\gamma_1} p_2^{\gamma_2} \cdots p_k^{\gamma_k}$ merupakan faktorisasi kanonik dari $m,n$ dan $d’$. Karena $d’$ habis membagi $m$ dan $n$, maka jelas bahwa $\gamma_i \leq \alpha_i$ dan $\gamma_i \leq \beta_i$ untuk setiap $i = 1,2,\ldots,k$. Akibatnya, $\gamma_i \leq \min(\alpha_i,\beta_i)$ sehingga jelas bahwa $d’ \mid d$. Cara yang serupa dapat digunakan untuk membuktikan poin 2. Rincian pembuktian diserahkan kepada pembaca.

[/learn_more]

Teorema 4

Diberikan bilangan asli $m$ dan $n$. Jika $m = nq+r$ untuk suatu bilangan asli $q$ dan $r$, maka $\gcd(m,n) = \gcd(n,r)$.

[learn_more caption=”Bukti:” state=”open”]

Misalkan $d = \gcd(m,n)$ dan $d’ = \gcd(n,r)$. Karena $d’$ membagi ruas kanan dari persamaan $m = nq+r$, maka $d’ \mid m$. Akibatnya, $d’$ memebagi $m$ dan $n$ sehingga menurut Teorema 4, diperoleh $d’ \mid d$.

Di lain pihak, perhatikan bahwa $d$ membagi ruas kanan dari persamaan $r = m-nq$, sehingga $d \mid r$. Akibatnya, $d$ merupakan faktor persekutuan $n$ dan $r$, sehingga menurut Teorema 4, diperoleh $d \mid d’$. Akibatnya, $d = d’$ dan teorema terbukti.

[/learn_more]