Sejarah Aljabar: Dari Babilonia Kuno hingga Teorema Bézout dan Aljabar Modern
A. Pengantar Sejarah Aljabar: Dari Tradisi Babilonia hingga Abstraksi Modern
1. Perbedaan Mendasar Aritmatika dan Aljabar
Salah satu miskonsepsi paling umum dalam matematika adalah menganggap aljabar sekadar aritmatika yang menggunakan simbol huruf. Menurut Profesor Keith Devlin (Stanford University), aritmatika dan aljabar merupakan dua mode penalaran yang berbeda secara kualitatif: * Aritmatika (Quantitative Reasoning with Numbers): Berfokus pada perhitungan langsung menggunakan bilangan-bilangan yang nilainya sudah diketahui secara pasti. * Aljabar (Qualitative Reasoning about Unknowns): Berfokus pada penalaran logis mengenai hubungan antar-kuantitas yang belum diketahui (unknowns).
Aljabar tidak lahir ketika huruf $x$ atau $y$ pertama kali dituliskan di atas kertas, melainkan ketika manusia mulai menalar secara terstruktur tentang variabel atau nilai yang belum diketahui.
2. Evolusi Cara Berpikir Aljabar
Sejarah perkembangan aljabar secara umum dibagi menjadi tiga fase utama: 1. Aljabar Retoris (Rhetorical Algebra): Digunakan oleh peradaban Babilonia Kuno (sekitar 2000 SM) dan Yunani Kuno. Seluruh permasalahan dan langkah penyelesaian dijelaskan sepenuhnya menggunakan kata-kata naratif atau representasi geometris (misalnya memotong dan menyusun area persegi). 2. Aljabar Sinkopasi (Syncopated Algebra): Dipelopori oleh Diophantus dari Aleksandria (abad ke-3 M) dan dilanjutkan oleh Al-Khwarizmi (abad ke-9 M), di mana beberapa singkatan dan simbol awal mulai digunakan untuk menggantikan kata-kata yang berulang. 3. Aljabar Simbolik Modern (Symbolic Algebra): Dikembangkan mulai abad ke-16 oleh François Viète dan René Descartes, menggunakan simbol abjad modern secara sistematis untuk mewakili variabel dan konstanta.
B. Teorema Bézout (Bézout's Identity): Definisi dan Pernyataan Utama
Dalam teori bilangan modern dan aljabar tingkat lanjut, salah satu pilar utama yang menghubungkan konsep keterbagian (divisibility) dengan kombinasi linear adalah Teorema Bézout (sering disebut Bézout's Lemma atau Bézout's Identity), yang dinamai dari matematikawan Prancis Étienne Bézout (1730–1783).
Pernyataan Teorema Bézout
Teorema 1.8.1 (Teorema Bézout):
Misalkan $a$ dan $b$ adalah bilangan bulat tak-nol. Persamaan linear Diophantine: $$ax + by = n$$ memiliki solusi bilangan bulat $(x, y) \in \mathbb{Z}^2$ jika dan hanya jika faktor persekutuan terbesar $\gcd(a, b)$ membagi $n$ ($\gcd(a, b) \mid n$).
Implikasi Utama
- Identitas Utama: Selalu terdapat pasangan bilangan bulat $(x_0, y_0)$ sedemikian rupa sehingga: $$ax_0 + by_0 = \gcd(a, b)$$
- Himpunan Kombinasi Linear: Nilai terkecil positif yang dapat dibentuk dari kombinasi linear $ax + by$ (untuk $x, y \in \mathbb{Z}$) adalah tepat sebesar $\gcd(a, b)$.
- Generasi Kelipatan: Setiap bilangan yang dapat dinyatakan dalam bentuk $ax + by$ pasti merupakan kelipatan dari $\gcd(a, b)$, dan sebaliknya setiap kelipatan dari $\gcd(a, b)$ dapat dinyatakan dalam bentuk $ax + by$.
Tabel Contoh Kombinasi Linear untuk $a = 2, b = 4$
Untuk memberikan gambaran intuitif, perhatikan nilai dari $2x + 4y$ saat $x$ dan $y$ bervariasi:
| $y \setminus x$ | -2 | -1 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|---|
| -2 | -12 | -10 | -8 | -6 | -4 | -2 |
| -1 | -10 | -8 | -6 | -4 | -2 | 0 |
| 0 | -8 | -6 | -4 | -2 | 0 | 2 |
| 1 | -6 | -4 | -2 | 0 | 2 | 4 |
| 2 | -4 | -2 | 0 | 2 | 4 | 6 |
Tampak bahwa semua nilai hasil kombinasi linear merupakan kelipatan dari $\gcd(2, 4) = 2$, dan nilai positif terkecil yang muncul adalah 2.
C. Dua Pembuktian Rigorus Teorema Bézout
Berdasarkan referensi Modern_Olympiad_TN.pdf (Contoh 1.10.5), Teorema Bézout dapat dibuktikan melalui dua pendekatan mendasar: pembuktian algoritmik dan pembuktian prinsip ekstremal.
Pembuktian 1: Pendekatan Algoritmik (Algoritma Euclid / Back-Substitution)
Pembuktian ini bersifat konstruktif karena memberikan metode eksplisit untuk menemukan nilai $x$ dan $y$ melalui substitusi balik Algoritma Euclid.
Langkah-langkah Algoritma: Misalkan kita ingin menyatakan $\gcd(a, b)$ sebagai kombinasi linear dari $a$ dan $b$. 1. Lakukan Algoritma Pembagian Euclid berulang hingga sisa pembagian menjadi 0: $$a = b q_1 + r_1 \quad (0 < r_1 < b)$$ $$b = r_1 q_2 + r_2 \quad (0 < r_2 < r_1)$$ $$r_1 = r_2 q_3 + r_3 \quad (0 < r_3 < r_2)$$ $$\dots$$ $$r_{k-2} = r_{k-1} q_k + r_k \quad (r_k = \gcd(a, b))$$ $$r_{k-1} = r_k q_{k+1} + 0$$ 2. Nyatakan sisa terakhir yang tidak nol, yaitu $r_k = \gcd(a, b)$, sebagai: $$r_k = r_{k-2} - r_{k-1} q_k$$ 3. Substitusikan sisa-sisa pembagian sebelumnya secara mundur hingga diperoleh ekspresi berbentuk $ax + by$.
Contoh Konkret (Menyatakan $\gcd(45, 65) = 5$)
- Langkah Pembagian Euclid:
- $65 = 45 \times 1 + 20$
- $45 = 20 \times 2 + 5$
- $20 = 5 \times 4 + 0$
- Substitusi Balik:
- Dari langkah (2): $5 = 45 - 20 \times 2$
- Substitusi $20 = 65 - 45 \times 1$ dari langkah (1): $$5 = 45 - (65 - 45 \times 1) \times 2 = 45 \times 3 + 65 \times (-2)$$
- Diperoleh solusi pasangan bulat $(x, y) = (3, -2)$ untuk $45x + 65y = 5$.
Pembuktian 2: Pendekatan Non-Konstruktif (Prinsip Ekstremal / Teori Himpunan)
Pembuktian ini menunjukkan keberadaan solusi tanpa harus menghitung nilainya secara langsung, menggunakan sifat keterurutan rapi (Well-Ordering Principle).
Bukti: 1. Definisikan himpunan semua kombinasi linear bulat dari $a$ dan $b$: $$S = {ax + by \mid x, y \in \mathbb{Z}}$$ 2. Ambil himpunan bagian dari $S$ yang berisi elemen-elemen positif saja: $$S^+ = {n \in S \mid n > 0}$$ Himpunan $S^+$ tidak kosong karena untuk $x = a$ dan $y = b$, $a(a) + b(b) = a^2 + b^2 > 0 \in S^+$. 3. Berdasarkan Well-Ordering Principle, $S^+$ pasti memiliki elemen positif terkecil. Sebut elemen terkecil ini $d$, yang dapat dituliskan sebagai: $$d = ax_0 + by_0 \quad \text{untuk suatu } x_0, y_0 \in \mathbb{Z}$$ 4. Kita akan membuktikan bahwa $d = \gcd(a, b)$ dengan menunjukkan dua arah keterbagian: * Arah 1 ($\gcd(a, b) \mid d$): Karena $\gcd(a, b) \mid a$ dan $\gcd(a, b) \mid b$, maka berdasarkan sifat umum keterbagian (Teorema 1.2.3), $\gcd(a, b)$ membagi sembarang kombinasi linear dari $a$ dan $b$. Karena $d = ax_0 + by_0$, maka $\gcd(a, b) \mid d$. * Arah 2 ($d \mid a$ dan $d \mid b$): Gunakan kontradiksi. Pengandaian: $d \nmid a$. Berdasarkan Lemma Pembagian Euclid, tuliskan $a = dq + r$ dengan sisa $0 < r < d$. Substitusikan nilai $d = ax_0 + by_0$: $$r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0 q) + b(-y_0 q)$$ Persamaan di atas menunjukkan bahwa $r$ merupakan kombinasi linear dari $a$ dan $b$, sehingga $r \in S$. Namun, kita memiliki $0 < r < d$, yang berarti $r$ adalah elemen positif di $S$ yang nilainya lebih kecil dari $d$. Hal ini bertentangan dengan asumsi bahwa $d$ adalah elemen positif terkecil di $S^+$. Oleh karena itu, pengandaian salah, sehingga haruslah $r = 0$, yang berarti $d \mid a$. Dengan cara yang sama, dapat dibuktikan bahwa $d \mid b$. 5. Karena $d \mid a$ dan $d \mid b$, maka $d$ adalah faktor persekutuan dari $a$ dan $b$. Oleh definisi faktor persekutuan terbesar, $d \le \gcd(a, b)$. 6. Karena $\gcd(a, b) \mid d$ (di mana $\gcd(a, b) > 0$ dan $d > 0$), maka $\gcd(a, b) \le d$. 7. Dari $d \le \gcd(a, b)$ dan $\gcd(a, b) \le d$, disimpulkan bahwa $d = \gcd(a, b)$. ($\text{Q.E.D.}$)
D. Aplikasi Penting Teorema Bézout dalam Olimpiade Matematika
Teorema Bézout merupakan alat analisis yang sangat ampuh untuk membuktikan berbagai lema fundamental dan menyelesaikan soal-soal tingkat kompetisi.
1. Pembuktian Lemma Euclid (Euclid's Lemma)
Pernyataan: Jika $c \mid ab$ dan $\gcd(c, a) = 1$, maka $c \mid b$.
Bukti menggunakan Teorema Bézout: * Karena $\gcd(c, a) = 1$, menurut Teorema Bézout terdapat bilangan bulat $x, y$ sedemikian rupa sehingga: $$cx + ay = 1$$ * Kalikan kedua ruas dengan $b$: $$cbx + aby = b$$ * Perhatikan kedua suku di ruas kiri: * $c \mid cbx$ (jelas karena terdapat faktor $c$). * $c \mid aby$ (karena diketahui $c \mid ab$). * Karena $c$ membagi kedua suku di ruas kiri, maka $c$ pasti membagi jumlahnya: $$c \mid (cbx + aby) \implies c \mid b \quad (\text{Q.E.D.})$$
2. Pembuktian Soal Putnam 2000 (Contoh 1.8.3)
Soal: Buktikan bahwa untuk setiap pasangan bilangan bulat $n \ge m \ge 1$, bentuk berikut adalah bilangan bulat: $$\frac{\gcd(m, n)}{n} \binom{n}{m}$$
Solusi: * Berdasarkan Teorema Bézout, terdapat bilangan bulat $x, y \in \mathbb{Z}$ sehingga $\gcd(m, n) = mx + ny$. * Substitusikan ke dalam persamaan: $$\frac{\gcd(m, n)}{n} \binom{n}{m} = \frac{mx + ny}{n} \binom{n}{m} = x \cdot \frac{m}{n} \binom{n}{m} + y \binom{n}{m}$$ * Menggunakan identitas kombinatorial $\frac{m}{n} \binom{n}{m} = \binom{n-1}{m-1}$: $$\frac{\gcd(m, n)}{n} \binom{n}{m} = x \binom{n-1}{m-1} + y \binom{n}{m}$$ * Karena $x, y, \binom{n-1}{m-1},$ dan $\binom{n}{m}$ semuanya adalah bilangan bulat, maka penjumlahan kombinasi linear tersebut dipastikan menghasilkan bilangan bulat. ($\text{Q.E.D.}$)
3. Sifat Kongruensi Eksponen Modulo (Contoh 2.12.1)
Soal: Misalkan $a, m, n, d$ adalah bilangan bulat positif sedemikian hingga: $$a^m \equiv 1 \pmod d \quad \text{dan} \quad a^n \equiv 1 \pmod d$$ Buktikan bahwa: $$a^{\gcd(m, n)} \equiv 1 \pmod d$$
Solusi: * Berdasarkan Teorema Bézout, terdapat $x, y \in \mathbb{Z}$ sedemikian rupa sehingga $mx + ny = \gcd(m, n)$. * Maka: $$a^{\gcd(m, n)} = a^{mx + ny} = (a^m)^x \cdot (a^n)^y$$ * Substitusikan kongruensi yang diketahui: $$a^{\gcd(m, n)} \equiv (1)^x \cdot (1)^y \equiv 1 \pmod d \quad (\text{Q.E.D.})$$
4. Struktur Solusi Persamaan Diophantine Linear $ax + by = c$
Jika $\gcd(a, b) \mid c$, maka persamaan $ax + by = c$ memiliki tak hingga banyak solusi bulat. Jika $(x_0, y_0)$ adalah salah satu solusi khusus (particular solution), maka solusi umum diberikan oleh: $$x = x_0 + k \cdot \frac{b}{\gcd(a, b)}, \quad y = y_0 - k \cdot \frac{a}{\gcd(a, b)} \quad (k \in \mathbb{Z})$$
E. Kesimpulan dan Refleksi Filosofis
Perkembangan aljabar dari masalah geometris dua persegi Babilonia Kuno hingga bentuk abstrak Teorema Bézout mencerminkan evolusi pemikiran manusia: 1. Perubahan Paradigma: Dari sekadar melakukan kalkulasi aritmatika menjadi penalaran kualitatif terhadap struktur variabel yang belum diketahui (qualitative reasoning about unknowns). 2. Kekuatan Abstraksi: Teorema Bézout mengubah masalah geometri pembagian menjadi struktur aljabar kombinasi linear $ax + by$, yang menjadi landasan utama teori bilangan modern, kriptografi (seperti algoritma RSA), dan aljabar abstrak.
F. 20 Soal Latihan dan Pembahasan Lengkap
Berikut adalah 20 soal latihan yang dirancang untuk menguji pemahaman konseptual dan teknis seputar Sejarah Aljabar, Teorema Bézout, Algoritma Euclid, dan Aplikasinya.
Question 1
Manakah dari pernyataan berikut yang paling tepat menggambarkan perbedaan antara Aritmatika dan Aljabar menurut Profesor Keith Devlin?
Pilihan Jawaban
- A. Aritmatika menggunakan angka bulat, sedangkan aljabar menggunakan angka desimal dan pecahan.
- B. Aritmatika adalah perhitungan kuantitatif dengan angka yang sudah diketahui, sedangkan aljabar adalah penalaran kualitatif tentang variabel yang belum diketahui.
- C. Aritmatika diciptakan oleh Babilonia, sedangkan aljabar diciptakan oleh Yunani Kuno.
- D. Aritmatika tidak menggunakan rumus, sedangkan aljabar selalu menggunakan tabel.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Menurut Keith Devlin, perbedaan mendasar aljabar dan aritmatika bukan terletak pada simbol huruf, melainkan pada mode penalaran (*way of thinking*). * **Step 2 $\rightarrow$** Aritmatika melakukan *quantitative reasoning with known numbers*, sedangkan Aljabar melakukan *qualitative reasoning about unknowns*. **Jawaban: B**Question 2
Jika $\gcd(a, b) = 1$, manakah dari persamaan berikut yang dipastikan selalu memiliki solusi bilangan bulat $(x, y)$ berdasarkan Teorema Bézout?
Pilihan Jawaban
- A. $ax + by = 0,5$
- B. $ax + by = 1$
- C. $ax + by = \frac{1}{2}$
- D. $ax + by = \sqrt{2}$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Teorema Bézout menyatakan bahwa $ax + by = n$ memiliki solusi bulat $(x, y) \in \mathbb{Z}^2$ jika dan hanya jika $\gcd(a, b) \mid n$. * **Step 2 $\rightarrow$** Karena $\gcd(a, b) = 1$ dan $n = 1$ adalah bilangan bulat yang membagi 1 ($1 \mid 1$), maka $ax + by = 1$ pasti memiliki solusi bulat. Nilai pada pilihan A, C, dan D bukan bilangan bulat. **Jawaban: B**Question 3
Diberikan dua bilangan $a = 45$ dan $b = 65$. Pasangan bilangan bulat $(x, y)$ manakah yang memenuhi identitas Bézout $45x + 65y = \gcd(45, 65)$?
Pilihan Jawaban
- A. $(x, y) = (3, -2)$
- B. $(x, y) = (-3, 2)$
- C. $(x, y) = (2, -3)$
- D. $(x, y) = (1, -1)$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Hitung $\gcd(45, 65)$ dengan Algoritma Euclid: * $65 = 45 \times 1 + 20$ * $45 = 20 \times 2 + 5$ * $20 = 5 \times 4 + 0$ * Jadi $\gcd(45, 65) = 5$. * **Step 2 $\rightarrow$** Lakukan *back-substitution*: * $5 = 45 - 20 \times 2$ * Substitusi $20 = 65 - 45 \times 1$: * $5 = 45 - (65 - 45 \times 1) \times 2 = 45 \times 3 + 65 \times (-2)$. * Diperoleh $x = 3$ dan $y = -2$. **Jawaban: A**Question 4
Manakah dari nilai $n$ berikut yang menyebabkan persamaan Diophantine $12x + 18y = n$ TIDAK memiliki solusi bilangan bulat $(x, y)$?
Pilihan Jawaban
- A. $n = 6$
- B. $n = 12$
- C. $n = 15$
- D. $n = 24$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Hitung $\gcd(12, 18) = 6$. * **Step 2 $\rightarrow$** Berdasarkan Teorema Bézout, persamaan $12x + 18y = n$ memiliki solusi bulat jika dan hanya jika $6 \mid n$. * **Step 3 $\rightarrow$** Uji pilihan: * $6 \mid 6$ (Ada solusi) * $6 \mid 12$ (Ada solusi) * $6 \nmid 15$ (TIDAK ada solusi) * $6 \mid 24$ (Ada solusi) **Jawaban: C**Question 5
Dalam pembuktian Teorema Bézout menggunakan Prinsip Ekstremal (Well-Ordering Principle), himpunan $S^+$ didefinisikan sebagai ${ax + by > 0 \mid x, y \in \mathbb{Z}}$. Elemen terkecil $d \in S^+$ dibuktikan merupakan:
Pilihan Jawaban
- A. Nilai rata-rata dari $a$ dan $b$.
- B. Faktor persekutuan terbesar $\gcd(a, b)$.
- C. Kelipatan persekutuan terkecil $\text{kpk}(a, b)$.
- D. Hasil kali $a \times b$.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Dalam bukti prinsip ekstremal, diambil elemen positif terkecil $d = ax_0 + by_0 \in S^+$. * **Step 2 $\rightarrow$** Melalui pembagian berulang $a = dq + r$, ditunjukkan bahwa sisa $r < d$ harus nol (jika tidak, $r \in S^+$ akan lebih kecil dari $d$, kontradiksi). * **Step 3 $\rightarrow$** Terbukti bahwa $d \mid a$ dan $d \mid b$ serta $\gcd(a, b) \mid d$, sehingga $d = \gcd(a, b)$. **Jawaban: B**Question 6
Mengapa pembuktian Lemma Euclid ($c \mid ab \land \gcd(c, a) = 1 \implies c \mid b$) memerlukan Teorema Bézout?
Pilihan Jawaban
- A. Karena Teorema Bézout memungkinkan kita menuliskan $cx + ay = 1$, lalu mengalikannya dengan $b$ menjadi $cbx + aby = b$.
- B. Karena Teorema Bézout menjamin bahwa $a$ dan $b$ pasti bilangan prima.
- C. Karena Teorema Bézout membagi $ab$ dengan $c^2$.
- D. Karena Teorema Bézout mengubah perkalian menjadi pembagian desimal.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Dari $\gcd(c, a) = 1$, Teorema Bézout memberikan keberadaan $x, y \in \mathbb{Z}$ sehingga $cx + ay = 1$. * **Step 2 $\rightarrow$** Mengalikan dengan $b$ menghasilkan $cbx + aby = b$. Karena $c \mid cbx$ dan $c \mid aby$ (karena $c \mid ab$), disimpulkan $c \mid b$. **Jawaban: A**Question 7
Diketahui $a^9 \equiv 1 \pmod d$ dan $a^{15} \equiv 1 \pmod d$. Berdasarkan aplikasi Teorema Bézout pada eksponen kongruensi, manakah hubungan yang pasti berlaku?
Pilihan Jawaban
- A. $a^3 \equiv 1 \pmod d$
- B. $a^6 \equiv 1 \pmod d$
- C. $a^{135} \equiv 1 \pmod d$
- D. $a^{24} \equiv 1 \pmod d$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Berdasarkan aplikasi Teorema Bézout (Contoh 2.12.1), jika $a^m \equiv 1 \pmod d$ dan $a^n \equiv 1 \pmod d$, maka $a^{\gcd(m, n)} \equiv 1 \pmod d$. * **Step 2 $\rightarrow$** Hitung $\gcd(9, 15) = 3$. * **Step 3 $\rightarrow$** Maka dipastikan $a^3 \equiv 1 \pmod d$. **Jawaban: A**Question 8
Jika pasangan $(x_0, y_0) = (2, -1)$ adalah salah satu solusi dari persamaan $7x + 11y = 3$, maka bentuk solusi umum untuk $x$ dan $y$ (dengan $k \in \mathbb{Z}$) adalah:
Pilihan Jawaban
- A. $x = 2 + 11k, \quad y = -1 - 7k$
- B. $x = 2 + 7k, \quad y = -1 - 11k$
- C. $x = 2 - 11k, \quad y = -1 - 7k$
- D. $x = 11k, \quad y = 7k$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Untuk persamaan $ax + by = c$ dengan $\gcd(a, b) = 1$, rumus solusi umum adalah: $$x = x_0 + k \cdot b, \quad y = y_0 - k \cdot a$$ * **Step 2 $\rightarrow$** Dengan $a = 7, b = 11, x_0 = 2, y_0 = -1$: $$x = 2 + 11k, \quad y = -1 - 7k \quad (k \in \mathbb{Z})$$ **Jawaban: A**Question 9
Mengapa peradaban Babilonia Kuno dikategorikan telah memiliki cara berpikir aljabar (algebraic thinking) meskipun mereka tidak menggunakan simbol huruf seperti $x$ atau $y$?
Pilihan Jawaban
- A. Karena mereka sudah menggunakan komputer kalkulator tanah liat.
- B. Karena mereka memecahkan masalah geometris dengan menalar nilai yang belum diketahui melalui prosedur langkah-demi-langkah logis.
- C. Karena mereka menuliskan semua rumus dalam bahasa Latin.
- D. Karena mereka tidak peduli pada luas bangun datar.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Menurut Keith Devlin, aljabar dicirikan oleh *qualitative reasoning about unknowns*. * **Step 2 $\rightarrow$** Tablet Babilonia berisi masalah seperti menentukan panjang sisi dari luas dua persegi yang diketahui jumlahan sisanya. Mereka menalar hubungan tersebut secara sistematis (aljabar retoris). **Jawaban: B**Question 10
Berapakah nilai positif terkecil dari kombinasi linear $21x + 15y$ untuk sembarang $x, y \in \mathbb{Z}$?
Pilihan Jawaban
- A. 1
- B. 3
- C. 6
- D. 15
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Berdasarkan Teorema Bézout, nilai positif terkecil dari $ax + by$ adalah $\gcd(a, b)$. * **Step 2 $\rightarrow$** Cari $\gcd(21, 15)$: * $21 = 15 \times 1 + 6$ * $15 = 6 \times 2 + 3$ * $6 = 3 \times 2 + 0$ * $\gcd(21, 15) = 3$. **Jawaban: B**Question 11
Fase perkembangan aljabar di mana singkatan kata mulai digunakan untuk mengantikan variabel (dipelopori oleh Diophantus dan Al-Khwarizmi) disebut:
Pilihan Jawaban
- A. Aljabar Retoris
- B. Aljabar Sinkopasi (Syncopated Algebra)
- C. Aljabar Simbolik Modern
- D. Aljabar Matriks
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Aljabar Retoris = kata-kata penuh; Aljabar Sinkopasi = kata-kata disingkat/simbol awal; Aljabar Simbolik = simbol abjad modern. * **Step 2 $\rightarrow$** Diophantus dan Al-Khwarizmi berada pada fase Aljabar Sinkopasi. **Jawaban: B**Question 12
Dalam masalah Putnam 2000, ekspresi $\frac{\gcd(m, n)}{n} \binom{n}{m}$ dibuktikan bernilai bulat dengan mengubah $\gcd(m, n)$ menjadi:
Pilihan Jawaban
- A. $m + n$
- B. $mx + ny$
- C. $m \times n$
- D. $m^n$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Teorema Bézout memungkingkan kita menyubstitusi $\gcd(m, n) = mx + ny$ untuk $x, y \in \mathbb{Z}$. * **Step 2 $\rightarrow$** Substitusi ini memecah pecahan menjadi $x \binom{n-1}{m-1} + y \binom{n}{m}$, yang keduanya jelas bilangan bulat. **Jawaban: B**Question 13
Diberikan persamaan $35x + 42y = 7$. Pasangan $(x, y)$ manakah yang merupakan solusi bulat yang memenuhi persamaan tersebut?
Pilihan Jawaban
- A. $(x, y) = (5, -4)$
- B. $(x, y) = (1, 1)$
- C. $(x, y) = (-4, 5)$
- D. $(x, y) = (2, -1)$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Hitung $\gcd(35, 42) = 7$. * **Step 2 $\rightarrow$** Uji pilihan A: $35(5) + 42(-4) = 175 - 168 = 7$. (Cocok dan sesuai dengan Contoh 1.8.1 pada teks sumber). **Jawaban: A**Question 14
Manakah dari sifat keterbagian berikut yang TIDAK didasarkan pada Teorema 1.2.3 ($c \mid x \land c \mid y \implies c \mid ax + by$)?
Pilihan Jawaban
- A. Jika $c \mid x$ dan $c \mid y$, maka $c \mid x + y$.
- B. Jika $c \mid x$ dan $c \mid y$, maka $c \mid x - y$.
- C. Jika $c \mid x$ dan $c \mid y$, maka $c \mid 2x - 3y$.
- D. Jika $c \mid x$, maka $c = x^2$.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Teorema 1.2.3 menyatakan bahwa jika $c$ membagi $x$ dan $y$, maka $c$ membagi kombinasi linear $ax + by$ untuk sembarang $a, b \in \mathbb{Z}$. * **Step 2 $\rightarrow$** Pilihan A ($a=1, b=1$), B ($a=1, b=-1$), C ($a=2, b=-3$) adalah bentuk kombinasi linear. Pilihan D tidak valid secara umum. **Jawaban: D**Question 15
Jika $\gcd(a, b) = d$, manakah dari pernyataan berikut mengenai pembagi bersama yang PASTI BENAR?
Pilihan Jawaban
- A. Jika $c \mid a$ dan $c \mid b$, maka $c \mid d$.
- B. $d$ selalu lebih kecil dari 0.
- C. $a + b$ pasti bilangan prima.
- D. $d$ tidak dapat membagi $a$.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Menurut Lemma 1.6.2 pada teks sumber, jika $c \mid a$ dan $c \mid b$, maka $c$ membagi faktor persekutuan terbesar mereka, yaitu $c \mid \gcd(a, b) = d$. **Jawaban: A**Question 16
Gunakan Algoritma Euclid mundur untuk menemukan nilai $x$ dan $y$ yang memenuhi $7x + 12y = \gcd(7, 12) = 1$.
Pilihan Jawaban
- A. $(x, y) = (7, -4)$
- B. $(x, y) = (-5, 3)$
- C. $(x, y) = (4, -2)$
- D. $(x, y) = (1, 1)$
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Pembagian Euclid: * $12 = 7 \times 1 + 5$ * $7 = 5 \times 1 + 2$ * $5 = 2 \times 2 + 1$ * **Step 2 $\rightarrow$** Back-substitution: * $1 = 5 - 2 \times 2$ * Substitusi $2 = 7 - 5 \times 1 \implies 1 = 5 - (7 - 5 \times 1) \times 2 = 5 \times 3 - 7 \times 2$ * Substitusi $5 = 12 - 7 \times 1 \implies 1 = (12 - 7 \times 1) \times 3 - 7 \times 2 = 12 \times 3 - 7 \times 5 = 7 \times (-5) + 12 \times 3$. * **Step 3 $\rightarrow$** Diperoleh $x = -5$ dan $y = 3$. **Jawaban: B**Question 17
Persamaan Diophantine $8x + 12y = 10$ memiliki solusi bilangan bulat:
Pilihan Jawaban
- A. Tak hingga banyak
- B. Tepat satu solusi
- C. Tidak ada solusi
- D. Dua solusi
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Hitung $\gcd(8, 12) = 4$. * **Step 2 $\rightarrow$** Periksa syarat Teorema Bézout: $4 \mid 10$? * **Step 3 $\rightarrow$** Karena $4 \nmid 10$, maka persamaan ini **TIDAK memiliki solusi** bilangan bulat. **Jawaban: C**Question 18
Manakah dari matematikawan berikut yang pertama kali memperkenalkan penggunaan simbol huruf secara sistematis untuk variabel dan konstanta dalam aljabar modern?
Pilihan Jawaban
- A. François Viète
- B. Euclid
- C. Etienne Bézout
- D. Pythagoras
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** François Viète (akhir abad ke-16) dan René Descartes adalah tokoh utama yang mentransformasi aljabar dari bentuk sinkopasi ke aljabar simbolik modern. **Jawaban: A**Question 19
Jika $ax + by = n$ memiliki solusi bulat khusus $(x_0, y_0)$, bagaimanakah cara membentuk solusi bulat lainnya?
Pilihan Jawaban
- A. Menambahkan $b/\gcd(a,b)$ pada $x_0$ dan mengurangkan $a/\gcd(a,b)$ dari $y_0$ dengan kelipatan $k$.
- B. Mengalikan $x_0$ dan $y_0$ dengan $\pi$.
- C. Membagi $x_0$ dengan $y_0$.
- D. Mengubah $n$ menjadi 0.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Solusi umum persamaan Diophantine linear $ax + by = n$ diberikan oleh pergeseran parameter $k \in \mathbb{Z}$: $$x = x_0 + k \frac{b}{\gcd(a, b)}, \quad y = y_0 - k \frac{a}{\gcd(a, b)}$$ **Jawaban: A**Question 20
Apa peranan utama Teorema Bézout dalam perkembangan Teori Bilangan modern dan Kriptografi (seperti RSA)?
Pilihan Jawaban
- A. Untuk menghitung luas lingkaran secara otomatis.
- B. Untuk menemukan invers modular (modular multiplicative inverse) yang digunakan dalam penyandian pesan.
- C. Untuk menggantikan fungsi kalkulus.
- D. Untuk menghapus semua bilangan negatif.
解 Solusi
**Pembahasan**: * **Step 1 $\rightarrow$** Jika $\gcd(a, m) = 1$, Teorema Bézout memberikan $ax + my = 1 \implies ax \equiv 1 \pmod m$. * **Step 2 $\rightarrow$** Nilai $x$ ini adalah **invers modular** dari $a$ modulo $m$, yang merupakan operasi krusial dalam enkripsi dan dekripsi Kriptografi RSA. **Jawaban: B**Daftar Pustaka
- Khurmi, Aditya. (2020). Modern Olympiad Number Theory. Chapter 1: Divisibility (Section 1.8: Bézout's Theorem & Section 1.10.5: Proof of Bézout's Theorem).
- Devlin, Keith. (2012). Algebra: The Motion of the Ocean — Public Lecture, Stanford Continuing Studies, Stanford University.
- Katz, Victor J. (2009). A History of Mathematics: An Introduction (3rd ed.). Addison-Wesley.
- Rosen, Kenneth H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.