Algoritma Pembagian Euclid (sering disebut Algoritma Euclid) adalah materi lanjutan yang sangat krusial dan bisa menjadi "senjata rahasia" bagi siswa yang sedang persiapan OSN.
Jika faktorisasi prima sangat baik untuk memahami konsep dasar, Algoritma Euclid adalah jalan pintas yang jauh lebih efisien ketika siswa dihadapkan pada soal OSN yang melibatkan bilangan ratusan, ribuan, atau bahkan variabel tak diketahui di mana pohon faktor sudah tidak lagi praktis.
Berikut adalah uraian materi Algoritma Euclid yang disusun sistematis untuk dipelajari siswa.
Menguasai Algoritma Euclid untuk Menentukan FPB
Algoritma Euclid adalah metode efisien untuk menemukan FPB (Faktor Persekutuan Terbesar) dari dua bilangan bulat tanpa perlu mencari faktor primanya sama sekali. Algoritma ini didasarkan pada prinsip pembagian bersisa.
1. Konsep Dasar: Teorema Pembagian (Division Lemma)
Sebelum masuk ke algoritma, siswa harus paham bahwa setiap pembagian bilangan bulat selalu bisa ditulis dalam bentuk persamaan dasar:
$$a = b \times q + r$$
Keterangan:
$a$ = Bilangan yang dibagi (bilangan yang lebih besar)
$b$ = Pembagi (bilangan yang lebih kecil)
$q$ = Hasil bagi (kuosien)
$r$ = Sisa bagi (residu), dengan syarat $0 \le r < b$
Inti dari Algoritma Euclid adalah sifat berikut:
$$\text{FPB}(a, b) = \text{FPB}(b, r)$$
Artinya: FPB dari bilangan awal sama dengan FPB dari bilangan pembagi dan sisa baginya.
2. Langkah-Langkah Algoritma Euclid
Untuk mencari FPB dari dua bilangan (misal $A$ dan $B$, di mana $A > B$):
Bagi bilangan yang lebih besar ($A$) dengan bilangan yang lebih kecil ($B$). Tuliskan hasil bagi dan sisa baginya.
Jika sisa baginya belum 0, jadikan pembagi sebelumnya ($B$) sebagai bilangan yang dibagi, dan sisa bagi sebelumnya sebagai pembagi yang baru.
Ulangi proses pembagian ini terus-menerus.
Proses berhenti ketika sisa baginya adalah 0.
FPB-nya adalah pembagi terakhir (bilangan yang menghasilkan sisa 0).
3. Contoh Penerapan (Tingkat Olimpiade)
Contoh 1: Pendekatan Berulang
Tentukan FPB dari 1071 dan 462!
(Catatan untuk siswa: Bayangkan betapa panjangnya jika harus membuat pohon faktor dari 1071)
Penyelesaian dengan Euclid:
Langkah 1: $1071 = 462 \times 2 + 147$ (Sisa 147)
Langkah 2: Geser posisi! Sekarang 462 dibagi 147.
$462 = 147 \times 3 + 21$ (Sisa 21)
Langkah 3: Geser lagi! Sekarang 147 dibagi 21.
$147 = 21 \times 7 + 0$ (Sisa 0)
Karena sisa bagi sudah 0, maka pembagi terakhirnya adalah jawabannya.
Jadi, FPB(1071, 462) = 21.
Contoh 2: Mencari KPK dari Bilangan Besar
Tentukan KPK dari 1071 dan 462!
Penyelesaian:
Daripada mencari KPK secara manual, siswa bisa langsung menggunakan rumus silang yang sudah dipelajari sebelumnya:
$$A \times B = \text{FPB}(A, B) \times \text{KPK}(A, B)$$
$$1071 \times 462 = 21 \times \text{KPK}$$
$$\text{KPK} = \frac{1071 \times 462}{21}$$
$$\text{KPK} = 51 \times 462 = 23562$$
4. Tips Cepat Menjawab Soal OSN dengan Euclid
Seringkali di soal OSN tingkat lanjut, bentuk bilangan tidak berupa angka konkret, melainkan variabel (aljabar). Algoritma Euclid sangat powerful untuk membuktikan FPB dari bentuk aljabar.
Contoh Kasus Aljabar:
Buktikan bahwa pecahan $\frac{21n + 4}{14n + 3}$ tidak dapat disederhanakan (irreducible) untuk semua bilangan asli $n$.
Analisis Siswa: Pecahan tidak dapat disederhanakan jika FPB pembilang dan penyebutnya adalah 1. Mari kita gunakan Euclid!
$21n + 4 = (14n + 3) \times 1 + (7n + 1)$
$14n + 3 = (7n + 1) \times 2 + 1$
$7n + 1 = 1 \times (7n + 1) + 0$
Sisa pembagian terakhir sebelum 0 adalah 1. Terbukti bahwa FPB-nya selalu 1, sehingga pecahan tersebut tidak akan pernah bisa disederhanakan.
5. LATIHAN SOAL
- Bentukan FPB dari $3430$ dan $1365$ menggunakan algoritma pembagian bersisa.
- Berapakah sisa pembagian dari $\text{FPB}(5^5 + 1, 5^6 + 1)$ jika dibagi dengan 5?
- Buktikan atau tentukan nilai FPB dari bentuk aljabar $(21n+4)$ dan $(14n+3)$ untuk sembarang bilangan bulat positif $n$.
- Jika dua bilangan bulat saling prima sehingga $\text{FPB}(a, b) = 1$, sebutkan semua kemungkinan nilai dari $\text{FPB}(a+b, a-b)$!
- Tentukan FPB dari bilangan yang terdiri dari seratus angka 1 ($111...111$) dan enam puluh angka 1 ($111...111$).
- Sisa pembagian bilangan bulat $A$ oleh $84$ adalah $52$. Berapakah sisa pembagian bilangan $A$ tersebut jika dibagi $21$?
- Diketahui suatu identitas pembagian Euclid: $A = 15B + 7$. Jika diketahui $\text{FPB}(A, B) = 1$, buktikan apakah $\text{FPB}(B, 7)$ juga pasti bernilai 1.
- Tentukan nilai FPB dari polinomial $(n^3 - n)$ dan $(n^2 + n)$ untuk bilangan bulat positif $n > 1$.
- Dua bilangan asli berurutan selalu koprima. Berdasarkan sifat tersebut, tentukan $\text{FPB}(n! + 1, (n+1)! + 1)$.
- Berapakah nilai konstanta terbesar $d$ yang selalu habis membagi $(n^5 - n)$ untuk semua bilangan bulat positif $n$?