KONSEP DASAR KETERBAGIAN

Uraian

Pembagian bilangan bulat merupakan bahan pelajaran matematika yang sudah diberikan di sekolah dasar. Bahan pelajaran ini diperluas penggunaannya sampai pada pemfaktoran prima, faktor persekutuan terbesar (FPB), kelipatan persekutuan terkecil (KPK), dan keterbagian oleh bilangan tertentu (misalnya keterbagian oleh 2,3, atau 9). Untuk memberikan dasar atau landasan yang lebih kuat kepada guru matematika di sekolah, maka mereka perlu belajar lebih mendalam tentang konsep-konsep dasar keterbagian.

Keterbagian (divisibility) merupakan dasar pengembangan teori bilangan, sehingga konsep-konsep keterbagian akan banyak digunakan di dalam sebagian besar uraian atau penjelasan matematis tentang pembuktian teorema.

Jika suatu bilangan bulat dibagi oleh suatu bilangan bulat yang lain, maka hasil baginya adalah suatu bilangan bulat atau suatu bilangan yang tidak bulat, misalnya, jika 40 dibagi 8, maka hasil baginya adalah bilangan bulat 8; tetapi jika 40 dibagi 16, maka hasil baginya adalah 2,5. Keadaan inilah yang memberikan gagasan tentang perlunya definisi keterbagian.

Definisi 2.1

Suatu bilangan bulat q habis dibagi oleh suatu bilangan bulat p ≠ 0 jika ada suatu bilangan bulat x sehingga q = px

Notasi

p | q     dibaca p membagi q, p faktor dari q, q habis dibagi p, atau q kelipatan dari p

p Q q   dibaca p tidak membagi q, p bukan faktor dari q, q tidak habis dibagi p, atau q bukan kelipatan dari p

Contoh 2.1
6 | 18 sebab ada bilangan bulat 3 sehingga 18 = 6.3
12 Q  15 sebab tidak ada bilangan bulat x sehingga 15 = 12.x
5 | -30 sebab ada bilangan bulat -6 sehingga -30 = 5.(-6)
-4 | 20 sebab ada bilangan bulat 5 sehingga 20 = (-4).5

Berdasarkan definisi 2.1 diatas jelas bahwa faktor-faktor suatu bilangan bisa merupakan bilangan bulat positif atau merupakan bilangan bulat negatif. Dengan demikian, faktor-faktor dari:

6, adalah 1, -1, 2, -2, 3, -3, 6, dan -6

15, adalah 1, -1, 3, -3, 5, -5, 15,  dan -15

Beberapa sifat sederhana keterbagian adalah :

      1 | p  untuk setiap p Î Z

      p | 0  untuk setiap p Î Z dan p ≠ 0

      p | p  untuk setiap p Î Z dan p ≠ 0

4    Jika p | q, maka kemungkinan hubungan antara p dan q adalah p < q, p = q, atau       p > q (misalnya 3 | 6, 3 | 3, atau 3 | -3)

Teorema 2.1

Jika p, q Î Z dan  p | q, maka p | qr untuk semua  r Î Z

Bukti:

Diketahui bahwa p | q, maka menurut definisi 2.1, ada suatu xÎZ sehingga   q  =  px

q = px berarti qr = pxr, atau qr = p(x.r) dengan xr Î Z (sebab x Î Z dan r Î Z)

Sesuai dengan definisi 2.1, karena qr = p(xr) maka p | qr

Teorema 2.2

Jika p , q, r Î Z, p | q, dan q | r , maka p | r

Bukti:

Diketahui p | q dan q | r, maka menurut definisi 2.1, tentu ada x, y Î Z sehingga q = px dan r  =  qy,

r = qy dan q  =  px, maka r  =  (px)y atau r  =  p (xy) dengan x, yÎZ

Sesuai dengan definisi 2.1, karena r = p(xy), maka  p | r

Teorema 2.3

Jika p, q Î Z, p | q dan q | p, maka p = q

Bukti:

Diketahui p | q dan q | p maka menurut definisi 2.1, terdapat x,y Î Z sehingga

p = qx dan q  =  py.

Jadi: p = (py)x = p(yx) = (xy) = (xy)p, atau 1.p = (xy) p, sehingga xy = 1

Dengan demikian, karena x,y Î Z dan xy = 1, maka diperoleh x = -1 = y atau

x = 1 = y

Jika x = -1 = y, maka p = -q

Jika x = 1 = y, maka p = q

Teorema 2.4

Jika p, q, r Î Z, p | q dan p | r, maka p | q + r

Bukti:

Karena p | q dan p | r, maka menurut definisi 2.1, ada x,y Î Z sehingga q =  px dan r = py.

Dengan demikian q + r = px + py = p(x + y)

Kerena x,yÎZ, maka sesuai dengan sifat tertutup penjumlahan bilangan bulat,    x + y Î Z

Jadi : p | q + r

Teorema 2.4 dapat diperluas tidak hanya berlaku untuk q, r tetapi untuk q, r, s, t,.., artinya jika p | q, p | r, p | s, p | t, dan…, maka p | q  +  r  +  s  +  t  +…

Selanjutnya, teorema 2.4 tetap berlaku jika operasi penjumlahan (+) diganti dengan operasi pengurangn (–), buktikan !

Teorema 2.5

Jika p, q, r Î Z, p | q dan p | r, maka  p | qx + ry untuk semua x, y Î Z             (qx + ry disebut kombinasi linear dari q dan r)

Buktikan!

Teorema 2.6.

Jika p, q, r Î Z, p  > 0, q  >  0, dan p | q, maka p  £  q

Bukti:

Karena p | q, maka menurut definisi 2.1, ada x Î Z sehingga q = px

Karena p > 0, q > 0, dan q = px, maka x > 0

Karena x Î Z dan x > 0, maka kemungkinan nilai-nilai x adalah 1, 2, 3, …, yaitu x = 1 atau x > 1

Jika x = 1, maka q = px = p(1) = p.

Jika x > 1, dan q = px, maka p < q

Jadi  p  ≤  q

Teorema 2.7

Jika p, q, r Î Z, p > 0, q > 0, p | q dan q | p, maka p = q.

Buktikan!

Teorema 2.8

p | q jika dan hanya jika kp | kq untuk semua k Î Z dan k ≠ 0

Buktikan!

Teorema 2.9

Jika p, q, r Î Z, p ≠ 0, p | q + r, dan p | q, maka p | r

Buktikan!

Uraian berikutnya membahas tentang algoritma pembagian. Suatu algoritma didefinisikan sebagai serangkaian langkah-lanbgkah atau prosedur yang jelas dan terhingga untuk menyelesaikan suatu masalah. Kita lazim menggunakan istilah algoritma pembagian (division algoritma) meskipun istilah ini tidak menunjukkan adanya altoritma. Pembicaraan algoritma sebagai prosedur dalam menyelesaikan masalah terdapat nanti pada pembahasan tentang algoritma Enclides.

Teorema 2.10, Algoritma Pembagian

Jika p, q Î Z dan p > 0, maka ada bilangan-bilangan r, s Î Z  yang masing-masing tunggal sehingga q = rp  +  s  dengan 0 £ s < p.

Jika p tidak membagi  q, maka s memenuhi ketidaksamaan 0 < s < p.

Dari pernyataan q = rp + s, 0 ≤ s < p, r disebut hasil bagi (quotient), s disebut sisa (remainder), q disebut yang dibagi (dividend) dan p disebut pembagi (divisor). Kita secara tradisi menggunakan istilah algoritma meskipun sesungguhnya algoritma pembagian bukan merupakan suatu algoritma.

Sebelum membuktikan Teorema 2.9, agar lebih mudah dalam memahami langkah-langkah pembuktian, simaklah dengan cermat uraian berikut:

Ditentukan dua bilangan bulat 4 dan 7 dengan 4 | 7, maka dapat dibuat barisan aritmetika 7 – (r.4) dengan x Î Z

untuk r = 3, 7 – (r.4)      = 7 – 12   = -5

untuk r = 2, 7 – (r.4)      = 7 – 8     = -1

untuk r = 1, 7 – (r.4)      = 7 – 4     =  3

untuk r = 0, 7 – (r.4)      = 7 – 0    =  7

untuk r = -1, 7 – (r.4)    = 7 – (-4)=  11

dan seterusnya

sehingga diperoleh barisan …, -5,  -1,  3, 7,  11,  …

Barisan ini mempunyai suku-suku yang negativf, dan suku-suku yang tidak negatif sebagai unsur-unsur himpunan T.

T  =  {3, 7, 11,…} atau T  =  {7 – (4.r) | r Î Z, 7 – (4.r)  ³  0}

Karena TN dan N adalah himpunan yang terurut rapi, maka menurut prinsip urutan rapi, T mempunyai unsur terkecil.

Perhatikan bahwa unsur terkecil T adalah 3.

Karena 3 Î T, maka 3 = 7 – (4.r) untuk suatu r Î Z. dalam hal ini r = 1, sehingga

3 = 7 -  (4.1), atau 7 = 1.4 + 3

Dengan demikian dapat ditentukan bahwa:

7 = 1.4  + 3 dengan 0  £  3  < 4

Karena   4 │ 7, maka 7 = r.4  +  s dengan r  =  1 dan s  =  3

Perhatikan bahwa untuk 4, 7 Î Z, ada r, s Î Z sehingga 7 = r.4 + s dengan 0  ≤ s <  4

Marilah sekarang kita membuktikan teorema 2.10

Bukti:

Dengan p, q Î Z dapat dibentuk suatu barisan aritmatika (q –  rp) dengan r Î Z, yaitu … , q – 3p, q – 2p, q – p, q, q + 2p, q + 3 p, …

yang mempunyai bentuk umum q – rp

Ambil suatu himpunan T yang unsur-unsurnya adalah suku barisan yang tidak negatif, yaitu:

T = {q – rp | r Î Z, q – rp ³ 0}

Karena TN dan N adalah himpunan yang terurut rapi, maka menurut prinsip urutan rapi, T mempunyai unsur terkecil, misalnya s.

Karena s Î T, maka s = q – rp untuk suatu r Î Z, sehingga q = rp + s.

Jadi jika p, q Î Z dan p > 0, maka ada r, s Î Z sehingga q = rp + s.

Sampai disini pembuktian baru pada tahap menunjukkan eksistensi dari r dan s. berikutnya akan dibuktikan bahwa 0 ≤ s < p dengan menggunakan bukti tidak langsung.

Anggaplah bahwa 0 £ s < p tidak benar, s < 0 atau s ³ p.

Karena s Î T, maka s tidak mungkin negatif, sehingga kemungkinannya tinggal s ³ p.

s ³ p, maka s – p ³ 0, sehingga (q – rp) – p ³ 0 atau q – (r + 1) p ³ 0.

Karena s – p ³ 0 dan s – p = q – (r + 1) p atau s – p mempunyai bentuk q – rp, maka s – p Î T

Karena p > 0, maka s – p < s, sehingga s – p merupakan unsur T yang lebih kecil dari s. Hal ini bertentangan dengan pengambilan s sebagai unsur terkecil dari T.

Jadi: 0 £ s < p

Selanjutnya, buktikan ketunggalan dari r dan s

Petunjuk: gunakan bukti tidak langsung, misalnya r dan s tidak tunggal, yaitu ada r₁, r₂, s₁, s₂ Î Z dan :

q = r₁p + s₁, 0 < s₁ < p

q = r₂p + s₂, 0 < s₁ < p

Contoh 2.1

Tunjukkan:

1.      Jika p | q, maka p² | q²

2.      Jika p | q, maka p | 3q²

Jawab:

1.      Karena p | q, maka sesuai dengan definisi 2.1, ada bilangan k Î Z sehingga q = kp, dengan demikian q²  =  k²p².

Sesuai dengan sifat ketertutupan perkalian bilangan bulat, karena      k Î Z, maka k . k = k² Î Z

q² = k²p² dan k² Î Z, maka sesuai dengan definisi 2.1, p² | q².

1.      Karena p | q, maka sesuai dengan teorema 2.1, p|qr untuk semua r Î Z

Ambil r = 3q, maka 3q Î Z untuk sebarang q Î Z

Dengan demikian, dari p | qr dan r = 3q Î Z, maka p | q (3q) atau

p | 3q².

Contoh 2.2.

Diketahui:  (a₁a₀)  = a₁.10 + a₀ dan 3 | t

Tunjukkan bahwa t | a₁ + a₀

Jawab:

t = a₁.10 + a₀ = a₁ (9 + 1) + a₀ = 9a₁ + (a₁ + a₀)

3 | t atau 3 | 9a₀ + (a₁ + a₀) dan 3 | 9a₀, maka menurut teorema 2.9,           3 | a₁ + a₀

Contoh 2.3

Diketahui t = (a₄ a₃ a₂ a₁ a₀) = a₄.10⁴ + a₃.10³ + a₂.10² + a₁.10 + 4₀ dan  11 | t

Tunjukkan bahwa t | a₀ – a₁ + a₂ – a₃ – a₃ + a₄

Jawab:

t = a₄.10⁴ + a₃.10³ + a₂.10² + a₁.10 + a₀

= a₀ + a₁(11 – 1) + a₂ + a₁(99 + 1) + a₃ (1001 – 1) + a₄ (9999 + 1)

= (11a₁ + 99a₂ + 1001a₃ + 9999a₄) + (a₀ -a₁ + a₂ -a₃ + a₄)

t = 11(a₁ + 9a₂ + 91a₃ + 909a₄) + (a₀ -a₁ + a₂ -a₃ + a₄)

Karena  11 | t, yaitu 11 | 11(a₁ + 9a₂ + 91a₃ + 909a₄) + (a₀ -a₁ + a₂ -a₃ + a₄) dan 11 | 11 (a₁ + 9a₂ + 91a₃ + 909a₄), maka menurut teorema 2.9,     11 | (a₀ -a₁ + a₂ -a₃ + a₄)

Contoh 2.4

Menurut teorema algoritma pembagian, nyatakan sebagai q = rp + s, 0 ≤ s < p, jika:

1.      p = 7 dan q = – 100

2.      p = 12 dan q = – 150

Jawab:

1.      -100 = (-15)(7) + 5, 0 £ 5 < 7

2.      -150 = (-13)(12) + 6, 0 £ 6 < 12

Teorema algoritma pembagian dapat digunakan untuk memilahkan atau memisahkan himpunan bilangan bulat menjadi n himpunan bagian yang saling lepas (disjoint) dengan n Î {2, 3, 4,…}

Jika p = 2 dan q adalah sebarang bilangan bulat, maka menurut teorema algoritma pembagian, q dapat dinyatakan sebagai:

q = 2p + s, 0 ≤ s < 2

Karena r Î Z dan  0 ≤ r < 2, maka kemungkinan nilai-nilai s adalah s = 0 dan s = 1

untuk s  =  0, q  =  2p  +  s  =  2p  +  0  =  2p

untuk s  =  1, q  =  2p  +  s  =  2p  +  1

q = 2p dengan p Î Z disebut bilangan bulat genap (even integer) dan q = 2p + 1 dengan p Î Z disebut bilangan bulat ganjil atau gasal (odd integer). Dengan demikian himpunan bilangan bulat dapat dipisahkan menjadi dua himpunan bagian yang lepas, yaitu himpunan bilangan bulat genap dan himpunan bilangan bulat ganjil. Dengan kata lain, setiap bilangan bulat selalu dapat dinyatakan sebagai salah satu dari:

q = 2p atau q = 2p + 1, p Î Z

Dengan jalan lain yang sama, setiap bilangan bulat selalu dapat dinyatakan sebagai:

q = 3p, q = 3p + 1, q = 3p + 2, p Î Z

q = 4p, q = 4p + 1, q = 4p + 2, q = 4p + 3 , p Î Z

q = 5p, q = 5p + 1, q = 4p + 2, q = 5p + 3 , q = 5p + 4, p Î Z

dan seterusnya.

Contoh 2.5

Buktikan: 2 | n³ – n untuk sebarang n Î Z

Bukti:

Menurut teorema 2.10 (algoritma pembagian), setiap bilangan bulat n dapat dinyatakan sebagai n = 2p atau n = 2p + 1

Untuk n = 2p, dapat ditentukan:

n³ – n   = n (n² -1)

= n (n -1) (n +1)

= 2p (2p -1) (2p +1)

Jadi 2 | n³ – n

Untuk n = 2p + 1, dapat ditentukan

n³ – n   = n (n² -1)

= n (n -1) (n +1)

= (2p +1) (2p +1 – 1) (2p +1 + 1)

= 2p(2p + 1)(2p + 2)

Jadi 2 | n³ – n

Dengan demikian 2 | n³ – n untuk sekarang n Î Z

Selanjutnya, marilah kita lihat cara mengganti suatu bilangan dalam basis 10 menjadi basis yang lain dengan menggunakan teorema yang dibuktikan dengan menggunakan teorema algoritma pembagian.

Teorema 2.11

Jika q Î z dan q > 1, maka setiap n Î Z⁺ dapat dinyatakan  secara tunggal dalam bentuk n = p_kq^k + p_k-1q^k-1 + ….. + p₂q² + p₁q¹ + p₀q⁰

yang mana k Î Z, k ≥ 0, p_t Î Z, 0 £ p_t < q – 1, t = 0, 1,…, k dan  p_k ≠ 0

Bukti:

Karena q Î Z dan q > 1, maka q > 0, sehingga menurut teorema algoritma pembagian, hubungan antara n dan q adalah :

n = qr₀ + p₀, 0 £ p₀ < q (0 £ p₀ £ q -1)

Jika r₀ ≠ 0, maka hubungan antara r₀ dan q menurut teorema algoritma pembagian adalah:

r₀ = qr₁ + p₁, 0 ≤ p₁ ≤ q (0 ≤ p₁ ≤ q – 1)

Jika langkah serupa dikerjakan, maka diperoleh:

r₁ = qr₂ + p₂, 0 ≤ p₂ ≤ q (0 ≤ p₂ ≤ q – 1)

r₂ = qr₃ + p₃, 0 ≤ p₃ ≤ q (0 ≤ p₃ ≤ q – 1)

r_k-2 = qr_k-1 + p_k-1, 0 ≤ p_k-1 < q (0 ≤ p _k-1 ≤ q – 1)

r_k-1 = qr_k-1 + p_k-2, 0 ≤ p_k-2 < q (0 ≤ p_k ≤ q – 1)

Ambil r_k = 0, maka barisan r₀, r₁,…, r_k merupakan barisan bilangan bulat tidak negatif yang menurun, paling banyak mempunyai suku-suku bernilai nol (yaitu r_k), dan k suku yang positif (yaitu r₀,r₁,…, r_k-1).

Dari hubungan antara n, q, dan r_i (i = 0,1, 2,…, k) diatas dapat ditentukan bahwa:

n = qr₀ + p₀

= q(r₁ + p₁) + p₀ = q²r₁ + qp₁ + p₀

= q²(qr₂ + p₂) + qp₁ + p₀ = q³r₂ + q²p₂ + qp₁ + p₀

= ….

= q^k-1r_k-2 + q^k-2p_k-2 + q^k-3p_k-3 + …. + qp₁ + p₀

= q^k-1(qr^k-1 + p_k-1) + q^k-2p_k-2 + q^k-3p_k-3 + … + qp₁ + p₀

= q^k r_k-1 + q^k-1p_k-1 + q^k-2p_k-2 + q^k-3p_k-3 + … + qp₁ + p₀

= q^k(qr_k + p_k) + q^k-1p_k-1+ q^k-2p_k-2 + q^k-3p_k-3 + … + qp₁ + p₀

n = q^k+1r_k + q^kp_k + q^k-1p_k-1 + q^k-2p_k-2 + q^k-3p_k-3 +… + qp₁ + p₀

Karena r_k = 0, maka :

n = q^kp_k + q^k-1p_k-1 + q^k-2p_k-2 + q^k-3p_k-3 +… + qp₁ + p₀

n = p_kq^k + p_k-1q^k-1 + p_k-2q^k-2 +p_k-3q^k-3 +… + qp₁ + p₀

n = (p_kp_k-1p_k-2p_k-3 … p₁ + p₀)_q

Ini berarti bilangan asli n yang ditulis dalam lambang bilangan basis 10, dapat diubah menjadi lambang bilangan basis q > 1

Agar langkah-langkah dalam pembuktian teorema 2.10 dapat dipahami dengan sebaik-baiknya, marilah kita lihat suatu peragaan berikut ini.

Ambil n = 985 dan q = 6

985    =  6.164 + 1       (n    = qr₀ + p₀, r₀ = 164, p₀   = 1)

164    =  6.27 + 2         (r₀   = qr₁ + p₁, r₁ = 27, p₁     = 2)

27      =  6.4 + 3           (r₁   = qr₂ + p₂, r₂ = 4,  p₂ = 3)

4        =  6.0 + 4           (r₂   = qr₃ + p₃, r₃ = 0,  p₃ = 4)

Dengan demikian dapat ditentukan bahwa:

985    =  6.164 + 1

=  6(6.27 + 2) + 1 = 6².27 + 6.2 + 1

=  6²(6.4 + 3) + 6.2 + 1 = 6³.4 + 6².3 + 6.2 + 1

Jadi: (985)₁₀ = (4321)₆

Perhatikan pola yang terdapat pada lambang bilangan basis 6 yang dicari. Angka-angka pada lambang bilangan basis 6 yang dicari merupakan sisa dari masing-masing algoritma pembagian.

Contoh 2.6.

Tuliskan (985)₁₀ dalam lambang bilangan basis 4 dan basis 3.

Jawab:

985   = 4.246 + 1

246   = 4.61 + 2

61     = 4.15 + 1

15     = 4.3 + 3

3       = 4.0 + 3

(985)₁₀ = (33121)₄

Pemeriksaan:

(33121)₄ =  3.4⁴ + 3.4³ + 1.4² + 2.4 + 1

=  768 + 192+ 16+ 8 + 1

=  985

985        =  3.328 + 1

385        =  3.109 + 1

109        =  3.36 + 1

36          =  3.12 + 0

12          =  3.4 + 0

4            =  3.1 + 1

1            =  3.0 + 1

(985)₁₀   =  (1100111)₃

Pemeriksaan:

(1100111)₃  = 1 . 3⁶ + 1 . 3⁵ + 0 . 3⁴ + 0 . 3³ + 1 . 3² + 1 . 3 + 1

= 729 + 243 + 0 + 0 + 9 + 3 + 1    =  985