Modul perkuliahan

Dalil 2.2 (Dalil Algoritma Pembagian)

Jika a > 0, dan a,b Z, maka ada bilangan-bilangan q, r Z yang masing-masing tunggal (unique) sehingga b = qa + r dengan 0 ≤ r < a.

Jika a ┼ b maka r memenuhi ketidaksamaan 0 < r < a.

Bukti.

Misal a, b Z, maka dapat dibentuk suatu barisan aritmatika b – na, n Z, yaitu:

..., b –3a, b – 2a, b-a, b, b + a, b + 2a, ....

Barisan di atas mempunyai bentuk umum b – na.

Selanjutnya, misal S adalah suatu himpunan yang unsur-unsurnya suku yang bernilai positip dari barisan b – na, sehingga:

S = { (b – na) │n Z, dan b – na > 0 }

Menurut prinsip urutan, maka S mempunyai unsur terkecil, sebut saja r.

Karena r S, maka r dapat dinyatakan sebagai r = b – qa, dengan q Z.

Dari r = b – qa dapat diperoleh b = qa + r.

Jadi jika a > 0 dan a,b Z maka ada q,r Z sedemikian sehingga b = qa + r.

Untuk menunjukkan bahwa 0 r < a, maka digunakan bukti tidak langsung sebagai berikut:

Anggaplah bahwa 0 r < a tidakbenar, maka r a dan dalam hal ini r tidak mungkin negatip karena r S.

Jika r a maka r – a 0.

r = b – qa r – a = b – qa – a

= b – ( q +1) a.

r – a 0 dan r-a = b – ( q + 1 ) a 0.

r – a 0 dan r – a mempunyai bentuk b – na, maka r – a S.

Karena a > 0 maka r – a < r sehingga r – a merupakan unsur terkecil dari S dan lebih kecil dari r. Hal ini bertentangan dengan pengambilan r sebagai unsur terkecil S. Jadi haruslah 0 r < a.

Untuk menunjukkan ketunggal q dan r, dimisalkan q dan r tidak tunggal yaitu q₁, q₂, r₁, r₂ Z dan memenuhi hunbungan persamaan

b = q₁a + r₁

b = q₂a + r₂

Sehingga berlaku q₁a+ r₁ = q₂a+ r₂

( q_{1 -} q₂ ) a + ( r₁ - r₂ ) = 0 .

( r₁ - r₂ ) = ( q_{2 –} q₁ )a

a │ ( r₁ - r₂ )

a │ ( r₁ - r₂ ) r₁ - r₂ = 0 atau r₁ - r₂ a ( a r₁ - r₂ )

r₁ - r₂ = 0 r₁ = r₂ (q_{1 -} q₂ ) a = 0 q₁ = q₂

r₁ - r₂ a > 0, r₁ > 0 , r₂ > 0 r₁ a = 0.

Jadi r₁ = r₂ dan q₁ = q₂ yaitu q dan r masing-masing adalah tunggal.

Selanjutnya jika a ┼ b, maka tidak ada q Z sehingga b = qa. Hal ini berarti b qa atau b = qa + r dengan 0 < r < a. ( r 0, sebab jika r = 0 diperoleh b = qa).

1. Dalil 2.3

Jika b = qa + r dengan 0 ≤ r < a, maka

b disebut bilangan yang dibagi (devidend)

a disebut bilangan pembagi (devisor/faktor)

q disebut bilangan hasil bagi (quotient), dan

r disebut bilangan sisa (remainder/residu)

Dalil 2.3 di atas disebut pula dengan dalil algoritma pembagian. Algoaritma adalah prosedur atau metode matematis untuk memperoleh hasil tertentu yang dilakukan menurut sejumlah langkah berurutan yang berhingga. Dalil 2 ini sebenarnya lebih bersifat dalil eksistensi (keujudan) dari adanya bilangan-bilangan bulat q dan r dari suatu algortima. Namun demikian uraian tentang pembuktiannya dapat memberikan gambaran adanya suatu metode, cara , atau prosedur matematis untuk memperoleh bilangan-bilangan bulat q dan r sehingga b = qa + r.

Jika a = 2 dan b adalah sebarang bilangan bulat, maka menurut dalil sebelumnya b dapat dinyatakan dengan b = 2q + r, dengan 0 ≤ r < a. Hal ini berarti bahwa nilai-nilai b yang mungkin dapat ditentukan oleh nilai-nilai r yang mungkin yaitu r = 0 dan r = 1.

Untuk r = 0 maka b = 2q + r = 2q + 0.

b = 2q, dengan q Z.

b yang dapat dinyatakan dengan 2q ( q Z ) disebut bilangan bulat genap (even integer).

Untuk r = 1, b = 2q + r = 2q + 1 ( q Z ) disebut bilangan bulat ganjil. (odd intereger, gasal).

Ternyata berdasarkan dalil algoritma pembagian, setiap bilangan bulat dapat dinyatakan sebagai bilangan bulat genap (2q) atau bilangan bulat ganjil ( 2q + 1). Selanjutnya jika diambil a = 3, maka menurut dalil Algoritma Pembagian, dengan mengambil r= 0, r=l dan r=2. Sehingga sebarang bilangan bulat b dapat dinyatakan sebagai bentuk dari salah satu persamaan berikut:

b = 3q

b = 3q + 1

b = 3q + 2

Dengan alasan yang sama, setiap bilangan bulat selalu dapat dinyatakan antara lain:

1. 
   Salah satu dari 4q, 4q+1, 4q+2, 4q+3 (q Z)
   
2. 
   Salah satu dari 5q, 5q+1, 5q+2, 5q+3, 5q+4 (q Z)
   
3. 
   Salah satu dari 6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5 (q Z)
   

Disinilah sebenarnya letak dari konsep algoritma pembagian, suatu konsep mendasar yang dapat digunakan untuk membantu pembuktian sifat-sifat tertentu.

Contoh:

1. 
   Diketahui n adalah bilangan bulat, buktikan bahwa 2 │n³ – n .
   

Bukti:

Menurut dalil Algoritma pembagian, terdapat bilangan bulat q sedemikian sehingga n = 2q atau n = 2q + 1,

Untuk n = 2q maka

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

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

= 2q(2q-1)(2q+1)

= 2{q(2q-1)(2q+1)

n³ – n = 2{q(2q-1)(2q+1)

Sehingga 2 │2{q(2q-1)(2q+1) atau 2 │ n³ – n

Untuk n = 2q+1 maka

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

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

= (2q+1)(2q+1-1)(2q+1+1)

= (2q+1)(2q)(2q+2)

n³ – n = (2q+1)(2q)(2q+2)

Sehingga 2 │(2q+1)(2q)(2q+2) atau 2 │ n³ – n

1. 
   Tunjukkan bahwa 4 ┼ n² + 2 untuk sebarang n Z
   

Jawab

• 
  Dengan bukti tidak langsung, anggaplah 4 │ n² + 2.
  

Sesuai dengan dalil algoritma pembagian, untuk n Z dapat dinyatakan sebagai

n = 2q atau n = 2q + 1, q Z.

Untuk n = 2q, maka n² + 2 = (2q)² + 2 = 4q² + 2

4 │n² + 2

n² + 2 = 4q² + 2

4 │4q² + 2

4 │4q² , maka 4 │2, hal ini terjadi kontradiksi karena 4 ┼ 2.

• 
  Jadi anggapan bahwa 4 │ n² + 2. adalah salah sehingga 4 ┼ n² + 2.
  

Untuk n = 2q + 1, maka n² + 2 = (2q+1)² + 2 = 4q² + 4q + 3

= 4(q²+q) + 3

4 │n² + 2

n² + 2 = 4(q² +q) + 3

4 │4(q² + q) + 3

4 │4(q² + q), maka 4 │3, hal ini terjadi kontradiksi karena 4 ┼ 3.

1.