Page 27 - E-MODUL STRUKTUR ALJABAR

Definisi I-2 Jika ≡ ( ) 0 ≤ ≤ , maka r disebut residu terkecil dari a

modulo n. Himpunan {0,1,2,3,4,…, (n-1)} dinamakan himpunan residu

terkecil modulo n.
Contoh 2.12

Residu terkeil dari 29 modulo 2 adalah 1 karena 29 : 2 sisa 1

Residu terkecil dari 29 modulo 3 adalah 2 karena 29 : 3 sisa 2

J. Induksi Matematika

Sebagian besar metode pembuktian dalam matematika adalah metode deduksi, yaitu

mengikuti sejumlah pemikiran (premis yang bersifat umum) untuk memperoleh suatu konklusi
atau kesimpulan yang sifatnya khusus. Namun, adakalanya metode deduksi tidak dapat

digunakan, misalnya untuk membuktikan jumlah berhingga bilangan ganjil yang pertama
merupakan suatu kuadrat sempurna. Pada kasus seperti itu digunakan metode induksi, yaitu

memperoleh kesimpulan yang bersifat umum dari informasi-informasi (premis yang bersifat
khusus). Alat bukti yang bisa digunakan pada permasalahan ini adalah induksi matematika.

Prinsip induksi matematika menggunakan bilangan asli karena bilangan asli memiliki

sifat terurut dengan baik. Setiap subhimpunan tak kosong dari N mempunyai elemen terkecil.
Misalkan ⊆ , ≠ 0, ∃ ∈ ∋ ≤ , ∀ ∈ .

Teorema : (Prinsip Induksi Matematika)

Misalkan S subhimpunan takkosong dari N yang mempunyai sifat berikut:
1. 1 ∈

2. Jika ∈ , + 1 ∈

Maka S = N
Bukti :

Karena ⊆ , ⊆
Andaikan ⊈ , N/S takkosong. Menurut sifat terurut dengan baik N/S memiliki elemen

terkecil, misalkan m. Perhatikan bahwa ≠ 1 1 ∈ . Karena itu, m > 1 sehingga ( −

1) ∈ . Tetapi karena m elemen terkecil dari N/S dan m – 1 < m, maka m – 1 haruslah anggota
S. Sekarang, jika − 1 ∈ , ( − 1) + 1 = ∈ . Hal

ini kontradiksi dengan ∈ / . Jadi pengandaian salah sehingga haruslah ⊆ , akibatnya , S

= N.
Secara praktis penggunaan prinsip induksi matematika dapat dilakukan dengan cara

berikut.

E-Modul Struktur Aljabar Page 21