Pembuktian Algoritma Pembagian pada Bilangan Bulat

Algoritma pembagian pada bilangan bulat (Division Algorithm for Integer) merupakan suatu algoritma (langkah-langkah sistematis) dasar yang dapat digunakan untuk menentukan sisa pembagian dari dua bilangan bulat positif.

Sisa pembagian ini dikenal juga dengan istilah modulo.

 

Teorema

Diketahui dua bilangan bulat $a$ dan $b$ dengan $a, b > 0$. Maka, terdapat bilangan bulat $q$ dan $r$ sedemikian sehingga

$a = b \cdot q + r$ dengan sifat $0 \leq r < b$.

 

Pembuktian

Diketahui dua bilangan bulat $a$ dan $b$ dengan $a, b > 0$. Maka, dari dua bilangan bulat ini kita bisa memperoleh tiga kemungkinan kasus sebagai berikut.

1. $a = b$
2. $a < b$
3. $a > b$

 

Untuk kasus $a = b$, kita bisa memilih $q = 1$ dan $r = 0$, sehingga dengan demikian diperoleh:

$a = b \cdot 1 + 0$

 

Untuk kasus $a < b$, kita bisa memilih $q = 0$ dan $r = a$, sehingga dengan demikian diperoleh:

$a = b \cdot 0 + a$

Perhatikan bahwa karena $r = a > 0$, dan $a < b$, maka $r$ jelas memenuhi sifat $0 \leq r < b$.

 

Untuk kasus terakhir yaitu $a > b$, menggunakan sifat bilangan bulat kita selalu dapat menemukan bilangan bulat $s$ sehingga

$a = b + s$. Ya kan?

Perhatikan bahwa $s$ selalu lebih kecil dari $a$.

Perhatikan juga bahwa jika dibandingkan dengan $b$, kita akan memperoleh 3 kemungkinan dari $s$ sebagai berikut.

1. $s = 0$
2. $s < b$
3. $s > b$

 

Untuk kasus $s = 0$ tidak mungkin terjadi. Karena bila terjadi, maka mengingkari pembahasan kita terhadap kasus $a > b$. Dengan demikian maka pasti berlaku salah satu di antara $s < b$ atau $s > b$.

 

Jika yang terjadi $s < b$ maka kita dapat memilih $r = s$ sehingga dengan demikian diperoleh

$a = b \cdot (1) + s$.

Karena $a > b > s > 0$ maka jelas $r = s$ memenuhi sifat $0 \leq r < b$.

 

Jika yang terjadi $s > b$ maka menggunakan sifat bilangan bulat kita akan selalu dapat menemukan bilangan bulat $s'$ sedemikian sehingga berlaku

$s = b + s'$

Ya toh?

 

Dengan demikian persamaan $a = b + s$ dapat "dipecah" sebagai berikut

$a = b + (b + s')$

$a = (b + b) + s'$

$a = 2 \cdot b + s'$

 

Perhatikan bahwa kita akan selalu dapat membandingkan $s$ dan juga $s'$ dengan $b$. Dengan demikian, kita akan selalu dapat melakukan perulangan "pemecahan" persamaan $a = b + s$.

 

Perulangan "pemecahan" ini akan terhenti ketika kita memperoleh bilangan bulat $\dot{s}$ yang memenuhi persamaan

$a = n \cdot b + \dot{s}$ untuk suatu bilangan bulat positif $n$.

 

Perulangan "pemecahan" ini pasti akan berhenti pada suatu langkah ke-$n$ karena nilai $\dot{s}$ yang dihasilkan akan semakin mengecil menuju 0. 

 

Jadi, dengan demikian terbuktilah algoritma pembagian pada bilangan bulat.