Sifat GCD (1)
Jika \( a \) adalah sebuah bilangan bulat bukan \( 0 \), maka GCD dari \( a \) dan \( 0 \) adalah \( \lvert a \rvert \)
\( \gcd(a, 0) = \lvert a \rvert \) dimana \( a \ne 0 \) dan \( a \in \mathbb{Z} \)
Walaupun sifat ini rasanya sudah sangat jelas, tetapi rasanya penting untuk memberikan bukti formal atas sifat GCD ini karena sifat ini akan dipakai sebagai kasus dasar (base case) dalam Algoritma Euclid.
Selain itu, ada beberapa akibat langsung (corollary) dari sifat ini yang rasanya perlu dicontohkan dan dibuktikan.
Corollary pertama dari teorema di atas adalah \( \gcd(a, 0) = \gcd(\lvert a \rvert, 0) \)
\( \gcd(a, 0) = \gcd(\lvert a \rvert, 0) \) dimana \( a \ne 0 \) dan \( a \in \mathbb{Z} \)
Artinya, walaupun \( a \) adalah sebuah bilangan bulat negatif, tanda negatif boleh diabaikan dan pencarian GCD dari \( a \) dan \( 0 \) boleh dilanjutkan dengan hanya mempertimbangkan nilai positif dari \( a \) saja. Sifat yang lebih umum akan diberikan dalam sifat GCD selanjutnya.
Corollary kedua dari teorema di atas adalah \( \gcd(a, 0) \ge 1 \)
\( \gcd(a, 0) \ge 1 \) dimana \( a \ne 0 \) dan \( a \in \mathbb{Z} \)
Artinya, nilai minimum dari \( \gcd(a, 0) \) adalah \( 1 \).
bukti teorema
Karena semua bilangan habis membagi \( 0 \), maka \( \gcd(a, 0) \) hanya bergantung dari faktor terbesar \( a \).
Misalkan \( A \) adalah himpunan bilangan bulat positif yang habis membagi \( a \) (faktor positif dari \( a \)) yang sudah disusun dari yang terkecil ke yang terbesar:
\( A = \{ 1, a_1, a_2, a_3, \cdots , a \} \)
Jelas sekali terlihat bahwa faktor terbesar dari \( a \) adalah bilangan positif \( a \). Jadi, memang betul \( \gcd(a, 0) = \lvert a \rvert \)
bukti corollary 1
Misalkan \( a \) adalah sebuah bilangan bulat positif.
Dari teorema di atas, sudah dibuktikan bahwa \( \gcd(a, 0) = \lvert a \rvert = a \)
Sekarang, karena \( a \) adalah sebuah bilangan bulat positif, maka \( -a \) adalah sebuah bilangan bulat negatif.
Misalkan \( A \) adalah himpunan semua bilangan bulat positif yang habis membagi \( -a \).
Kalau anggota himpunan \( A \) disusun dari yang terkecil ke yang terbesar, maka himpunan \( A \) akan terlihat seperti ini:
\( A = \{ 1, a_1, a_2, a_3, \cdots , a \} \)
Jelas terlihat bahwa bilangan bulat positif terbesar yang habis membagi \( -a \) adalah \( a \).
Karena semua bilangan pasti habis membagi \( 0 \), maka \( a \) juga pasti habis membagi \( 0 \). Dengan demikian GCD dari \( -a \) dan \( 0 \) adalah \( a \) juga.
Karena \( \gcd(-a, 0) = \gcd(a, 0) \) maka terbuktilah bahwa \( \gcd(a, 0) = \gcd(\lvert a \rvert, 0) \)
bukti corollary 2
Corollary ini diperoleh melalui rantai logika berikut
Sesuai definisi nilai mutlak, \( \lvert a \rvert \ge 0 \)
Karena \( a \ne 0 \) maka pasti \( \lvert a \rvert \ne 0 \)
Karena \( \lvert a \rvert \ge 0 \) dan \( \lvert a \rvert \ne 0 \) maka \( \lvert a \rvert \gt 0 \)
Karena \( a \) adalah bilangan bulat, maka \( \lvert a \rvert \ge 1 \)
Karena \( \lvert a \rvert \ge 1 \), maka \( \gcd(a, 0) \ge 1 \)
Terbukti sudah bahwa nilai minimum dari \( \gcd(a, 0) \) adalah \( 1 \).
Contoh
Contoh 1
Carilah faktor persekutuan terbesar (GCD) dari \( 5 \) dan \( 0 \).
Menggunakan Teorema
Dengan menggunakan teorema yang sudah diberikan \( \gcd(5, 0) = 5 \)
Menggunakan Faktor
Himpunan faktor-faktor positif dari \( 5 \) adalah \( \{ 1, 5 \} \)
Karena semua bilangan habis membagi \( 0 \), maka semua bilangan di dalam himpunan di atas juga habis membagi \( 0 \). Jelas sekali terlihat bahwa \( 5 \) adalah bilangan terbesar di dalam himpunan di atas.
Dengan demikian, \( \gcd(5, 0) = 5 \)
Contoh 2
Carilah faktor persekutuan terbesar (GCD) dari \( -8 \) dan \( 0\).
Menggunakan Teorema
Dengan menggunakan teorema yang sudah diberikan:
\(
\begin{align*}
\gcd(-8, 0) &= \lvert -8\rvert \\
&= 8
\end{align*}
\)
Menggunakan Faktor
Himpunan faktor-faktor positif dari \( -8 \) adalah \( \{ 1,2,4,8 \} \)
Karena semua bilangan habis membagi \( 0 \), maka semua bilangan di dalam himpunan di atas juga habis membagi \( 0 \). Jelas sekali terlihat bahwa \( 8 \) adalah bilangan terbesar di dalam himpunan di atas.
Dengan demikian, \( \gcd(-8, 0) = 8 \)
Contoh 3
Carilah faktor persekutuan terbesar (GCD) dari \( -5 \) dan \( 0 \).
Menggunakan Corollary
\( \begin{align*} \gcd(-5, 0) &= \gcd(5, 0) \\ &= 5 \end{align*} \)
Corollary pertama mengajarkan bahwa \( \gcd(-5, 0) \) sama saja dengan \( \gcd(5, 0) \)
Selanjutnya, karena \( \gcd(5, 0) \) adalah \( 5 \) maka \( \gcd(-5, 0) = 5 \)
Menggunakan Faktor
Himpunan faktor-faktor positif dari \( -5 \) adalah \( \{ 1, 5 \} \)
Karena semua bilangan habis membagi \( 0 \), maka semua bilangan di dalam himpunan di atas juga habis membagi \( 0 \). Jelas sekali terlihat bahwa \( 5 \) adalah bilangan terbesar di dalam himpunan di atas.
Dengan demikian, \( \gcd(-5, 0) = 5 \)