Teorema Euclidean

Posted on Updated on

Bilangan Bulat

  • Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8, 21, 8765, -34, 0
  • Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal, seperti 8.0, 34.25, 0.02.

Sifat Pembagian pada Bilangan Bulat

  • Misalkan a dan b bilangan bulat, a
    ¹ 0.

    a habis membagi b (a divides b) jika terdapat bilangan bulat c sedemikian sehingga b = ac.

  • Notasi: a | b jika ba = c, c
    Î Z dan a
    ¹ 0.
  • Contoh 1: 4 | 12 karena 124 = 3 (bilangan bulat) atau 12 = 4 ´ 3. Tetapi 4 | 13 karena 134 = 3.25 (bukan bilangan bulat).

Teorema Euclidean

    Teorema 1 (Teorema Euclidean). Misalkan m dan n bilangan bulat, n > 0. Jika m dibagi dengan n maka terdapat bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga

m = nq + r         (1)

    dengan 0 £
r < n.

Contoh 2.

(i) 1987/97 = 20, sisa 47:

        1987 = 97 × 20 + 47

(ii) –22/3 = –8, sisa 2:

     –22 = 3(–8) + 2

    tetapi –22 = 3(–7) – 1 salah

    karena r = –1 (syarat 0 £
r < n)

Pembagi Bersama Terbesar (PBB)

Misalkan a dan b bilangan bulat tidak nol.

Pembagi bersama terbesar (PBB – greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian hingga d | a dan d | b.

Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.

Contoh 3.

     Faktor pembagi 45: 1, 3, 5, 9, 15, 45;

Faktor pembagi 36: 1, 2, 3, 4, 6, 9, 12, 18, 36;

     Faktor pembagi bersama 45 dan 36: 1, 3, 9


à PBB(45, 36) = 9.

Teorema 2. Misalkan m dan n bilangan bulat, dengan syarat n > 0 sedemikian sehingga

m = nq + r    , 0 £
r < n

maka PBB(m, n) = PBB(n, r)

  • Contoh 4: m = 60, n = 18,

            60 = 18 × 3 + 6

maka PBB(60, 18) = PBB(18, 6) = 6

Untuk lebih jelasnya silahkan download link berikut ini:


Terimakasih atas perhatiannya.

Untuk materi sebelumnya tentang Kombinatorial, silahkan Klik Disini.

Untuk materi selanjutnya tentang Algoritma Euclidean, silahkan Klik Disini.


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s