KPK dan FPB

Published by ricky.the.ising on

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. 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]

Categories: Materi
Tags:

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.

Related Posts

Materi

Relasi Urutan Pada Bilangan Bulat

Pada himpunan dapat didefinisikan relasi dengan definisi untuk setiap     Berdasarkan relasi didefinisikan relasi dengan definisi untuk setiap     Mudah dibuktikan jika dan hanya jika , sehingga diperoleh jika dan hanya jika dapat Read more…

Materi

Sistem Bilangan Bulat

Seiring dengan perkembangan budaya masyarakat baik dalam ilmu pengetahuan, kehidupan sehari-hari maupun dalam ekonomi sistem bilangan asli yang telah berkembang dianggap masih belum mampu mencukupi fenomena dunia matematika serta kebutuhan masyarakat tentang alat hitung. Khususnya Read more…

Materi

Operasi Perkalian Pada Sistem Bilangan Asli

Berdasarkan operasi penjumlahan pada selanjutnya dikonstruksi operasi perkalian dua bilangan asli. Operasi ini muncul dari penjumlahan secara berulang bilangan asli yang memunculkan pemetaan biner pada sperti dalam teorema berikut ini. Teorema 1 Pada himpunan bilangan Read more…