Teorema 1: (Algoritma Pembagian)
Diberikan bilangan bulat a dan b, dengan b > 0, maka ada bilangan bulat tunggal q dan r yang memenuhi
Bilangan bulat q dan r disebut hasil bagi dan sisa dari pembagian a oleh b.
Bukti:
• Bentuk S = {a - xb | x∈Z; a - xb ≥ 0}. Akan diperlihatkan eksistensi dari r dan q.
• Karena bilangan asli b ≥ 1, maka |a|b ≥ |a| dan a - (-|a|)b = a + |a|b ≥ a + |a| ≥ 0
• Pilih x = (-|a|). Maka a - xb ∈ S. Jadi S ≠ Ø
• Dari Prinsip Terurut Baik, maka S mempunyai unsur terkecil, namakan r.
• Dari definisi S, ada bilangan bulat q yang memenuhi r = a - qb, 0 ≤ r.
• Andaikan r ≥ b, maka a - (q + 1)b = (a - qb) - b = r - b ≥ 0.
• Jadi a-(q+1)b ∈ S. Tetapi a-(q+1)b=r-b<r mengakibatkan kontradiksi dengan r unsur terkecil dari S. Jadi haruslah r < b.
• Akan diperlihatkan ketunggalan dari q dan r.
• Misalkan a dapat dituliskan dalam dua bentuk, a = qb + r = q’b+r’ ; 0 ≤ r < b, 0 ≤ r’< b.
• Maka r’- r = b(q - q’) dan |r’- r| = b| q - q’|.
• Dengan menambahkan –b < -r ≤ 0 dan 0 ≤ r’ < b, maka -b < r’- r < b atau |r’- r| < b.
• Jadi b|q - q’| < b. Akibatnya 0 ≤ |q - q’| < 1.
• Karena |q - q’| bilangan bulat tak negatif, maka haruslah |q - q’| = 0. Akibatnya q = q’. Sehingga r = r’
Akibat (Teorema Euclid)
Jika a dan b bilangan bulat dengan b∈0, maka ada bilangan bulat tunggal q dan r sedemikian hingga a = qb + r, 0 ≤ r < |b|.
Bukti:
• Cukup dengan memperlihatkan untuk b < 0.
• Maka |b| > 0 dan Teorema 1 menjamin ketunggalan q’ dan r yang memenuhi a = q’|b| + r, 0 ≤ r < |b|.
• Karena b < 0, maka |b| = -b.
• Pilih q = -q’, maka a = qb + r, 0 ≤ r < b.
Contoh :
1. Misalkan b = -7. Untuk a = 1, -2, 61, dan -59 dapat dituliskan
1 = 0(-7) + 1
2 = 1(-7) + 5
61 = (-8)(-7) + 5
-59 = 9(-7) + 4.
2. Buktikan bahwa jika b = 2, maka sisa yang mungkin adalah r = 0 dan r = 1.
Bukti :
Jika r = 0, bilangan bulat a berbentuk 2q dan disebut bilangan genap.
Jika r = 1, bilangan a berbentuk 2q + 1 dan disebut bilangan ganjil.
3. Kuadrat dari bilangan bulat mempunyai sisa 0 atau 1 jika dibagi 4.
Bukti:
a genap ➝ a = 2q ➝ a² = (2q)² = 4q² = 4k
a ganjil ➝ a = 2q+1 ➝ a² = (2q+1)² = 4q² + 4q + 1 = 4(q² + q) + 1 = 4k + 1
4. Tentukan (4840, 1512)
Jawab :
4840 = 3 × 1512 + 304
1512 = 4 × 304 + 296
304 = 1 × 296 + 8
296 = 37 × 8 +0
Jadi (4840, 1512) = 8
5. Buktikan bahwa jika ( a, b ) = 1 dan a ⏐bc , maka a ⏐ c.
Bukti :
( a, b ) = 1 ⇒ terdapat m dan n sedemikian sehingga 1 = ma + nb.
a ⏐ bc ⇒ terdapat k sedemikian sehingga bc = ak.
Diperoleh
1 = ma + nb
c . 1 = mac + nbc
c = mac + nak
c = a ( mc + nk ) ⇔ a ⏐ c (terbukti)
6. Diambil r adalah sisa ketika 1059, 1417 dan 2312 dibagi oleh b > 1. Tentukan nilai dari b r.
Jawab:
Berdasarkan Algoritma Pembagian, 1059 = q₁b + r, 1417 = q₂b + r, dan 2312 = q₃b + r untuk bilangan-bilangan bulat q₁, q₂, q₃. Dari sini, 358 = 1417 - 1059 = b (q₂ - q₁), 1253 = 2312 - 1059 = b (q₃ - q₁), dan 895 = 2312 - 1417 = b (q₃ - q₂). Karena itu b | 358 atau b | 2 . 179, b | 1253 atau b | 7 . 179, dan b | 895 atau b | 5 . 179. Karena b > 1, disimpulkan bahwa b = 179. Jadi (sebagai contoh) 1059 = 5 . 179 + 164, yang berarti bahwa r = 164. Disimpulkan bahwa b - r = 179 - 164 = 15.
7. Tunjukkan bahwa n² + 23 dapat dibagi oleh 24 untuk n tak hingga banyaknya.
Bukti:
n² + 23 = n² 1 + 24 = (n - 1) (n + 1) + 24. Jika diambil n = 24k ±1, k = 0, 1, 2,...... , maka pernyataan dapat dibagi oleh 24.
8. Tunjukkan bahwa jika p > 3 adalah prima, maka 24 | (p² - 1).
Bukti:
Berdasarkan Algoritma Pembagian, sembarang bilangan bulat dapat dinyatakan sebagai salah satu dari: 6k, 6k ± 1, 6k ± 2, atau 6k + 3, dengan k ∊ ℤ: Jika p > 3 adalah prima, maka p mempunyai bentuk p = 6k ± 1 (karena pilihan lainnya dapatdibagi 2 atau 3). Dicatat bahwa (6k ± 1)² - 1 = 36k² ± 12k = 12k (3k - 1). Karena k atau 3k - 1 adalah genap, maka 12k (3k - 1) dapat dibagi oleh 24.
9. Buktikan bahwa kuadrat dari sembarang bilangan mempunyai bentuk 4k atau 4k + 1.
Bukti:
Berdasarkan Algoritma Pembagian, sembarang bilangan bulat dapat dinyatakan sebagai salah satu dari: 2a atau 2a + 1. Dikuadratkan,
(2a)² = 4a² , (2a + 1)² = 4 (a² + a) + 1
sehingga pernyataan adalah benar.
10. Buktikan bahwa tidak ada bilangan bulat dalam barisan 11, 111, 1111, 11111, ... yang merupakan kuadrat dari suatu bilangan bulat.
Bukti:
Sudah diperoleh bahwa kuadrat dari sembarang bilangan bulat mempunyai bentuk 4k atau 4k + 1. Semua bilangan dalam barisan 11, 111, 1111, 11111, ... mempunyai bentuk 4k - 1, yang berarti tidak bisa menjadi kuadrat dari sembarang bilangan bulat.
11. Tunjukkan bahwa dari sembarang tiga bilangan bulat, selalu dapat dipilih dua diantaranya, misalnya a dan b, sehingga a³b - ab³ dapat dibagi 10.
Bukti.
Jelas bahwa a³b - ab³ = ab (a - b) (a + b) selalu genap. Jika satu dari tiga bilangan bulat mempunyai bentuk 5k, maka selesai (misalnya diambil a = 5k). Jika tidak, dipilih tiga bilangan yang terletak dalam klas-klas sisa 5k ± 1 atau 5k ± 2. Dua dari tiga bilangan bulat pasti terletak di salah satu dari dua kelompok tersebut. Akibatnya jumlah atau selisih dari dua bilangan tersebut berbentuk 5k dan diperoleh hasil yang diinginkan.
12. Buktikan bahwa jika 3 | a2 + b2 , maka 3 | a dan 3 | b.
Bukti:
Dibuktikan dengan kontraposisi seperti berikut ini. Diandaikan bahwa 3 ∤ a atau 3 ∤ b, dan akan dibuktikan bahwa 3 ∤ (a² + b²) . Dari hipotesis dapat dinyatakan a = 3k ± 1 atau b = 3m ± 1. Dari sini diperoleh a² = 3(3k² ± 2k) + 1 atau a² = 3x + 1, dan serupa dengan itu b² = 3y + 1. Jadi a² + b² = 3x + 1 + 3y + 1 = 3s + 2, yang berarti 3 ∤ (a² + b²) .
13. Tentukan semua bilangan prima berbentuk n³ - 1, untuk bilangan bulat n > 1.
Jawab:
n³ - 1 = (n - 1)(n² + n + 1) . Jika pernyataan ini merupakan bilangan prima, karena n²+n+1 > 1, pasti dipunyai n - 1 = 1, yang berarti n = 2. Jadi bilangan prima yang dimaksud hanyalah 7.
14. Buktikan bahwa n⁴ + 4, n ∈ ℕ, adalah prima hanya untuk n = 1.
Jawab:
15. Tentukan semua bilangan bulat n ≥ 1 yang memenuhi n⁴ + 4ⁿ adalah prima.
Jawab :
Untuk n = 1, jelas bahwa pernyataan merupakan bilangan prima. Lebih lanjut haruslah diambil n adalah ganjil. Untuk n ≥ 3, semua bilangan di bawah ini adalah bulat:
$n^4+2^{2n}=n^4+2n^22^n+2^{2n}-2n^22^n$
$=(n^2+2^n)^2-(n2^{\frac{1}{2}(n+1)})^2$
$=(n^2+2^n+n2^{\frac{1}{2}(n+1)})(n^2+2^n-n2^{\frac{1}{2}(n+1)})$
Ini mudah dilihat bahwa jika n ≥ 3, maka setiap faktor lebih besar 1, sehingga bilangan
tersebut bukan prima.
Diberikan bilangan bulat a dan b, dengan b > 0, maka ada bilangan bulat tunggal q dan r yang memenuhi
a = qb + r, 0 ≤ r < b
Bilangan bulat q dan r disebut hasil bagi dan sisa dari pembagian a oleh b.
Bukti:
• Bentuk S = {a - xb | x∈Z; a - xb ≥ 0}. Akan diperlihatkan eksistensi dari r dan q.
• Karena bilangan asli b ≥ 1, maka |a|b ≥ |a| dan a - (-|a|)b = a + |a|b ≥ a + |a| ≥ 0
• Pilih x = (-|a|). Maka a - xb ∈ S. Jadi S ≠ Ø
• Dari Prinsip Terurut Baik, maka S mempunyai unsur terkecil, namakan r.
• Dari definisi S, ada bilangan bulat q yang memenuhi r = a - qb, 0 ≤ r.
• Andaikan r ≥ b, maka a - (q + 1)b = (a - qb) - b = r - b ≥ 0.
• Jadi a-(q+1)b ∈ S. Tetapi a-(q+1)b=r-b<r mengakibatkan kontradiksi dengan r unsur terkecil dari S. Jadi haruslah r < b.
• Akan diperlihatkan ketunggalan dari q dan r.
• Misalkan a dapat dituliskan dalam dua bentuk, a = qb + r = q’b+r’ ; 0 ≤ r < b, 0 ≤ r’< b.
• Maka r’- r = b(q - q’) dan |r’- r| = b| q - q’|.
• Dengan menambahkan –b < -r ≤ 0 dan 0 ≤ r’ < b, maka -b < r’- r < b atau |r’- r| < b.
• Jadi b|q - q’| < b. Akibatnya 0 ≤ |q - q’| < 1.
• Karena |q - q’| bilangan bulat tak negatif, maka haruslah |q - q’| = 0. Akibatnya q = q’. Sehingga r = r’
Akibat (Teorema Euclid)
Jika a dan b bilangan bulat dengan b∈0, maka ada bilangan bulat tunggal q dan r sedemikian hingga a = qb + r, 0 ≤ r < |b|.
Bukti:
• Cukup dengan memperlihatkan untuk b < 0.
• Maka |b| > 0 dan Teorema 1 menjamin ketunggalan q’ dan r yang memenuhi a = q’|b| + r, 0 ≤ r < |b|.
• Karena b < 0, maka |b| = -b.
• Pilih q = -q’, maka a = qb + r, 0 ≤ r < b.
Contoh :
1. Misalkan b = -7. Untuk a = 1, -2, 61, dan -59 dapat dituliskan
1 = 0(-7) + 1
2 = 1(-7) + 5
61 = (-8)(-7) + 5
-59 = 9(-7) + 4.
2. Buktikan bahwa jika b = 2, maka sisa yang mungkin adalah r = 0 dan r = 1.
Bukti :
Jika r = 0, bilangan bulat a berbentuk 2q dan disebut bilangan genap.
Jika r = 1, bilangan a berbentuk 2q + 1 dan disebut bilangan ganjil.
3. Kuadrat dari bilangan bulat mempunyai sisa 0 atau 1 jika dibagi 4.
Bukti:
a genap ➝ a = 2q ➝ a² = (2q)² = 4q² = 4k
a ganjil ➝ a = 2q+1 ➝ a² = (2q+1)² = 4q² + 4q + 1 = 4(q² + q) + 1 = 4k + 1
4. Tentukan (4840, 1512)
Jawab :
4840 = 3 × 1512 + 304
1512 = 4 × 304 + 296
304 = 1 × 296 + 8
296 = 37 × 8 +0
Jadi (4840, 1512) = 8
5. Buktikan bahwa jika ( a, b ) = 1 dan a ⏐bc , maka a ⏐ c.
Bukti :
( a, b ) = 1 ⇒ terdapat m dan n sedemikian sehingga 1 = ma + nb.
a ⏐ bc ⇒ terdapat k sedemikian sehingga bc = ak.
Diperoleh
1 = ma + nb
c . 1 = mac + nbc
c = mac + nak
c = a ( mc + nk ) ⇔ a ⏐ c (terbukti)
6. Diambil r adalah sisa ketika 1059, 1417 dan 2312 dibagi oleh b > 1. Tentukan nilai dari b r.
Jawab:
Berdasarkan Algoritma Pembagian, 1059 = q₁b + r, 1417 = q₂b + r, dan 2312 = q₃b + r untuk bilangan-bilangan bulat q₁, q₂, q₃. Dari sini, 358 = 1417 - 1059 = b (q₂ - q₁), 1253 = 2312 - 1059 = b (q₃ - q₁), dan 895 = 2312 - 1417 = b (q₃ - q₂). Karena itu b | 358 atau b | 2 . 179, b | 1253 atau b | 7 . 179, dan b | 895 atau b | 5 . 179. Karena b > 1, disimpulkan bahwa b = 179. Jadi (sebagai contoh) 1059 = 5 . 179 + 164, yang berarti bahwa r = 164. Disimpulkan bahwa b - r = 179 - 164 = 15.
7. Tunjukkan bahwa n² + 23 dapat dibagi oleh 24 untuk n tak hingga banyaknya.
Bukti:
n² + 23 = n² 1 + 24 = (n - 1) (n + 1) + 24. Jika diambil n = 24k ±1, k = 0, 1, 2,...... , maka pernyataan dapat dibagi oleh 24.
8. Tunjukkan bahwa jika p > 3 adalah prima, maka 24 | (p² - 1).
Bukti:
Berdasarkan Algoritma Pembagian, sembarang bilangan bulat dapat dinyatakan sebagai salah satu dari: 6k, 6k ± 1, 6k ± 2, atau 6k + 3, dengan k ∊ ℤ: Jika p > 3 adalah prima, maka p mempunyai bentuk p = 6k ± 1 (karena pilihan lainnya dapatdibagi 2 atau 3). Dicatat bahwa (6k ± 1)² - 1 = 36k² ± 12k = 12k (3k - 1). Karena k atau 3k - 1 adalah genap, maka 12k (3k - 1) dapat dibagi oleh 24.
9. Buktikan bahwa kuadrat dari sembarang bilangan mempunyai bentuk 4k atau 4k + 1.
Bukti:
Berdasarkan Algoritma Pembagian, sembarang bilangan bulat dapat dinyatakan sebagai salah satu dari: 2a atau 2a + 1. Dikuadratkan,
(2a)² = 4a² , (2a + 1)² = 4 (a² + a) + 1
sehingga pernyataan adalah benar.
10. Buktikan bahwa tidak ada bilangan bulat dalam barisan 11, 111, 1111, 11111, ... yang merupakan kuadrat dari suatu bilangan bulat.
Bukti:
Sudah diperoleh bahwa kuadrat dari sembarang bilangan bulat mempunyai bentuk 4k atau 4k + 1. Semua bilangan dalam barisan 11, 111, 1111, 11111, ... mempunyai bentuk 4k - 1, yang berarti tidak bisa menjadi kuadrat dari sembarang bilangan bulat.
11. Tunjukkan bahwa dari sembarang tiga bilangan bulat, selalu dapat dipilih dua diantaranya, misalnya a dan b, sehingga a³b - ab³ dapat dibagi 10.
Bukti.
Jelas bahwa a³b - ab³ = ab (a - b) (a + b) selalu genap. Jika satu dari tiga bilangan bulat mempunyai bentuk 5k, maka selesai (misalnya diambil a = 5k). Jika tidak, dipilih tiga bilangan yang terletak dalam klas-klas sisa 5k ± 1 atau 5k ± 2. Dua dari tiga bilangan bulat pasti terletak di salah satu dari dua kelompok tersebut. Akibatnya jumlah atau selisih dari dua bilangan tersebut berbentuk 5k dan diperoleh hasil yang diinginkan.
12. Buktikan bahwa jika 3 | a2 + b2 , maka 3 | a dan 3 | b.
Bukti:
Dibuktikan dengan kontraposisi seperti berikut ini. Diandaikan bahwa 3 ∤ a atau 3 ∤ b, dan akan dibuktikan bahwa 3 ∤ (a² + b²) . Dari hipotesis dapat dinyatakan a = 3k ± 1 atau b = 3m ± 1. Dari sini diperoleh a² = 3(3k² ± 2k) + 1 atau a² = 3x + 1, dan serupa dengan itu b² = 3y + 1. Jadi a² + b² = 3x + 1 + 3y + 1 = 3s + 2, yang berarti 3 ∤ (a² + b²) .
13. Tentukan semua bilangan prima berbentuk n³ - 1, untuk bilangan bulat n > 1.
Jawab:
n³ - 1 = (n - 1)(n² + n + 1) . Jika pernyataan ini merupakan bilangan prima, karena n²+n+1 > 1, pasti dipunyai n - 1 = 1, yang berarti n = 2. Jadi bilangan prima yang dimaksud hanyalah 7.
14. Buktikan bahwa n⁴ + 4, n ∈ ℕ, adalah prima hanya untuk n = 1.
Jawab:
15. Tentukan semua bilangan bulat n ≥ 1 yang memenuhi n⁴ + 4ⁿ adalah prima.
Jawab :
Untuk n = 1, jelas bahwa pernyataan merupakan bilangan prima. Lebih lanjut haruslah diambil n adalah ganjil. Untuk n ≥ 3, semua bilangan di bawah ini adalah bulat:
$n^4+2^{2n}=n^4+2n^22^n+2^{2n}-2n^22^n$
$=(n^2+2^n)^2-(n2^{\frac{1}{2}(n+1)})^2$
$=(n^2+2^n+n2^{\frac{1}{2}(n+1)})(n^2+2^n-n2^{\frac{1}{2}(n+1)})$
Ini mudah dilihat bahwa jika n ≥ 3, maka setiap faktor lebih besar 1, sehingga bilangan
tersebut bukan prima.
No comments:
Post a Comment