1. Masalah: Cari PBB (Pembagi Bersama Terbesar) dari 312 dan 70 menggunakan algoritma Euclidean dan ekspansi ke bentuk linear. 2. Rumus utama: Algoritma Euclidean untuk PBB menggunakan pembagian berulang: $$a = bq + r$$ Dimana $a$ dan $b$ adalah bilangan, $q$ adalah hasil bagi, dan $r$ adalah sisa. 3. Langkah pertama: Hitung sisa pembagian 312 dengan 70: $$312 = 4 \times 70 + 32 \Rightarrow 32 = 312 - 4 \times 70$$ 4. Langkah kedua: Hitung sisa pembagian 70 dengan 32: $$70 = 2 \times 32 + 6 \Rightarrow 6 = 70 - 2 \times 32$$ 5. Langkah ketiga: Hitung sisa pembagian 32 dengan 6: $$32 = 5 \times 6 + 2 \Rightarrow 2 = 32 - 5 \times 6$$ 6. Langkah keempat: Hitung sisa pembagian 6 dengan 2: $$6 = 3 \times 2 + 0$$ Karena sisanya 0, maka PBB adalah 2. 7. Ekspansi ke bentuk linear: Mulai dari: $$2 = 32 - 5 \times 6$$ Substitusi $6$ dari langkah 4: $$2 = 32 - 5 \times (70 - 2 \times 32) = 32 - 5 \times 70 + 10 \times 32 = 11 \times 32 - 5 \times 70$$ Substitusi $32$ dari langkah 3: $$2 = 11 \times (312 - 4 \times 70) - 5 \times 70 = 11 \times 312 - 44 \times 70 - 5 \times 70 = 11 \times 312 - 49 \times 70$$ Jadi, PBB(312, 70) = 2 dan dapat ditulis sebagai kombinasi linear: $$2 = 11 \times 312 - 49 \times 70$$ Ini menunjukkan bahwa 2 adalah pembagi terbesar yang dapat ditulis sebagai kombinasi dari 312 dan 70 dengan koefisien 11 dan -49.