Keterbagian

Pada kesempatan kali ini, kita akan membahas suatu bagian yang paling dasar dalam teori bilangan yaitu Keterbagian. Keterbagian merupakan sifat dasar yang dimiliki semua bilangan bulat. Jika ada 2 bilangan bulat $a$ dan $b$ dimana $a\not =0$. Bilangan bulat $a$ dikatakan membagi $b$ jika dan hanya jika ada bilangan bulat $c$ sedemikian hingga $a=bc$. Kita bisa menyatakan hal ini dengan $a|b$ yang berarti $a$ habis membagi $b$ atau $b$ adalah kelipatan dari $a$.

Kita tahu bahwa $0=a\cdot 0$, jadi $a|0$ untuk semua bilangan bulat $a\not=0$

Beberapa sifat lain dari keterbagian antara lain:

• Jika $a|b$ dan $b\not=0$ maka $|a|\le|b|$
• jika $a|b$ dan $a|c$ maka ada bilangan bulat $\alpha$ dan $\beta$ sedemikian hingga $a|\alpha b+\beta c$
• jika $a|b$ dan $a|b\pm c$ maka $a|c$
• $a|a$
• jika $a|b$ dan $b|c$ maka $a|c$
• jika $a|b$ dan $b|a$ maka $|a|=|b|$

Selain sifat-sifat diatas ada beberapa teorema tentang keterbagian, salah satunya adalah Division Algorithm. Division Algorithm sendiri memiliki peran yang cukup penting dalam mengerjakan soal-soal matematika. Sejarang kita akan membahas tentang Division Algorithm

Teorema 1. Untuk setiap bilangan bulat positif $a$ dan $b$, terdapat bilangan bulat non-negatif $q$ dan $r$ yang unik (unik berarti hanya ada 1 kemungkinan, tidak ada kemungkinan lain) yang memenuhi
$$b=aq+r,r < a$$

Bukti.Untuk memnbuktikan teorema ini kita perlu tinjau 3 kemungkinan yaitu: $a > b, a=b,$ dan $a < b $. Jika $a > b$ maka kita dapatkan $q=0$ dan $r=b < a$. Jika $a=b$ kita ambil $q=1$ dan $r=0 < a$. Jika$a < b$ maka ada bilangan bulat $n$ sedemikian hingga $na > b$, misalkan $q$ adalah bilangan bulat terkecil sedemikian hingga $(q+1)a > b$. Hal ini berarti $qa\le b$, selanjutnya kita ambil $r=b-qa$. Untuk membuktikan keunikannya, kita asumsikan ada bilangan bulat non-negatif $q'$ dan $r'$ sedemikian hingga $b=aq' + r$. Kita punya $aq+r=aq'+r'$ atau $a(q-q')=(r'-r)$. Dengan sifat diatas kita dapati $a|r'-r$ dan $a\le |r'-r|$. Karena $0\le r,r' < a$ kita punya $|r'-r| < a$. Dengan ini kita dapat simpulkan bahwa $r'=r$ dan otomatis $q'=q$. Dari teorema diatas, saat $a$ dibagi $b$, bilangan $q$ kita sebut quotient dan bilangan $r$ kita sebut reminder.

Contoh Soal. Buktikan untuk semia bilangan bulat positif $n$, bilangan
$$\frac{21n+4}{14n+3}$$
tidak dapat disederhanakan lagi. (IMO pertama)

Solusi. Misalkan ada bilangan bulat positif $d$ sedemikian hingga $d|21n+4$ dan $d|14n+3$.Dengan sifat nomor 2, $d|2(21n+4)-3(14n+3)=-1$. Jadi kita dapat simpulkan bahwa $d=1$ yang berarti pecahan tersebut tidak dapat disederhanakan lagi.