PENERAPAN ALGORITMA EUCLID PADA PENYELESAIAN PERSAMAAN DIOPHANTINE LINEAR

Abstract

Penelitian ini membahas penerapan Algoritma Euclid dalam menyelesaikan persamaan Diophantine linear, yaitupersamaan polinomial dengan dua atau lebih variabel yang solusi yang dicari adalah bilangan bulat. PersamaanDiophantine linear umumnya berbentuk ax + by = cax + by = cax + by = c, dengan a, b, dan c menjadi bilanganbulat. Penelitian ini menggunakan metode deskriptif-eksploratif, dengan pendekatan studi literatur dan analisisalgoritma. Fokus utama adalah bagaimana Algoritma Euclid digunakan untuk mencari faktor persekutuan terbesar (FPB) dari dua atau lebih koefisien, yang menjadi syarat utama agar suatu persamaan linier memiliki solusi bilangan bulat. Dalam penelitian ini ditunjukkan bahwa persamaan memiliki solusi hanya jika FPB dari koefisien pembagian konstanta pada ruas kanan persamaan. Penelitian ini juga memberikan beberapa contoh soal persamaan linear dua, tiga, dan empat variabel, beserta langkah-langkah penyelesaiannya menggunakan Algoritma Euclid. Hasil yang diperoleh menunjukkan bahwa algoritma ini tidak hanya efisien dan sistematis, tetapi juga memberikan solusi umum dan spesifik yang dapat berfungsi. Pemahaman terhadap konsep dasar teori bilangan, khususnya FPB, sangat penting untuk menerapkan algoritma ini secara efektif dalam menyelesaikan masalah-masalah persamaan Diophantine linear.