Sifat GCD (5)

Jika keduanya tidak \( 0 \), maka nilai maksimum yang mungkin dari GCD dua buah bilangan bulat \( a \) dan \( b \) adalah \( \min(\lvert a \rvert, \lvert b \rvert) \)

\( \gcd(a, b) \le min(\lvert a \rvert, \lvert b \rvert) \) dimana \( a, b \ne 0 \) dan \( a, b \in \mathbb{Z} \)

Kasus maksimum, kasus \( \gcd(a, b) = \min(\lvert a \rvert, \lvert b \rvert) \) terjadi jika dan hanya jika \( a \) habis membagi \( b \) atau \( b \) habis membagi \( a \).

Definisi

\( \min(a, b) \) adalah sebuah fungsi yang mengembalikan nilai terkecil (minimum) di antara \( a \) dan \( b \)

bukti

Pembuktian-pembuktian di bawah akan mengambil pemisalan sebagai berikut:

Misalkan \( \gcd(a, b) = d \)
Akibatnya \( a \) dan \( b \) pasti habis dibagi oleh \( d \).

Tanpa kehilangan sifat umum (without loss of generality), misalkan \( \lvert a \rvert \le \lvert b \rvert \)
Karena \( \lvert a \rvert \le \lvert b \rvert \) maka \( \min(\lvert a \rvert, \lvert b \rvert) = \lvert a \rvert \)

Bukti ketaksamaan

Tujuan pembuktian adalah untuk membuktikan \( \gcd(a, b) \le \lvert a \rvert \)

Asumsikan \( d \gt \lvert a \rvert \)

Karena \( a \ne 0 \), maka \( \lvert a \rvert \gt 0 \). Kalau digabungkan dengan asumsi di atas, ketaksamaan menjadi \( d \gt \lvert a \rvert \gt 0 \)

Dari ketaksamaan di atas, tentu saja \( a \) tidak akan habis dibagi oleh \( d \). Terjadi kontradiksi dan artinya asumsi ini pasti salah. Pernyataan yang benar adalah \( d \le \lvert a \rvert \)

\( \begin{align*} d &\le \lvert a \rvert \\ \gcd(a, b) &\le \min(\lvert a \rvert, \lvert b \rvert) \end{align*} \)

Terbuktilah \( \gcd(a, b) \le \min(\lvert a \rvert, \lvert b \rvert) \)

Bukti implikasi 1

Akan dibuktikan implikasi berikut: jika \( \gcd(a, b) = \min(\lvert a \rvert, \lvert b \rvert) \) maka \( a \) habis membagi \( b \).

\( \begin{align*} \gcd(a, b) &= \min(\lvert a \rvert, \lvert b \rvert) \\ &= \lvert a \rvert \end{align*} \)

Karena \( \lvert a \rvert \) habis membagi \( a \) dan \( b \), maka \( a \) pasti habis membagi \( a \) dan \( b \) juga.

Bukti implikasi 2

Akan dibuktikan implikasi berikut: Jika \( a \) habis membagi \( b \) maka \( \gcd(a, b) = \min(\lvert a \rvert, \lvert b \rvert) \)

Jika \( a \) habis membagi \( b \) maka \( a \) adalah salah satu faktor persekutuan dari \( a \) dan \( b\). Karena \( a \) bisa saja positif ataupun negatif, maka, untuk memastikan nilainya positif, hanya \( \lvert a \rvert \) saja yang dimasukkan ke dalam himpunan faktor persekutuan positif dari \( a \) dan \( b \).

Karena faktor positif terbesar dari \( a \) adalah \( \lvert a \rvert \), maka tidak mungkin ada faktor persekutuan positif dari \( a \) dan \( b \) yang lebih besar dari \( \lvert a \rvert \). Akibatnya, faktor persekutuan positif terbesar dari \( a \) dan \( b \) adalah \( \lvert a \rvert \).

\( \begin{align*} \gcd(a, b) &= \lvert a \rvert \\ &= \min(\lvert a \rvert, \lvert b \rvert) \end{align*} \)

Kesimpulan

Pembuktian sudah lengkap dan memang betul:

\( \gcd(a, b) \le min(\lvert a \rvert, \lvert b \rvert) \) dimana \( a, b \ne 0 \) dan \( a, b \in \mathbb{Z} \)

\( \gcd(a, b) = \min(\lvert a \rvert, \lvert b \rvert) \) jika dan hanya jika \( a \) habis membagi \( b \) atau \( b \) habis membagi \( a \).

Last updated: 5 October 2026