Kue Lebaran: Geometri Euclides

Masih dalam rangka belajar menulis dengan menggunakan LaTeX, kali ini saya sajikan catatan kuliah saya pada mata kuliah DM 241 Geometri Euclides dari Bapak Drs. Samjoeto di Institut Teknologi Bandung pada tanggal 22 Agustus s.d. 8 September 1988 dalam 5 kali perkuliahan.

Naskah ini saya tulis dengan memanfaatkan write LaTeX. Ternyata, untuk anggota gratisnya, write LaTeX membatasi jatah pengunggahan gambar hingga 60 buah saja, padahal untuk materi ini tentu saja saya memerlukan banyak gambar. Karena baru belajar, saya belum bisa memproduksi gambar langsung dengan menggunakan LaTeX. Dengan demikian tulisan geometri Euclides ini akan terbit dalam beberapa bagian.

Bila dalam naskah ini terdapat kesalahan konsep, dimohon untuk diberitahukan disertai dengan perbaikannya.

Demikian semoga bermanfaat!

Adjie Gumarang Pujakelana, 2013

-->

Teori Bilangan #7

Kekongruenan

Definisi Andaikan a, b, dan m bilangan bulat dengan m > 0. Dikatakan bahwa a º b (mod m) jika dan hanya jika m\(a – b) atau $k bulat demikian sehingga a – b = km.

Contoh:
11 º 5 (mod 3) karena 3\(11 – 5) = 6.

Teorema 1

Kekongruenan adalah suatu relasi ekuivalen.

Bukti:

(i)      a º a (mod m) karena m\(a – a) = 0

(ii)    Misalkan a º b (mod m) maka m\(a – b) demikian sehingga m\–(a – b) = b – a.

        Jadi b º a (mod m).

(iii)   Misalkan a º b (mod m) dan b º c (mod m) maka m\(a – b) dan m\(b – c) demikian sehingga

      m\(a – b) + (b – c) = a – c.
        Jadi a º c (mod m).

Teorema 2

a º b (mod m) jika dan hanya jika a dan b mempunyai sisa yang sama pada pembagian dengan m.

Bukti:
(i)      Misalkan a º b (mod m) maka $k bulat demikian sehingga a = b + km.
        Misalkan pula b = qm + r dengan 0 £ r < m, maka a = b + km = (qm + r) + km = m(k + q) + r.
        Jadi a dan b mempunyai sisa yang sama (sebesar r) pada pembagian dengan m.
(ii)    Misalkan a = q₁m + r dan b = q₂m + r maka a – b = (q₁ - q₂)m sehingga m\(a – b).
        Jadi a º b (mod m).

Teorema 3

Jika a º b (mod m) maka untuk setiap bilangan bulat x berlaku: (i)         a + x º b + x (mod m) (ii)       ax º bx (mod m) (iii)     -a º -b (mod m)

Bukti:
a º b (mod m)             ®        m\(a – b)

(i)       Karena m\(a – b) maka m\(a + x) – (b + x), sehingga a + x º b + x (mod m).

(ii)      Karena m\(a – b) maka m\x(a – b) ® m\(ax – bx), sehingga ax º bx (mod m).

(iii)     Karena m\(a – b) maka m\–(a – b) ® m\(–a – (–b)), sehingga -a º -b (mod m).

Teorema 4 – Hukum Pembatalan (Cancellation)

Jika c dan m koprima sedangkan ca º cb (mod m) maka a º b (mod m).

Bukti:
ca º cb (mod m)          ®        m\(ca – cb) sehingga m\c(a – b)
Karena c dan m koprima atau (c, m) = 1, maka berdasarkan Teorema 2 Dalil dasar Ilmu Hitung, haruslah m\(a – b). 
Jadi a º b (mod m).

Teorema 5

Jika (c, m) = 1 maka persamaan cx º b (mod m) selalu mempunyai solusi dan solusi ini tunggal mod m.

Bukti:

(i)         (c, m) = 1 maka $s, t bulat demikian sehingga 

          1 = sc + tm              kalikan dengan b

 b = bsc + btm             

 b - bsc = (bt)m

        m\(b – bsc)
        b º bsc (mod m)
        c(bs) º b (mod m)       karena kongruensi adalah relasi ekuivalen
         \ x = bs adalah suatu solusi dari cx º b (mod m).

(ii)       Misalkan x₁ dan x₂ masing-masing adalah solusi dari cx º b (mod m) maka

        cx₁ º b (mod m)                                                          ……………………. (*)
        cx₂ º b (mod m)             ®     b º cx₂ (mod m)         ……………………. (**)
         Berdasarkan Teorema 1, dari (*) dan (**) diperoleh cx₁ º cx₂ (mod m).
         Karena (c, m) = 1 maka x₁ º x₂ (mod m).
         Jadi cx º b (mod m) mempunyai solusi tunggal mod m.

Akibat

Jika m = p (bilangan prima) dan (c, p) = 1, maka cx º b (mod p) mempunyai suatu solusi dan solusi itu tunggal mod p.

Teorema 6

Jika (m1, m2) = 1 maka kedua persamaan x º b1 (mod m1) dan x º b2 (mod m2) mempunyai solusi persekutuan (solusi bersama). Setiap dua solusi adalah kongruen mod m1m2.

Bukti:

Jelas b₁ adalah suatu solusi dari persamaan x º b₁ (mod m₁), karena b₁ º b₁ (mod m₁).

Solusi umumnya adalah b₁ + ym₁ dengan y bulat.

b₁ + ym₁ º b₁ (mod m₁), karena m₁\(b₁ + ym₁ – b₁) = ym₁.

Substitusi solusi tersebut ke persamaan kedua menghasilkan

b₁ + ym₁ º b₂ (mod m₂)

ym₁ º b₂ – b₁ (mod m₂)

m₁y º  b₂ – b₁ (mod m₂)           ini adalah suatu persamaan dalam variabel y

Karena (m₁, m₂) = 1 maka, menurut Teorema 5, persamaan tersebut selalu mempunyai solusi (dapat dipenuhi oleh suatu nilai y).

Misalkan x₁ dan x₂ adalah solusi persekutuan, maka

x₁ º b₁ (mod m₁) dan x₂ º b₁ (mod m₁), sehingga x₁ º x₂ (mod m₁)    ®      m₁\(x₁ – x₂)

x₁ º b₂ (mod m₂) dan x₂ º b₂ (mod m₂), sehingga x₁ º x₂ (mod m₂)    ®   m₂\(x₁ – x₂)

Karena (m₁, m₂) = 1 maka, menurut Teorema 3 Dalil Dasar Ilmu Hitung, m₁m₂\(x₁ – x₂).

Jadi x₁ º  x₂ (mod m₁m₂).

______________________________________________________________________________________________________

Kuliah 6 Teori bilangan oleh Drs. Bachtiar Sjarif, Institut Teknologi Bandung, 21 Desember 1988

-->