Sifat GCD (1)

Jika $a$ adalah sebuah bilangan bulat bukan $0$, maka GCD dari $a$ dan $0$ adalah $\mathrm{|a|}$

$\gcd (a,0)=\mathrm{|a|}$ 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 (\mathrm{|a|},0)$

$\gcd (a,0)=\gcd (\mathrm{|a|},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$.

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 $\mathrm{-8}$ dan $0$.

Menggunakan Teorema

Dengan menggunakan teorema yang sudah diberikan:
$\gcd (\mathrm{-8},0)=\mathrm{|-8|}$
$\gcd (\mathrm{-8},0)=8$

Menggunakan Faktor

Himpunan faktor-faktor positif dari $\mathrm{-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 (\mathrm{-8},0)=8$

Contoh 3

Carilah faktor persekutuan terbesar (GCD) dari $\mathrm{-5}$ dan $0$.

Menggunakan Corollary

$\gcd (\mathrm{-5},0)=\gcd (5,0)$
$\gcd (\mathrm{-5},0)=5$

Corollary pertama mengajarkan bahwa $\gcd (\mathrm{-5},0)$ sama saja dengan $\gcd (5,0)$
Selanjutnya, karena $\gcd (5,0)$ adalah $5$ maka $\gcd (\mathrm{-5},0)=5$

Menggunakan Faktor

Himpunan faktor-faktor positif dari $\mathrm{-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 (\mathrm{-5},0)=5$

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,\dots ,a\}$

Jelas sekali terlihat bahwa faktor terbesar dari $a$ adalah bilangan positif $a$. Jadi, memang betul $\gcd (a,0)=\mathrm{|a|}$

Bukti Corollary 1

Misalkan $a$ adalah sebuah bilangan bulat positif.

Dari teorema di atas, sudah dibuktikan bahwa $\gcd (a,0)=\mathrm{|a|}=a$

Sekarang, karena $a$ adalah sebuah bilangan bulat positif, maka $\mathrm{-a}$ adalah sebuah bilangan bulat negatif.

Misalkan $A$ adalah himpunan semua bilangan bulat positif yang habis membagi $\mathrm{-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,\dots ,a\}$

Jelas terlihat bahwa bilangan bulat positif terbesar yang habis membagi $\mathrm{-a}$ adalah $a$.

Karena semua bilangan pasti habis membagi $0$, maka $a$ juga pasti habis membagi $0$. Dengan demikian GCD dari $\mathrm{-a}$ dan $0$ adalah $a$ juga.

Karena $\gcd (\mathrm{-a},0)=\gcd (a,0)$ maka terbuktilah bahwa $\gcd (a,0)=\gcd (\mathrm{|a|},0)$

Bukti Corollary 2

Corollary ini diperoleh melalui rantai logika berikut

Sesuai definisi nilai mutlak, $\mathrm{|a|}\ge 0$
Karena $a\ne 0$ maka pasti $\mathrm{|a|}\ne 0$

Dari dua informasi di atas, karena $\mathrm{|a|}\ge 0$ dan $\mathrm{|a|}\ne 0$ maka $\mathrm{|a|}>0$

Karena $a$ adalah bilangan bulat, maka $\mathrm{|a|}\ge 1$

Karena $\mathrm{|a|}\ge 1$, maka $\gcd (a,0)\ge 1$

Terbukti sudah bahwa nilai minimum dari $\gcd (a,0)$ adalah $1$.