Di dalam toples Andi, terdapat permen. Andi mengambil
permen untuk dia berikan kepada
temannya dimana masing-masing mendapatkan
permen, sehingga permen Andi tersisa
buah. Lalu Andi mengambil
permen lagi untuk dibagikan kepada
teman tadi dengan cara yang sama, berakibat permen di toples tersisa
buah. Proses tersebut Andi lakukan secara terus-menerus sampai permen di toples kurang dari
.
Kita dapat menghitung bahwa Andi melakukan proses tersebut kali, sehingga masing-masing teman Andi mendapatkan
buah permen. Di sisi lain, kita juga dengan mudah mengetahui bahwa sisa permen di dalam toples Andi adalah
buah permen.
Secara matematis, ini dapat kita tuliskan sebagai atau
, dimana 19 kita katakan sebagai hasil bagi dan
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 dan
terdapat dengan tunggal pasangan bilangan bulat non-negatif
sedemikian sehingga
dimana
. Selanjutnya,
dikatakan sebagai \textbf{hasil bagi} dan
adalah \textbf{sisa pembagian} ketika
dibagi oleh
.[/box]
[learn_more caption=”Bukti:” state=”open”] Pertama, ditunjukkan eksistensi . Dibagi 3 kasus.
Kasus 1: .
Jika , dapat dipilih
dan
, sehingga dapat dituliskan dalam
Dalam kasus ini, kita peroleh pasangan .
Kasus 2: .
Jika , dapat dipilih
dan
sehingga dapat dituliskan dalam
Untuk kasus ini, diperoleh pasangan .
Kasus 3: .
Diasumsikan . Terdapat bilangan asli
sehingga
. Karena himpunan bilangan asli \textit{well-ordered}, terdapat bilangan asli terkecil
sehingga
. Berdasarkan minimalitas
, kita peroleh
.
Dengan memilih , didapat
dengan
.
Dari 3 kasus di atas, kita telah membuktikan eksistensi . Selanjutnya, akan dibuktikan ketunggalannya.
Diasumsikan terdapat yang juga memenuhi
dengan
. Oleh karena itu, kita peroleh
Sehingga . Dengan sifat keterbagian, maka
atau
. Karena
, maka
dan menyebabkan
tidak mungkin. Ini berakibat
, yang terpenuhi hanya saat
. Dengan mudah kita juga akan memperoleh
. 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 dan
dimana
, terdapat dengan tunggal pasangan bilangan bulat
sedemikian sehingga
dan
.
[/box]
Berikut adalah contoh penggunaan algoritma pembagian.
- Bilangan genap
dapat dinyatakan dalam
dimana
.
- Bilangan ganjil
dapat dinyatakan dalam
dimana
.
- Untuk setiap bilangan bulat
,
adalah bilangan genap.
- Jika
bilangan bulat yang tidak habis dibagi 3, maka
untuk suatu bilangan bulat
.
- Jika
bilangan ganjil, maka
untuk suatu bilangan bulat
.
- Jika
bilangan bulat,
atau
untuk suatu bilangan bulat (non-negatif)
.
- Jika
bilangan genap,
atau
untuk suatu bilangan bulat (non-negatif)
.
- Jika
adalah bilangan prima yang lebih besar dari 3, maka
dapat dinyatakan dalam
atau
untuk suatu bilangan bulat
.
Bukti contoh penggunaan contoh di atas dapat digunakan Pembaca sebagai latihan.
0 Comments