Faktor persekutuan terbesar: Perbedaan antara revisi
Tidak ada ringkasan suntingan Tag: Suntingan perangkat seluler Suntingan peramban seluler |
Pembenaran istilah, dan menambahkan beberapa penjelasan |
||
Baris 1: | Baris 1: | ||
Dalam [[matematika]], '''Faktor Persekutuan Terbesar''' (FPB) dari dua bilangan adalah [[bilangan bulat]] positif terbesar yang |
Dalam [[matematika]], '''Faktor Persekutuan Terbesar''' (FPB) dari dua atau lebih bilangan adalah [[bilangan bulat]] positif terbesar yang membagi semua bilangan tersebut. |
||
Dalam [[bahasa Inggris]] FPB dikenal dengan ''Greatest Common Divisor'' (GCD), sering djiuga disebut sebagai ''Greatest Common Factor'' (GCF) atau ''Highest Common Factor'' (HCF) |
Dalam [[bahasa Inggris]], FPB dikenal dengan ''Greatest Common Divisor'' (GCD), sering djiuga disebut sebagai ''Greatest Common Factor'' (GCF) atau ''Highest Common Factor'' (HCF). |
||
Dua buah bilangan dikatakan saling prima [[Jika dan hanya jika|jika dan hanya]] jika FPB dari kedua bilangan tersebut bernilai 1. |
|||
== Notasi == |
|||
Pada artikel ini, FPB dari dua buah bilangan a dan b ditulis sebagai fpb(a, b). Beberapa penulis menuliskannya sebagai (a, b). |
|||
== Contoh == |
== Contoh == |
||
Cara sederhana dapat digunakan untuk mencari FPB dari 2 atau 3 [[bilangan]] yang tidak terlalu besar, namun untuk bilangan yang lebih besar |
Cara sederhana dapat digunakan untuk mencari FPB dari 2 atau 3 [[bilangan]] yang tidak terlalu besar, namun untuk bilangan yang lebih besar dapat digunakan cara pemfaktoran. |
||
=== Cara sederhana === |
=== Cara sederhana === |
||
Baris 18: | Baris 23: | ||
* FPB dari 15 dan 25 adalah faktor sekutu (sama) yang terbesar, yaitu '''5'''. |
* FPB dari 15 dan 25 adalah faktor sekutu (sama) yang terbesar, yaitu '''5'''. |
||
=== Cara |
=== Cara pemfaktoran === |
||
Mencari FPB dari bilangan 147, 189 dan 231: |
Mencari FPB dari bilangan 147, 189 dan 231: |
||
Baris 32: | Baris 37: | ||
3 3 |
3 3 |
||
* Susun bilangan dari pohon faktor |
* Susun bilangan dari pohon faktor untuk mendapatkan faktorisasinya: |
||
: |
:Faktorisasi 147 = '''3<sup>1</sup>''' x '''7<sup>2</sup>''' |
||
: |
:Faktorisasi 189 = '''3<sup>3</sup>''' x '''7<sup>1</sup>''' |
||
: |
:Faktorisasi 231 = '''3<sup>1</sup>''' x '''7<sup>1</sup>''' x '''11<sup>1</sup>''' |
||
* Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini '''3''' dan '''7'''. |
* Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini '''3''' dan '''7'''. |
||
Baris 47: | Baris 52: | ||
* Anom dalam Intelegen of East, KPK adalah Kelipatan Persekutuan Terkecil. |
* Anom dalam Intelegen of East, KPK adalah Kelipatan Persekutuan Terkecil. |
||
== |
== Algoritme Euklidean == |
||
Cara lain untuk mencari '''FPB''' adalah dengan menggunakan [[ |
Cara lain untuk mencari '''FPB''' adalah dengan menggunakan [[algoritme Euklidean]]. Misalkan a dan b adalah 2 bilangan bulat yang tidak sama, maka algoritme Euklidean adalah sebagai berikut: |
||
:* a<sub>1</sub> = maximum(a,b)-minimum(a,b) |
:* a<sub>1</sub> = maximum(a,b)-minimum(a,b) |
||
Baris 64: | Baris 69: | ||
::b<sub>i</sub> = minimum(a<sub>i-1</sub>,b<sub>i-1</sub>) |
::b<sub>i</sub> = minimum(a<sub>i-1</sub>,b<sub>i-1</sub>) |
||
Algoritme tersebut berhenti hingga diperoleh a<sub>i</sub> = b<sub>i</sub>. |
|||
⚫ | |||
Algoritme ini dapat lebih jauh disederhanakan lagi dengan pembagian Euklidean, yang dideskripsikan sebagai berikut: |
|||
<math>\gcd(a, 0) = 0</math> |
|||
<math>\gcd(a, b) = \gcd(b, a \,\mathrm{mod}\, b)</math> |
|||
dengan <math>a \, \mathrm{mod} \, b</math> adalah [[operasi modulus]]. |
|||
Pencarian algoritme Euklid dengan pembagian memerlukan sekitar <math>O(\log(\min(a, b)))</math> pembagian. |
|||
⚫ | |||
== Lihat pula == |
== Lihat pula == |
Revisi per 7 Februari 2020 03.50
Dalam matematika, Faktor Persekutuan Terbesar (FPB) dari dua atau lebih bilangan adalah bilangan bulat positif terbesar yang membagi semua bilangan tersebut.
Dalam bahasa Inggris, FPB dikenal dengan Greatest Common Divisor (GCD), sering djiuga disebut sebagai Greatest Common Factor (GCF) atau Highest Common Factor (HCF).
Dua buah bilangan dikatakan saling prima jika dan hanya jika FPB dari kedua bilangan tersebut bernilai 1.
Notasi
Pada artikel ini, FPB dari dua buah bilangan a dan b ditulis sebagai fpb(a, b). Beberapa penulis menuliskannya sebagai (a, b).
Contoh
Cara sederhana dapat digunakan untuk mencari FPB dari 2 atau 3 bilangan yang tidak terlalu besar, namun untuk bilangan yang lebih besar dapat digunakan cara pemfaktoran.
Cara sederhana
Mencari FPB dari 12 dan 20:
- Faktor dari 12 = 1, 2, 3, 4, 6 dan 12
- Faktor dari 20 = 1, 2, 4, 5, 10 dan 20
- FPB dari 12 dan 20 adalah faktor sekutu (sama) yang terbesar, yaitu 4.
Mencari FPB dari 15 dan 25:
- Faktor dari 15 = 1, 3, 5, dan 15
- Faktor dari 25 = 1, 5, dan 25
- FPB dari 15 dan 25 adalah faktor sekutu (sama) yang terbesar, yaitu 5.
Cara pemfaktoran
Mencari FPB dari bilangan 147, 189 dan 231:
- Buat pohon faktor dari masing-masing bilangan:
147 189 231 /\ /\ /\ 3 49 3 63 3 77 /\ /\ /\ 7 7 7 9 7 11 /\ 3 3
- Susun bilangan dari pohon faktor untuk mendapatkan faktorisasinya:
- Faktorisasi 147 = 31 x 72
- Faktorisasi 189 = 33 x 71
- Faktorisasi 231 = 31 x 71 x 111
- Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini 3 dan 7.
- Kalikan faktor-faktor sekutu yang memiliki pangkat terkecil, dalam hal ini 31 x 71 = 21.
- Maka FPB dari bilangan 147, 189 dan 231 adalah 21. Dengan kata lain, tidak ada bilangan yang lebih besar dari 21 yang dapat membagi habis bilangan 147, 189 dan 231.
- Anom dalam Intelegen of East, KPK adalah Kelipatan Persekutuan Terkecil.
Algoritme Euklidean
Cara lain untuk mencari FPB adalah dengan menggunakan algoritme Euklidean. Misalkan a dan b adalah 2 bilangan bulat yang tidak sama, maka algoritme Euklidean adalah sebagai berikut:
- a1 = maximum(a,b)-minimum(a,b)
- b1 = minimum(a,b)
- a2 = maximum(a1,b1)-minimum(a1,b1)
- b2 = minimum(a1,b1)
- .
- .
- .
- ai = maximum(ai-1,bi-1)-minimum(ai-1,bi-1)
- bi = minimum(ai-1,bi-1)
Algoritme tersebut berhenti hingga diperoleh ai = bi.
FPB dari a dan b adalah ai = bi.
Algoritme ini dapat lebih jauh disederhanakan lagi dengan pembagian Euklidean, yang dideskripsikan sebagai berikut:
dengan adalah operasi modulus.
Pencarian algoritme Euklid dengan pembagian memerlukan sekitar pembagian.