1. Masalah: Nyatakan PBB(126, 35) = 7 sebagai kombinasi linear dari 126 dan 35. 2. Formula: Jika $d = \text{PBB}(a,b)$, maka ada bilangan bulat $x$ dan $y$ sehingga $$ax + by = d.$$ Ini disebut kombinasi linear dari $a$ dan $b$. 3. Kita gunakan algoritma Euclidean untuk mencari $x$ dan $y$. 4. Hitung PBB dan sisa: $$126 = 35 \times 3 + 21$$ $$35 = 21 \times 1 + 14$$ $$21 = 14 \times 1 + 7$$ $$14 = 7 \times 2 + 0$$ Jadi, PBB(126, 35) = 7. 5. Gunakan substitusi mundur untuk mengekspresikan 7 sebagai kombinasi linear: $$7 = 21 - 14 \times 1$$ $$14 = 35 - 21 \times 1$$ Jadi, $$7 = 21 - (35 - 21) = 2 \times 21 - 35$$ 6. Substitusi kembali 21: $$21 = 126 - 35 \times 3$$ Jadi, $$7 = 2(126 - 35 \times 3) - 35 = 2 \times 126 - 6 \times 35 - 35 = 2 \times 126 - 7 \times 35$$ 7. Kesimpulan: Kombinasi linear dari 126 dan 35 yang menghasilkan 7 adalah $$7 = 2 \times 126 - 7 \times 35.$$