Teorema Bézout (1)
Faktor Persekutuan Terbesar (GCD) dari dua buah bilangan bulat \( a \) dan \( b \), dimana setidaknya salah satunya tidak nol, adalah bilangan bulat positif terkecil yang merupakan kombinasi linear dari \( a \) dan \( b \).
Jika \( d = ma + nb \) dimana \( a, b, m, n \in \mathbb{Z} \) maka \( d \) positif terkecil adalah \( \gcd(a, b) \)
Teorema ini sulit dipahami tanpa contoh. Oleh karena itu, perhatikan contoh di bawah ini baik-baik:
bukti
Ada tak terhingga banyaknya kombinasi linear positif
Jika setidaknya salah satu dari \( a \) atau \( b \) tidak nol, rasanya cukup mudah untuk meyakini bahwa kombinasi linear positif selalu bisa dibuat. Sekalipun \( a \) dan \( b \) bernilai negatif, kombinasi linear positif selalu bisa dibuat dengan mengambil \( m \) dan \( n \) bernilai negatif. Negatif kali negatif akan menghasilkan nilai positif.
Karena ada tak terhingga banyaknya \( m \) dan \( n \) yang bisa dipilih, maka ada tak terhingga pula banyaknya kombinasi linear positif yang bisa dibuat.
Prinsip terurut rapi
Jika kombinasi-kombinasi linear positif ini disimpan dalam sebuah himpunan \( D \), maka pasti himpunan \( D \) tidak kosong. Menurut prinsip terurut rapi (well-ordering principle), himpunan \( D \) pasti mempunyai anggota himpunan terkecil. Katakanlah anggota himpunan terkecil ini adalah \( d \).
d adalah faktor persekutuan dari a dan b
Sekarang akan dibuktikan bahwa \( d \) adalah salah satu faktor persekutuan dari \( a \) dan \( b \). Yaitu, dengan cara menunjukkan bahwa \( d \) habis membagi \( a \) dan \( b \).
Menurut pembagian Euclid, pembagian \( a \) oleh \( d \) bisa dinyatakan sebagai:
\( a = dq + r \) dimana \( 0 \le r \lt d \)
\( r = a - dq \)
Karena \( d = ma + nb \) maka:
\(
\begin{align*}
r &= a - dq \\
r &= a - (ma + nb)q \\
r &= (1 - m)a - nqb
\end{align*}
\)
Perhatikan bahwa \( r \) adalah sebuah kombinasi linear dari \( a \) dan \( b \). Dari konstrain \( 0 \le r \lt d \), ada dua kemungkinan nilai \( r \), yaitu:
Kemungkinan 1: \( 0 \lt r \lt d \)
Seandainya ini benar, artinya \( d \) bukan kombinasi linear positif minimum.
Terjadi kontradiksi.
Kemungkinan ini harus ditolak.
Kemungkinan 2: \( r = 0 \)
Karena ini satu-satunya kemungkinan yang tersisa, maka pasti inilah kemungkinan yang benar.
Karena \( r = 0 \), berarti \( d \) habis membagi \( a \). Dengan cara yang sama persis, dapat dibuktikan bahwa \( d \) juga habis membagi \( b \). Karena \( d \) habis membagi \( a \) dan \( b \), maka \( d \) adalah salah satu faktor persekutuan dari \( a \) dan \( b \).
d adalah faktor persekutuan terbesar dari a dan b
Di atas telah dibuktikan bahwa \( d \) adalah salah satu faktor persekutuan dari \( a \) dan \( b \). Tetapi, apakah \( d \) adalah faktor persekutuan terbesar dari \( a \) dan \( b \)?
Misalkan \( E \) adalah himpuan faktor-faktor persekutuan dari \( a \) dan \( b \).
\( E = \{ e_1, e_2, e_3, \cdots, e_k \} \)
Jika semua anggota himpunan \( E \) habis membagi \( d \), maka memang betul \( d = \gcd(a, b) \)
Ambil salah satu anggota himpunan \( E \). Katakanlah \( e_1 \)
Karena \( e_1 \) adalah faktor persekutuan dari \( a \) dan \( b \) maka:
\( a = e_1 \cdot v_1 \)
\( a = e_1 \cdot w_1 \)
Karena \( d = ma + nb \) maka:
\( d = m \cdot e_1 \cdot v_1 + n \cdot e_1 \cdot w_1 \)
\( d = e_1 ( m \cdot v_1 + n \cdot w_1) \)
Jelas sekali terlihat bahwa \( e_1 \) habis membagi \( d \). Dengan cara yang sama, dapat dipastikan bahwa semua anggota himpunan \( E \) habis membagi \( d \). Dengan demikian, memang betul bahwa \( d = \gcd(a, b) \)
Contoh
Contoh 1
Buatlah himpunan kombinasi linear positif dari \( 4 \) dan \( 10 \). Kemudian bandingkan anggota himpunan terkecil dengan \( \gcd(4, 10) \)
Kombinasi linear positif
\(
\begin{align*}
2 &= (-2) \cdot 4 + 1 \cdot 10 \\
4 &= 1 \cdot 4 + 0 \cdot 10 \\
6 &= (-1) \cdot 4 + 1 \cdot 10 \\
8 &= 2 \cdot 4 + 0 \cdot 10 \\
10 &= 0 \cdot 4 + 1 \cdot 10
\end{align*}
\)
dan seterusnya...
Himpunan kombinasi linear positif dari \( 4 \) dan \( 10 \) adalah \( D = \{ 2,4,6,8,10,\cdots \} \)
Anggota himpunan terkecil dari \( D \) adalah \( 2 \) dan \( \gcd(4, 10) = 2 \).
Ternyata \( \gcd(4, 10) \) sama dengan kombinasi linear positif terkecil dari \( 4 \) dan \( 10 \).
Contoh 2
Buatlah himpunan kombinasi linear positif dari \( -8 \) dan \( 12 \). Kemudian bandingkan anggota himpunan terkecil dengan \( \gcd(-8, 12) \)
Kombinasi linear positif
\(
\begin{align*}
4 &= 1 \cdot (-8) + 1 \cdot 12 \\
8 &= (-1) \cdot (-8) + 0 \cdot 12 \\
12 &= 0 \cdot (-8) + 1 \cdot 12 \\
16 &= (-2) \cdot (-8) + 0 \cdot 12 \\
20 &= (-1) \cdot (-8) + 1 \cdot 12
\end{align*}
\)
dan seterusnya...
Himpunan kombinasi linear positif dari \( -8 \) dan \( 12 \) adalah \( D = \{ 4,8,12,16,20, \cdots \} \)
Anggota himpunan terkecil dari \( D \) adalah \( 4 \) dan \( \gcd(-8, 12) = 4 \).
Ternyata \( \gcd(-8, 12) = 4 \) sama dengan kombinasi linear positif terkecil dari \( -8 \) dan \( 12 \).
Contoh 3
Buatlah himpunan kombinasi linear positif dari \( 6 \) dan \( -3 \). Kemudian bandingkan anggota himpunan terkecil dengan \( \gcd(6, -3) \)
Kombinasi linear positif
\(
\begin{align*}
3 &= 0 \cdot 6 + (-1) \cdot (-3) \\
6 &= 1 \cdot 6 + 0 \cdot (-3) \\
9 &= 0 \cdot 6 + (-3) \cdot (-3) \\
12 &= 1 \cdot 6 + (-2) \cdot (-3) \\
15 &= 2 \cdot 6 + (-1) \cdot (-3)
\end{align*}
\)
dan seterusnya...
Himpunan kombinasi linear positif dari \( 6 \) dan \( -3 \) adalah \( D = \{ 3,6,9,12,15, \cdots \} \)
Anggota himpunan terkecil dari \( D \) adalah \( 3 \) dan \( \gcd(6, -3) = 3 \).
Ternyata \( \gcd(6, -3) = 3 \) sama dengan kombinasi linear positif terkecil dari \( 6 \) dan \( -3 \).
Contoh 4
Buatlah himpunan kombinasi linear positif dari \( -3 \) dan \( -5 \). Kemudian bandingkan anggota himpunan terkecil dengan \( \gcd(-3, -5) \)
Kombinasi linear positif
\(
\begin{align*}
1 &= (-2) \cdot (-3) + 1 \cdot (-5) \\
2 &= 1 \cdot (-3) + (-1) \cdot (-5) \\
3 &= (-1) \cdot (-3) + 0 \cdot (-5) \\
4 &= (-3) \cdot (-3) + 1 \cdot (-5) \\
5 &= 0 \cdot (-3) + (-1) \cdot (-5)
\end{align*}
\)
dan seterusnya...
Himpunan kombinasi linear positif dari \( -3 \) dan \( -5 \) adalah \( D = \{1, 2, 3, 4, 5, \cdots \} \)
Anggota himpunan terkecil dari \( D \) adalah \( 1 \) dan \( \gcd(-3, -5) = 1 \).
Ternyata \( \gcd(-3, -5) \) sama dengan kombinasi linear positif terkecil dari \( -3 \) dan \( -5 \).