Sifat GCD (7)
Semua faktor persekutuan positif dari \( a \) dan \( b \) pasti habis membagi \( \gcd(a, b) \)
bukti 1: kontradiksi
Misalkan \( \gcd(a, b) = d \)
Asumsikan ada salah satu faktor persekutuan positif dari \( a \) dan \( b \) yang tidak habis membagi \( d \). Katakanlah \( c \) tidak habis membagi \( d \).
Misalkan \( \gcd(c, d) = e \) maka:
\( c = e \cdot m \)
\( d = e \cdot n \)
dimana \( 1 \lt m \lt n \) dan \( \gcd(m, n) = 1 \)
Penjelasan
Darimana ketaksamaan \( 1 \lt m \lt n \) diperoleh?
Kalau \( m = 1 \), artinya \( c \) habis membagi \( d \). Oleh karena itu, \( m \gt 1 \)
Karena \( d \) adalah faktor persekutuan terbesar, maka menurut definisi FPB, \( d \ge c \)
Tetapi, kalau \( d = c \) maka \( c \) pasti habis membagi \( d \).
Oleh karena itu tanda sama dengan '\( = \)' harus dibuang.
\(
\begin{align*}
d &\gt c \\
e \cdot n &\gt e \cdot m \\
n &\gt m
\end{align*}
\)
Gabungan dua ketaksamaan di atas adalah \( 1 \lt m \lt n \)
Akibat
Karena \( a \) habis dibagi oleh \( c \) dan \( d \) maka \( a \) pasti habis dibagi \( e \cdot m \cdot n \)
Karena \( b \) habis dibagi oleh \( c \) dan \( d \) maka \( b \) pasti habis dibagi \( e \cdot m \cdot n \)
Misalkan \( k = e \cdot m \cdot n \)
Karena \( a \) dan \( b \) keduanya habis dibagi oleh \( k \), maka \( k \) adalah salah satu faktor persekutuan dari \( a \) dan \( b \).
Kontradiksi
Karena \( 1 \lt m \lt n \) maka:
\(
\begin{align*}
e \cdot m \cdot n &\gt e \cdot n \\
k &\gt d
\end{align*}
\)
Ternyata \( k \) lebih besar dari \( d \). Artinya \( d \) bukan faktor persekutuan terbesar. Terjadi kontradiksi. Berarti asumsi yang diambil salah. Pernyataan yang benar adalah: semua faktor persekutuan positif \( a \) dan \( b \) pasti habis membagi \( d \)
bukti 2: teorema Bézout
Misalkan \( \gcd(a, b) = d \)
Menurut Teorema Bézout:
\( d = m \cdot a + n \cdot b \)
Misalkan \( D \) adalah himpunan faktor persekutuan positif dari \( a \) dan \( b \).
\( D = \{d_1, d_2, d_3, \cdots , d_k \} \)
Ambil salah satu faktor persekutuan positif dari \( a \) dan \( b \). Katakanlah \( d_1 \).
Karena \( d_1 \) habis membagi \( a \) dan \( b \):
\( a = d_1 \cdot v \)
\( b = d_1 \cdot w \)
Kemudian:
\(
\begin{align*}
d &= m \cdot a + n \cdot b \\
d &= m \cdot d_1 \cdot v + n \cdot d_1 \cdot w \\
d &= d_1 \cdot (m \cdot v + n \cdot w)
\end{align*}
\)
Jelas terlihat bahwa \( d_1 \) habis membagi \( d \). Dengan cara yang sama, dapat disimpulkan bahwa semua faktor persekutuan positif dari \( a \) dan \( b \) pasti habis membagi \( d \).