Sifat GCD (6)
\( \gcd(a + kb, b) = \gcd(a, b) \) dimana \( a, b, k \in \mathbb{Z} \)
Ini adalah sifat GCD yang sering dipakai dalam menyelesaikan soal teori bilangan.
bukti
Misalkan:
\(
\begin{align*}
d &= \gcd(a, b) \\
e &= \gcd(a + kb, b)
\end{align*}
\)
Teori
Ide utama pembuktian ini adalah membuktikan bahwa:
- \( d \) habis membagi \( e \) dan
- \( e \) habis membagi \( d \)
Jika \( d \) habis membagi \( e \) dan begitu juga sebaliknya \( e \) habis membagi \( d \), maka \( d = e \)
Bukti teori
Sebelum menggunakan teori ini untuk pembuktian, ada baiknya memberikan bukti kebenaran teori ini.
Karena \( d \) dan \( e \) adalah sebuah Faktor Persekutuan Terbesar (FPB), maka \( d, e \gt 0 \) dan \( d, e \in \mathbb{Z} \). Sifat ini sudah dibuktikan di sini.
Tanpa mengurangi sifat umum (without loss of generality), misalkan \( 0 \lt d \le e \)
Ada dua kemungkinan yang harus diperiksa:
- Kemungkinan 1: \( 0 \lt d \lt e \)
- Kemungkinan 2: \( d = e \) dan \( d, e \gt 0 \)
Kemungkinan 1
Karena \( e \) lebih besar dari \( d \) dan \( d \) lebih besar dari \( 0 \), maka \( e \) tidak mungkin habis membagi \( d \).
Kemungkinan 2
Karena \( e \) sama dengan \( d \), maka otomatis \( d \) habis membagi \( e \) dan \( e \) habis membagi \( d \).
Membuktikan d habis membagi e
Karena \( d = \gcd(a, b) \) maka \( d \) pasti habis membagi \( a \) dan \( b \) yaitu:
\(
\begin{align*}
a &= dm \\
b &= dn
\end{align*}
\)
\( \begin{align*} a + kb &= dm + kdn \\ &= d(m + kn) \end{align*} \)
Terlihat jelas bahwa \( d \) adalah salah satu faktor dari \( a + kb \)
Karena \( a + kb \) dan \( b \) keduanya mempunyai faktor \( d \), maka GCD dari \( a + kb \) dan \( b \), yaitu \( e \), pasti juga mempunyai faktor \( d \).
Artinya \( d \) pasti habis membagi \( e \).
Membuktikan e habis membagi d
Karena \( e = \gcd(a + kb, b) \) maka \( e \) pasti habis membagi \( a + kb \) dan \( b \) yaitu:
\(
\begin{align*}
a + kb &= em \\
b &= en
\end{align*}
\)
Kemudian
\(
\begin{align*}
a &= em - kb \\
a &= em - ken \\
a &= e(m - kn)
\end{align*}
\)
Terlihat jelas bahwa \( e \) adalah salah satu faktor dari \( a \)
Karena \( a \) dan \( b \) keduanya mempunyai faktor \( e \), maka menurut sifat ini, \( e \) pasti habis membagi GCD dari \( a \) dan \( b \), yaitu \( d \).
Kesimpulan
Karena \( d \) habis membagi \( e \) dan begitu juga sebaliknya \( e \) habis membagi \( d \), maka \( d = e \)
Contoh
Contoh 1
Carilah faktor persekutuan terbesar dari \( 582 \) dan \( 27 \).
Menggunakan Teorema
Karena \( 582 = 15 + 21 \cdot 27 \) maka
\( \begin{align*} \gcd(582, 27) &= \gcd(15 + 21 \cdot 27, 27) \\ &= \gcd(15, 27) \\ &= 3 \end{align*} \)
Menggunakan Faktor
\( \begin{align*} 582 &= 2 \cdot 3 \cdot 97 \\ 27 &= 3^3 \end{align*} \)
Dari faktor-faktor di atas, diperoleh \( \gcd(582, 27) = 3 \)