Pengantar Teori Bilangan. Kuliah 6

Pengantar Teori Bilangan Kuliah 6

Materi Kuliah  Carl Friedrich Gauss  Teori Dasar Kongruen

3/14/2014

Yanita FMIPA Matematika Unand

2

Carl Friedrich Gauss  Hidup pada masa 1777 − 1855  Mengenalkan konsep Disquisitiones Arithmetica yang dipublikasikanpada tahun 1801.  The Disquisitiones Arithmeticae (Investigasi Aritmatika) adalah buku teks teori bilangan yang ditulis dalam bahasa Latin oleh Carl Friedrich Gauss pada tahun 1798 ketika Gauss berusia 21 tahun dan pertama kali diterbitkan pada tahun 1801 ketika ia berusia 24. Dalam buku ini Gauss menyatukan hasil di teori bilangan yang diperoleh oleh matematikawan seperti Fermat, Euler, Lagrange dan Legendre dan menambahkan hasil baru yang penting.  Publikasi Disquisitiones Arithmeticae pada tahun 1801 sekaligus menempatkan Gauss di peringkat depan matematikawan. 3/14/2014


3

Buku Disquisitiones Aritmaticae terbagi dalam beberapa bagian:

3/14/2014


4

Gauss menemukan rumus Dari bilangan 1 sampai 100 jika dipasangkan dua bilangan berturut—turut bilangan yang paling kecil dan yang paling besar maka jumlahnya adalah selalu 101, yaitu 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101, …, 50 + 51 = 101 Maka terdapat 50 pasangan bilangan yang jumlahnya 101, dan jumlah dari semua bilangan adalah 50 × 101 = 5050. Dengan demikian teknik penghitungan ini memberikan cara lain untuk menurunkan rumus 𝑛(𝑛 + 1) 1 + 2 + 3 + 4 +5 + 6 + ⋯+ 𝑛 = 2 Untuk jumlah 𝑛 pertama bilangan bulat positif. 3/14/2014


5

Proses penurunan rumus 1 + 2 + 3 + 4 + 5 + 6 + ⋯ + 𝑛 =

𝑛(𝑛+1) 2

Perhatikan barisan bilangan 1 sampai 𝑛 dalam dua baris sebagai berikut:

Jika kolom vertikal dijumlahkan, maka masing-masing suku menghasilkan jumlah 𝑛 + 1, yaitu 1 + 𝑛, 2 + 𝑛 − 1 , 3 + 𝑛 − 2 , … , 𝑛 − 1 + 2, 𝑛 + 1 Ketika suku-suku ini ditambahkan, yaitu 𝑛 + 1 + 𝑛 + 1 + 𝑛 + 1 + ⋯+ 𝑛 + 1 = 𝑛 𝑛 + 1 Diperoleh nilai 𝑛(𝑛 + 1). Nilai 𝑛(𝑛 + 1) adalah nilai dari menjumlahkan dua barisan 1 2 3 4 … 𝑛 − 1 𝑛 atau 𝑛(𝑛 + 1) = 2 (1 + 2 + 3 + … + 𝑛) Sehingga Yanita FMIPA Matematika Unand

3/14/2014

6

Sejarah keilmuan dan penemuan penting Gauss • 1792-1795 di Collegium Carolinum (sekarang Braunschweig University of Technology) (atas rekomendasi Duke of Brunswick) • 1795-1798 di Universitas Göttingen • 1796 : Gauss menunjukkan bahwa setiap poligon beraturan 17-sisi (heptadecagon) yang merupakan bilangan prima Fermat (dan, akibatnya, poligon ini mempunyai jumlah sisi yang merupakan hasilkali dari bilangan prima Fermat yang berbeda dan berpangkat 2) dapat dibangun dengan kompas dan sejajar. • Pada tanggal 8 April 1796 ia menjadi yang pertama membuktikan hukum resiprositas kuadrat. Hukum yang sangat umum ini memungkinkan matematika untuk menentukan solvabilitas dari setiap persamaan kuadrat dalam aritmatika modular. • 31 Mei 1796 memberikan pemahaman yang baik tentang bagaimana bilangan prima didistribusikan di antara bilangan bulat. • 10 Juli 1796 Gauss juga menemukan bahwa setiap bilangan bulat positif adalah representable sebagai jumlah dari paling banyak tiga angka segitiga pada dan kemudian menuliskan dalam buku hariannya catatan yang terkenal: "! ΕΥΡΗΚΑ num = Δ + Δ + Δ". • 1 Oktober ia menerbitkan hasil pada jumlah solusi polinomial dengan koefisien di lapangan berhingga, yang 150 tahun kemudian mengakibatkan konjektur Weil. Yanita FMIPA Matematika Unand

7 3/14/2014

Sejarah keilmuan dan penemuan penting Gauss ► Pada tahun 1799 dalam thesis doktoralnya memberikan bukti yang tegas dari Teorema Fundamental Aljabar, yang telah dinyatakan pertama sekali oleh Girard pada tahun 1629 dan kemudian dibuktikan secara tidak sempurna oleh d'Alembert pada tahun 1746, dan kemudian oleh Euler 1749. Teorema itu menegaskan bahwa persamaan polinomial derajat 𝑛 memiliki tepat 𝑛 akar kompleks)

3/14/2014


8

Sifat-Sifat Dasar Konruen Pada Bab I buku Disquisitiones Aritmeticae Gauss mengenalkan konsep kongruen dan symbol ≡.

Definisi Misalkan 𝑛 bilangan bulat positif. Bilangan bulat 𝑎 dan 𝑏 dikatakan kongruen modulo 𝑛, disimbolkan dengan 𝑎 ≡ 𝑏 (mod 𝑛) jika 𝑛 membagi habis 𝑎 − 𝑏 (𝑛| 𝑎 − 𝑏 ), yaitu 𝑎 − 𝑏 = 𝑘𝑛 untuk suatu 𝑘 ∈ ℤ. Catatan: Jika 𝑎 tidak kongruen 𝑏 modulo 𝑛 jika 𝑛 ∤ (𝑎 − 𝑏), dan disimbolkan dengan 𝑎 ≢ 𝑏 (mod 𝑛). 3/14/2014


9

Contoh Misalkan 𝑛 = 7 • Akan diperiksa apakah 3 dan 24 kongruen modulo 7 atau 3 ≡ 7 (mod 7)? Untuk menjawab ini, perhatikan apakah 7|(3 − 24) atau 3 − 24 = 𝑘. 7? 3 − 24 = −21 = −3(7) Berarti ada 𝑘 = −3 ∈ ℤ yang memenuhi 3 − 24 = 𝑘. 7. Ini artinya 3 dan 24 kongruen modulo 7. • Apakah −31 ≡ 11 mod 7 ? • Apakah −15 ≡ −64 mod 7 ? • Apakah 25 ≡ 12 mod 7 ?

3/14/2014


10

Teorema: Untuk sebarang bilangan bulat 𝑎 dan 𝑏, 𝑎 ≡ 𝑏(mod 𝑛) jika dan hanya jika 𝑎 dan 𝑏 membuat sisa nonnegative tertentu yang sama ketika dibagi oleh 𝑛. Bukti ⟹ Diketahui 𝑎 ≡ 𝑏(mod 𝑛). Akan dibuktikan 𝑎 dan 𝑏 membuat sisa nonnegative tertentu yang sama ketika dibagi oleh 𝑛. 𝑎 ≡ 𝑏(mod 𝑛) artinya 𝑛|(𝑎 − 𝑏) atau 𝑎 − 𝑏 = 𝑘𝑛 untuk suatu 𝑘 ∈ ℤ , atau 𝑎 = 𝑘𝑛 + 𝑏 . Berdasarkan pembagian oleh 𝑛, 𝑏 membuat sisa tertentu 𝑟, yaitu 𝑏 = 𝑞𝑛 + 𝑟 dengan 0 ≤ 𝑟 < 𝑛. Selanjutnya dari 𝑎 − 𝑏 = 𝑘𝑛 diperoleh 𝑎 = 𝑏 + 𝑘𝑛 = 𝑞𝑛 + 𝑟 + 𝑘𝑛 = 𝑞 + 𝑘 𝑛 + 𝑟 Ini artinya 𝑎 mempunyai sisa yang sama dengan 𝑏, yaitu 𝑟. ⟸ Diketahui 𝑎 dan 𝑏 mempunyai sisa nonnegative yang sama ketika dibagi oleh 𝑛. Akan dibuktikan 𝑎 ≡ 𝑏(mod 𝑛). 𝑎 dan 𝑏 mempunyai sisa nonnegative yang sama ketika dibagi oleh 𝑛, artinya 𝑟 dan 𝑏 = 𝑞2 𝑛 + 𝑟 dengan sisa yang sama 𝑟 (0 ≤ 𝑟 < 𝑛). Kemudian diperoleh: 𝑎 − 𝑏 = (𝑞1 𝑛 + 𝑟) − (𝑞2 𝑛 + 𝑟) = (𝑞1 − 𝑞2 )𝑛

𝑎 = 𝑞1 𝑛 +

Ini artinya 𝑛|(𝑎 − 𝑏) atau 𝑎 ≡ 𝑏(mod 𝑛). Yanita FMIPA Matematika Unand

3/14/2014

11

Contoh −56 dan −11 dapat ditulis dalam bentuk: −56 = −7 9 + 7 dan −11 = −2 9 + 7, ini artinya −56 dan −11 mempunyai sisa yang sama ketika −56 dan −11 masing-masing dibagi oleh 9 atau −56 dan −11 adalah kongruen modulo 9 atau −56 ≡ − 11 (mod 9). −31 dan 11 dapat ditulis dalam bentuk: −31 = −5 7 + 4 dan 11 = 1.7 + 4 , ini artinya −31 dan 11 mempunyai sisa yang sama ketika −31 dan 11 masing-masing dibagi oleh 7 atau −31 dan 11 adalah kongruen modulo 7 atau −31 ≡ 11 (mod 7) 3/14/2014


12

Teorema Misalkan 𝑛 > 1, dan 𝑛 tetap, 𝑎, 𝑏, 𝑐 adalah sebarang bilangan bulat. Maka berlaku: a) 𝑎 ≡ 𝑎 (mod 𝑛). b) Jika 𝑎 ≡ 𝑏 mod 𝑛 , maka 𝑏 ≡ 𝑎 (mod 𝑛). c) Jika 𝑎 ≡ 𝑏 (mod 𝑛) dan 𝑏 ≡ 𝑐 (mod 𝑛), maka 𝑎 ≡ 𝑐 (mod 𝑛). d) Jika 𝑎 ≡ 𝑏 (mod 𝑛) dan 𝑐 ≡ 𝑑 (mod 𝑛), maka 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (mod 𝑛) dan 𝑎𝑐 ≡ 𝑏𝑑 (mod 𝑛) e) Jika 𝑎 ≡ 𝑏 (mod 𝑛), maka 𝑎 + 𝑐 ≡ 𝑏 + 𝑐 (mod 𝑛) dan 𝑎𝑐 = 𝑏𝑐 (mod 𝑛) f) Jika 𝑎 ≡ 𝑏 (mod 𝑛), maka 𝑎𝑘 ≡ 𝑏 𝑘 (mod 𝑛) untuk sebarang bilangan bulat positif 𝑘. 3/14/2014


13

Teorema 𝑛 Jika 𝑐𝑎 ≡ 𝑐𝑏 mod 𝑛 , maka 𝑎 ≡ 𝑏(mod ) dimana 𝑑 = 𝑝𝑝𝑏(𝑐, 𝑛) 𝑑

Bukti: Diketahui 𝑐𝑎 ≡ 𝑐𝑏 mod 𝑛 dan 𝑑 = 𝑝𝑝𝑏(𝑐, 𝑛). 𝑛 Akan dibuktikan 𝑎 ≡ 𝑏(mod ) 𝑑 𝑐𝑎 ≡ 𝑐𝑏 mod 𝑛 artinya 𝑐𝑎 − 𝑐𝑏 = 𝑘. 𝑛 untuk suatu 𝑘 ∈ ℤ …(∗) 𝑑 = 𝑝𝑝𝑏(𝑐, 𝑛) artinya 𝑑|𝑐 atau 𝑐 = 𝑠𝑑 untuk suatu 𝑠 ∈ ℤ dan 𝑑|𝑛 atau 𝑛 = 𝑟𝑑 untuk suatu 𝑟 ∈ ℤ dengan 𝑠 dan 𝑟 adalah relative prima. Subtitusi nilai 𝑐 = 𝑠𝑑 dan 𝑛 = 𝑟𝑑 pada persamaan (∗), maka diperoleh: 𝑠𝑑𝑎 − 𝑠𝑑𝑏 = 𝑘𝑟𝑑 … (∗∗) Oleh karena 𝑑 ≠ 0, maka persamaan (∗∗) menjadi 𝑠𝑎 − 𝑠𝑏 = 𝑘𝑟 atau 𝑠 𝑎 − 𝑏 = 𝑘𝑟 Ini artinya 𝑟|𝑠(𝑎 − 𝑏) dan 𝑝𝑝𝑏 𝑠, 𝑟 = 1. Berdasarkan Lemma Euclid diperoleh 𝑛 𝑟|(𝑎 − 𝑏), atau 𝑎 ≡ 𝑏 (mod 𝑟) atau 𝑎 ≡ 𝑏(mod ) 𝑑


3/14/2014

14

Akibat 1 Jika 𝑐𝑎 ≡ 𝑐𝑏 (mod 𝑝) 𝑏 (mod 𝑛).

dan 𝑝𝑝𝑏 𝑐, 𝑛 = 1 , maka 𝑎 ≡

Akibat 2 Jika 𝑐𝑎 ≡ 𝑐𝑏 (mod 𝑝) dan 𝑝 ∤ 𝑐, dimana 𝑝 adalah prima, maka 𝑎 ≡ 𝑏 (mod 𝑝).

3/14/2014

Selesai 16-3-2014

15

Pengantar Teori Bilangan. Kuliah 6

Recommend Documents