Algoritma Pembagian

Di dalam toples Andi, terdapat $97$ permen. Andi mengambil $5$ permen untuk dia berikan kepada $5$ temannya dimana masing-masing mendapatkan $1$ permen, sehingga permen Andi tersisa $92$ buah. Lalu Andi mengambil $5$ permen lagi untuk dibagikan kepada $5$ teman tadi dengan cara yang sama, berakibat permen di toples tersisa $87$ buah. Proses tersebut Andi lakukan secara terus-menerus sampai permen di toples kurang dari $5$ .

Kita dapat menghitung bahwa Andi melakukan proses tersebut $19$ kali, sehingga masing-masing teman Andi mendapatkan $19$ buah permen. Di sisi lain, kita juga dengan mudah mengetahui bahwa sisa permen di dalam toples Andi adalah $2$ buah permen.

Secara matematis, ini dapat kita tuliskan sebagai $97-\underbrace{5-5-\cdots-5}_{\text{19 kali}}=2$ atau $97 = 5\times 19+2$ , dimana 19 kita katakan sebagai hasil bagi dan $2$ adalah sisa pembagian.

Permasalahan di atas dapat digeneralisasi menjadi sebuah teorema yang terlihat cukup trivial, namun sangat berguna.

Teorema [Algoritma Pembagian] [box]
Untuk setiap bilangan bulat positif $a$ dan $b$ terdapat dengan tunggal pasangan bilangan bulat non-negatif $(q,r)$ sedemikian sehingga $b=aq+r$ dimana $0\leq r < a$ . Selanjutnya, $q$ dikatakan sebagai \textbf{hasil bagi} dan $r$ adalah \textbf{sisa pembagian} ketika $b$ dibagi oleh $a$ .[/box]

[learn_more caption=”Bukti:” state=”open”] Pertama, ditunjukkan eksistensi $(q,r)$ . Dibagi 3 kasus.

Kasus 1: $a>b$ .
Jika $a>b$ , dapat dipilih $q=0$ dan $r=b<a$ , sehingga dapat dituliskan dalam

$b=a\cdot 0+b=aq+r.$

Dalam kasus ini, kita peroleh pasangan $(q,r)=(0,b)$ .

Kasus 2: $a=b$ .
Jika $a=b$ , dapat dipilih $q=1$ dan $r=0$ sehingga dapat dituliskan dalam

$b=b\cdot1+0=aq+r.$

Untuk kasus ini, diperoleh pasangan $(q,r)=(1,0)$ .

Kasus 3: $a<b$ .
Diasumsikan $a<b$ . Terdapat bilangan asli $n$ sehingga $na>b$ . Karena himpunan bilangan asli \textit{well-ordered}, terdapat bilangan asli terkecil $q+1$ sehingga $(q+1)a>b$ . Berdasarkan minimalitas $q+1$ , kita peroleh $qa\leq b$ .
Dengan memilih $r=b-qa$ , didapat $b=qa+r$ dengan $0\leq r < a$ .

Dari 3 kasus di atas, kita telah membuktikan eksistensi $(q,r)$ . Selanjutnya, akan dibuktikan ketunggalannya.

Diasumsikan terdapat $(q',r')$ yang juga memenuhi $b=aq'+r'$ dengan $0\leq r' < a$ . Oleh karena itu, kita peroleh

$aq+r=aq'+r' \Leftrightarrow a(q-q')=r'-r.$

Sehingga $a|r'-r$ . Dengan sifat keterbagian, maka $a \leq |r'-r|$ atau $|r'-r|=0$ . Karena $0\leq r, r' <a$ , maka $0\leq |r'-r|<a$ dan menyebabkan $a \leq |r'-r|$ tidak mungkin. Ini berakibat $|r'-r|=0$ , yang terpenuhi hanya saat $r'=r$ . Dengan mudah kita juga akan memperoleh $q'=q$ . Ketunggalan terbukti. [/learn_more]

Teorema di atas menjamin setiap pembagian dua bilangan asli akan menghasilkan hasil bagi dan sisa yang unik (tunggal).

Teorema di atas dapat diperluas menjadi bilangan bulat.

Teorema [Generalisasi Algoritma Pembagian]
[box] Untuk sebarangn bilangan bulat $a$ dan $b$ dimana $a \neq 0$ , terdapat dengan tunggal pasangan bilangan bulat $(q,r)$ sedemikian sehingga $b=aq+r$ dan $0\leq r < |a|$ .
[/box]

Berikut adalah contoh penggunaan algoritma pembagian.

Bilangan genap $n$ dapat dinyatakan dalam $n=2k$ dimana $k\in \mathbb{Z}$ .
Bilangan ganjil $n$ dapat dinyatakan dalam $n=2k+1$ dimana $k \in \mathbb{Z}$ .
Untuk setiap bilangan bulat $n$ , $n^2+n$ adalah bilangan genap.
Jika $n$ bilangan bulat yang tidak habis dibagi 3, maka $n^2=3m+1$ untuk suatu bilangan bulat $m$ .
Jika $n$ bilangan ganjil, maka $n^2=8m+1$ untuk suatu bilangan bulat $m$ .
Jika $n$ bilangan bulat, $n^2=4m$ atau $n^2=4m+1$ untuk suatu bilangan bulat (non-negatif) $m$ .
Jika $n$ bilangan genap, $n^2=8m$ atau $n^2=8m+4$ untuk suatu bilangan bulat (non-negatif) $m$ .
Jika $p$ adalah bilangan prima yang lebih besar dari 3, maka $p$ dapat dinyatakan dalam $6m+1$ atau $6m+5$ untuk suatu bilangan bulat $m$ .

Bukti contoh penggunaan contoh di atas dapat digunakan Pembaca sebagai latihan.

Published by muh.fadlan on October 20, 2020October 20, 2020

0 Comments

Leave a Reply Cancel reply

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli