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 \).

Last updated: 5 October 2026