Bimbel Jakarta Timur akan mengupas tuntas Dalam matematika, teorema fundamental aritmatika, disebut juga teorema faktorisasi unik dan teorema faktorisasi prima
Teorema Dasar Aritmatika mengungkapkan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima atau bentuk bilangan prima
Tentang Teorema Dasar Aritmatika
Teorema Dasar Aritmatika mengungkapkan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima atau dapat dinyatakan dalam c. Dengan kata lain, semua bilangan asli dapat dinyatakan dalam bentuk perkalian faktor primanya. Perlu diingat, faktor prima adalah bilangan yang hanya dapat dibagi oleh 1 dan dirinya sendiri. Misalnya, angka 35 dapat dituliskan dalam bentuk faktor primanya sebagai:
Demikian pula, bilangan lain 114560 dapat direpresentasikan sebagai perkalian faktor primanya dengan menggunakan metode faktorisasi prima,
114560 = 27 × 5 × 179
Jadi, kita telah memfaktorkan 114560 sebagai perkalian dari pangkat bilangan primanya.
Oleh karena itu, setiap bilangan asli dapat dinyatakan dalam bentuk perkalian pangkat bilangan primanya. Pernyataan ini dikenal sebagai Teorema Dasar Aritmatika, teorema faktorisasi unik atau teorema faktorisasi prima unik.
Bukti Teorema Dasar Aritmatika
Dalam teori bilangan, bilangan komposit diekspresikan dalam bentuk perkalian bilangan prima dan faktorisasi ini unik terlepas dari urutan munculnya faktor prima.
Dari teorema ini kita juga dapat melihat bahwa tidak hanya bilangan komposit yang dapat difaktorkan sebagai hasil perkalian bilangan primanya, tetapi juga untuk setiap bilangan komposit faktorisasinya unik, tidak mempertimbangkan urutan kemunculan faktor prima.
Dengan kata sederhana, hanya ada satu cara untuk merepresentasikan bilangan asli dengan perkalian faktor prima. Fakta ini juga dapat dinyatakan sebagai:
Faktorisasi prima dari bilangan asli apa pun dikatakan unik kecuali urutan faktornya.
Secara umum, bilangan komposit “a” dapat dinyatakan sebagai,
a = p1 p2 p3 ………… pn, dimana p1, p2, p3 ………… pn adalah faktor prima dari suatu bilangan yang ditulis dalam urutan menaik yaitu p1≤p2≤p3 ………… ≤pn.
Menulis bilangan prima dalam urutan menaik membuat faktorisasi bersifat unik.
ContohTeorema Dasar Aritmatika
Contoh Soal: Dalam perlombaan balap formula waktu yang dibutuhkan oleh dua mobil balap A dan B untuk menyelesaikan 1 putaran lintasan masing-masing adalah 30 menit dan 45 menit. Setelah berapa lama kedua mobil akan bertemu lagi di titik awal?
Pembahasan:
Karena waktu yang dibutuhkan mobil B lebih banyak dibandingkan dengan waktu yang dibutuhkan A untuk menyelesaikan satu putaran, maka dapat diasumsikan bahwa A akan tiba lebih awal dan kedua mobil tersebut akan bertemu lagi ketika A telah mencapai titik awal. Waktu ini dapat dihitung dengan mencari KPK dari waktu yang dibutuhkan masing-masing.
30 = 2 × 3 × 5
45 = 3 × 3 × 5
KPK adalah 90.
Dengan demikian, kedua mobil akan bertemu di titik awal setelah 90 menit.
Faktorisasi Prima
Teorema dasar aritmatika mengatakan bahwa "faktorisasi setiap bilangan komposit dapat dinyatakan sebagai hasil dari bilangan prima terlepas dari urutan terjadinya faktor prima dari bilangan tersebut". Teorema dasar aritmatika adalah metode yang sangat berguna untuk memahami faktorisasi prima dari sembarang bilangan.
Pemfaktoran yang Unik
Pernyataan teorema dasar aritmatika adalah: "Setiap bilangan komposit dapat difaktorkan sebagai perkalian bilangan prima, dan pemfaktoran ini unik, terlepas dari urutan munculnya faktor prima."
Sebagai contoh, mari kita cari faktorisasi prima dari 240.
Dari contoh 240 = 2 × 2 × 2 × 2 × 3 × 5. Teorema ini lebih lanjut menyatakan bahwa faktorisasi ini harus unik. Artinya, tidak ada cara lain untuk menyatakan 240 sebagai perkalian bilangan prima. Tentu saja, kita dapat mengubah urutan terjadinya faktor prima. Misalnya, faktorisasi prima dapat ditulis sebagai: 240 = 31 × 24 × 51 atau 31 × 22 × 51 × 22 dst. Tetapi himpunan faktor prima (dan berapa kali setiap faktor muncul) adalah unik. Artinya, 240 hanya dapat memiliki satu kemungkinan faktorisasi prima, dengan empat faktor dari 2 yaitu 24, satu faktor dari 3 yaitu 31, dan satu faktor dari 5 yaitu 51.
Pembuktian Teorema Dasar Aritmatika
Untuk membuktikan teorema dasar aritmatika, kita harus membuktikan keberadaan dan keunikan faktorisasi prima. Dengan demikian, teorema dasar pembuktian aritmetika dilakukan dalam dua langkah. Kita akan membuktikan bahwa untuk setiap bilangan bulat, n ≥ 2, dapat dinyatakan sebagai Hasil bilangan prima dengan cara unik: n = p1 × p2 ×⋯ × pi.
Langkah 1 - Adanya Faktorisasi Prima
Kita akan membuktikannya dengan menggunakan induksi matematika.
Langkah Dasar: Pernyataan benar untuk n = 2.
Langkah Asumsi: Mari kita asumsikan bahwa pernyataan itu benar untuk n = k.
Maka, k dapat ditulis sebagai perkalian bilangan prima.
Langkah Induksi: Mari kita buktikan bahwa pernyataan itu benar untuk n = k + 1.
Jika k + 1 adalah bilangan prima, maka kasusnya jelas.
Jika k + 1 BUKAN prima, maka pasti memiliki beberapa faktor prima, katakanlah p.
Maka k + 1 = pj, di mana j < k →(1)
Sejak j < k, dengan "langkah induktif", k dapat ditulis sebagai hasil kali bilangan prima.
Jadi, dari (1), k + 1 juga dapat dituliskan sebagai hasil kali bilangan prima. Jadi, dengan induksi matematika, "keberadaan faktorisasi" dibuktikan.
Langkah 2 - Keunikan Faktorisasi Prima
Mari kita asumsikan bahwa n dapat ditulis sebagai hasil kali bilangan prima dengan dua cara berbeda, katakanlah,
n = p1p2⋯pi, atau,
n= q1q2⋯qj
Karena ini adalah faktorisasi prima, q1,q2,…,qj adalah bilangan koprime (karena merupakan bilangan prima).
Oleh karena itu, menurut lemma Euclid, p1 hanya membagi satu bilangan prima.
Perhatikan bahwa q1 adalah bilangan prima terkecil sehingga p1=q1.
Dengan cara yang sama, kita dapat membuktikan bahwa pn = qn, untuk semua n.
Oleh karena itu, i = j.
Jadi, faktorisasi prima dari n adalah unik.
FPB dan KPK Menggunakan Teorema Dasar Aritmatika
Untuk mencari FPB dan KPK dari dua bilangan, kita menggunakan teorema dasar aritmetika. Untuk ini, pertama-tama kita mencari faktorisasi prima dari kedua bilangan tersebut. Selanjutnya, kita mempertimbangkan hal-hal berikut:
Nilai FPB adalah nilai bilangan yang sama dan memiliki pangkat yang lebih kecil.
Nilai KPK dari hasil pangkat terbesar dari setiap faktor prima persekutuan. (jika keduanya sama maka ambil salah satunya).
Sebagai contoh, mari kita cari FPB dari 850 dan 680. Untuk ini, pertama-tama kita akan mencari faktorisasi prima dari bilangan-bilangan tersebut.
Faktorisasi prima dari 850 = 21 × 52 × 171
Faktorisasi prima dari 680 = 23 × 51 × 171
FPB Faktor Persekutuan Terbesar adalah faktor persekutuan yang nilainya terbesar di antara faktor-faktor persekutuan lainnya. (Faktor adalah sejumlah bilangan yang habis membagi sebuah bilangan tanpa sisa). Nilai FPB adalah nilai bilangan yang sama dan memiliki pangkat yang lebih kecil.
Maka, nilai FPB (850, 680) = 21 × 51 × 171 = 170.
KPK atau Kelipatan Persekutuan Terkecil adalah bilangan kelipatan terkecil yang sama dari banyaknya suatu bilangan tertentu.(Kelipatan adalah mengalikan bilangan dengan setiap bilangan asli secara berurutan.) dengan mengambil hasil pangkat terbesar dari setiap faktor prima persekutuan. (jika keduanya sama maka ambil salah satunya).
Jadi, KPK (850, 680) = 23 × 52 × 171 = 3400.
Dengan demikian,
FPB (850, 680) = 170
KPK (850, 680) = 3400
Pernyataan Teorema
Teorema Dasar Aritmatika menyatakan bahwa kita dapat menguraikan bilangan apa pun secara unik menjadi hasil bilangan prima. Misalnya, 350 = 2*7*5², dan tidak ada cara lain untuk menulis 350 sebagai hasil kali bilangan prima.
Bukti
Bagian I: Lemma Bezout
Lemma Bezout memberitahu kita bahwa, jika dua bilangan a dan b tidak berbagi faktor prima selain 1 dan -1, maka kita dapat menemukan q dan s sehingga qa+sb=1.
Oke, mari luangkan waktu untuk mencernanya dengan contoh yang berhasil. Pertimbangkan 7, dan 9. Satu-satunya angka yang membagi 7 adalah {7,1,-1,-7}. Satu-satunya angka yang membagi 9 adalah {9,3,1,-1,-3,-9}. Jadi, 7 dan 9 tidak berbagi faktor prima. Tugas kita sekarang adalah mencari dua bilangan q dan s sehingga 7q + 9s = 1.
Bisa sajakita menebak beberapa angka, dan mungkin kita menemukan bahwa 9*3 = 27, dan 7*4 = 28. Jadi kita bisa mencoba q=4, dan s=-3. Kemudian:
7*4–9*3 = 1.
Bukti Bezout Lemma
Catatan : jika sudah meyakini pada bukti Lemma Bezout, maka tidak apa-apa untuk melompat ke bagian berikutnya. Kita akan melihat ini sangat gampang di cerna.
Sebelumnya kita tebak beberapa angka sampai diperkirakan bahwa 7*4–9*3=1.
Namun, menebak tidak membuktikan hal-hal secara umum. Kita sekarang mencoba membuktikan hasilnya lagi untuk kasus 7 dan 9. Metode sistematis ini bekerja pada semua angka!
Kita menggunakan Algoritma Euclidean. Algoritma Euclidean adalah algoritma untuk mencari PBB (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. dari dua buah bilangan bulat Artinya, kita menggunakan pembagian dengan sisa untuk menemukan pembagi persekutuan terbesar dari dua bilangan.
Ambil 7 dan 9.
9 = 7 + 2
7 = 3*2 + 1
Kita memulai lagi dari 1 dalam bentuk 7 dan 9. sebagai berikut:
1 = 7–3*2
1 = 7–3(9–7)
1=7–3*9 +3*7 = 4*7–3*9
Kita pasang angka 49 dan 51.
51 = 49 + 2
49 = 2*24 + 1
Sekarang kita merekonstruksi:
1 = 49–2*24
1 = 49–24(51–49)
1 = 25*49–24*51
Diberikan dua angka yang tidak berbagi faktor, kita dapat melalui proses yang sama, hanya berpotensi dengan lebih banyak langkah. Kita melakukan satu contoh terakhir.
Kita pasang angka 99 dan 35.
99 = 2*35 + 29
35 = 29 + 6
29 = 4*6 + 5
6 = 1*5 + 1
Sekarang mari kita rekonstruksi langsung di TKP:
1 = 6–5
1=6-(29–4*6) = 5*6–29
1=5*(35–29) — 29 = 5*35 -6*29
1=5*35 — 6*(99–2*35)=17*35–6*99
Bagian II: Lemma Euclid
Lemma Euclid mengatakan bahwa jika suatu bilangan prima p membagi x dikalikan y, maka p membagi x, atau p membagi y (dan berpotensi keduanya).
Misalnya, 3 membagi 3465=99*35. Lemma Euclid mengatakan bahwa 3 membagi 99, atau 3 membagi 35. Kita dapat melihat bahwa 3 membagi 99, sebagai 99=3*33
Misalkan p membagi xy, tetapi p itu tidak membagi x. Kemudian, dengan Lemma Bezout, kita dapat menemukan t, s sehingga:
t*p + s*x = 1
Kemudian, kalikan dengan y:
t*p*y + s*x*y = y.
Bagi dengan p:
t*y +s*xy/p = y/p
Karena xy/p adalah bilangan bulat, kita simpulkan bahwa y/p adalah bilangan bulat, dan karenanya p membagi y.
Kita mengulangi langkah-langkah ini dengan contoh yang berhasil. Katakanlah kita tahu bahwa 3 membagi 99*35, sebagai 35*99=3*1155, tetapi tidak membagi 35. Maka:
12*3 +35(-1) =12*3 -35 = 1
12*3*99 -35*99 = 99.
12*99–35*99/3 = 99/3
Seperti yang kita ketahui 35*99/3 adalah bilangan bulat, oleh karena itu kita tahu 12*99–35*99/3 adalah bilangan bulat. Jadi 3 membagi 99.
Bimbel Jakarta Timur akan mengupas tuntas Dalam matematika, teorema fundamental aritmatika, disebut juga teorema faktorisasi unik dan teorema faktorisasi prima
Teorema Dasar Aritmatika mengungkapkan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima atau bentuk bilangan prima
Tentang Teorema Dasar Aritmatika
Teorema Dasar Aritmatika mengungkapkan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima atau dapat dinyatakan dalam c. Dengan kata lain, semua bilangan asli dapat dinyatakan dalam bentuk perkalian faktor primanya. Perlu diingat, faktor prima adalah bilangan yang hanya dapat dibagi oleh 1 dan dirinya sendiri. Misalnya, angka 35 dapat dituliskan dalam bentuk faktor primanya sebagai:
Demikian pula, bilangan lain 114560 dapat direpresentasikan sebagai perkalian faktor primanya dengan menggunakan metode faktorisasi prima,
114560 = 27 × 5 × 179
Jadi, kita telah memfaktorkan 114560 sebagai perkalian dari pangkat bilangan primanya.
Oleh karena itu, setiap bilangan asli dapat dinyatakan dalam bentuk perkalian pangkat bilangan primanya. Pernyataan ini dikenal sebagai Teorema Dasar Aritmatika, teorema faktorisasi unik atau teorema faktorisasi prima unik.
Bukti Teorema Dasar Aritmatika
Dalam teori bilangan, bilangan komposit diekspresikan dalam bentuk perkalian bilangan prima dan faktorisasi ini unik terlepas dari urutan munculnya faktor prima.
Dari teorema ini kita juga dapat melihat bahwa tidak hanya bilangan komposit yang dapat difaktorkan sebagai hasil perkalian bilangan primanya, tetapi juga untuk setiap bilangan komposit faktorisasinya unik, tidak mempertimbangkan urutan kemunculan faktor prima.
Dengan kata sederhana, hanya ada satu cara untuk merepresentasikan bilangan asli dengan perkalian faktor prima. Fakta ini juga dapat dinyatakan sebagai:
Faktorisasi prima dari bilangan asli apa pun dikatakan unik kecuali urutan faktornya.
Secara umum, bilangan komposit “a” dapat dinyatakan sebagai,
a = p1 p2 p3 ………… pn, dimana p1, p2, p3 ………… pn adalah faktor prima dari suatu bilangan yang ditulis dalam urutan menaik yaitu p1≤p2≤p3 ………… ≤pn.
Menulis bilangan prima dalam urutan menaik membuat faktorisasi bersifat unik.
ContohTeorema Dasar Aritmatika
Contoh Soal: Dalam perlombaan balap formula waktu yang dibutuhkan oleh dua mobil balap A dan B untuk menyelesaikan 1 putaran lintasan masing-masing adalah 30 menit dan 45 menit. Setelah berapa lama kedua mobil akan bertemu lagi di titik awal?
Pembahasan:
Karena waktu yang dibutuhkan mobil B lebih banyak dibandingkan dengan waktu yang dibutuhkan A untuk menyelesaikan satu putaran, maka dapat diasumsikan bahwa A akan tiba lebih awal dan kedua mobil tersebut akan bertemu lagi ketika A telah mencapai titik awal. Waktu ini dapat dihitung dengan mencari KPK dari waktu yang dibutuhkan masing-masing.
30 = 2 × 3 × 5
45 = 3 × 3 × 5
KPK adalah 90.
Dengan demikian, kedua mobil akan bertemu di titik awal setelah 90 menit.
Faktorisasi Prima
Teorema dasar aritmatika mengatakan bahwa "faktorisasi setiap bilangan komposit dapat dinyatakan sebagai hasil dari bilangan prima terlepas dari urutan terjadinya faktor prima dari bilangan tersebut". Teorema dasar aritmatika adalah metode yang sangat berguna untuk memahami faktorisasi prima dari sembarang bilangan.
Pemfaktoran yang Unik
Pernyataan teorema dasar aritmatika adalah: "Setiap bilangan komposit dapat difaktorkan sebagai perkalian bilangan prima, dan pemfaktoran ini unik, terlepas dari urutan munculnya faktor prima."
Sebagai contoh, mari kita cari faktorisasi prima dari 240.
Dari contoh 240 = 2 × 2 × 2 × 2 × 3 × 5. Teorema ini lebih lanjut menyatakan bahwa faktorisasi ini harus unik. Artinya, tidak ada cara lain untuk menyatakan 240 sebagai perkalian bilangan prima. Tentu saja, kita dapat mengubah urutan terjadinya faktor prima. Misalnya, faktorisasi prima dapat ditulis sebagai: 240 = 31 × 24 × 51 atau 31 × 22 × 51 × 22 dst. Tetapi himpunan faktor prima (dan berapa kali setiap faktor muncul) adalah unik. Artinya, 240 hanya dapat memiliki satu kemungkinan faktorisasi prima, dengan empat faktor dari 2 yaitu 24, satu faktor dari 3 yaitu 31, dan satu faktor dari 5 yaitu 51.
Pembuktian Teorema Dasar Aritmatika
Untuk membuktikan teorema dasar aritmatika, kita harus membuktikan keberadaan dan keunikan faktorisasi prima. Dengan demikian, teorema dasar pembuktian aritmetika dilakukan dalam dua langkah. Kita akan membuktikan bahwa untuk setiap bilangan bulat, n ≥ 2, dapat dinyatakan sebagai Hasil bilangan prima dengan cara unik: n = p1 × p2 ×⋯ × pi.
Langkah 1 - Adanya Faktorisasi Prima
Kita akan membuktikannya dengan menggunakan induksi matematika.
Langkah Dasar: Pernyataan benar untuk n = 2.
Langkah Asumsi: Mari kita asumsikan bahwa pernyataan itu benar untuk n = k.
Maka, k dapat ditulis sebagai perkalian bilangan prima.
Langkah Induksi: Mari kita buktikan bahwa pernyataan itu benar untuk n = k + 1.
Jika k + 1 adalah bilangan prima, maka kasusnya jelas.
Jika k + 1 BUKAN prima, maka pasti memiliki beberapa faktor prima, katakanlah p.
Maka k + 1 = pj, di mana j < k →(1)
Sejak j < k, dengan "langkah induktif", k dapat ditulis sebagai hasil kali bilangan prima.
Jadi, dari (1), k + 1 juga dapat dituliskan sebagai hasil kali bilangan prima. Jadi, dengan induksi matematika, "keberadaan faktorisasi" dibuktikan.
Langkah 2 - Keunikan Faktorisasi Prima
Mari kita asumsikan bahwa n dapat ditulis sebagai hasil kali bilangan prima dengan dua cara berbeda, katakanlah,
n = p1p2⋯pi, atau,
n= q1q2⋯qj
Karena ini adalah faktorisasi prima, q1,q2,…,qj adalah bilangan koprime (karena merupakan bilangan prima).
Oleh karena itu, menurut lemma Euclid, p1 hanya membagi satu bilangan prima.
Perhatikan bahwa q1 adalah bilangan prima terkecil sehingga p1=q1.
Dengan cara yang sama, kita dapat membuktikan bahwa pn = qn, untuk semua n.
Oleh karena itu, i = j.
Jadi, faktorisasi prima dari n adalah unik.
FPB dan KPK Menggunakan Teorema Dasar Aritmatika
Untuk mencari FPB dan KPK dari dua bilangan, kita menggunakan teorema dasar aritmetika. Untuk ini, pertama-tama kita mencari faktorisasi prima dari kedua bilangan tersebut. Selanjutnya, kita mempertimbangkan hal-hal berikut:
Nilai FPB adalah nilai bilangan yang sama dan memiliki pangkat yang lebih kecil.
Nilai KPK dari hasil pangkat terbesar dari setiap faktor prima persekutuan. (jika keduanya sama maka ambil salah satunya).
Sebagai contoh, mari kita cari FPB dari 850 dan 680. Untuk ini, pertama-tama kita akan mencari faktorisasi prima dari bilangan-bilangan tersebut.
Faktorisasi prima dari 850 = 21 × 52 × 171
Faktorisasi prima dari 680 = 23 × 51 × 171
FPB Faktor Persekutuan Terbesar adalah faktor persekutuan yang nilainya terbesar di antara faktor-faktor persekutuan lainnya. (Faktor adalah sejumlah bilangan yang habis membagi sebuah bilangan tanpa sisa). Nilai FPB adalah nilai bilangan yang sama dan memiliki pangkat yang lebih kecil.
Maka, nilai FPB (850, 680) = 21 × 51 × 171 = 170.
KPK atau Kelipatan Persekutuan Terkecil adalah bilangan kelipatan terkecil yang sama dari banyaknya suatu bilangan tertentu.(Kelipatan adalah mengalikan bilangan dengan setiap bilangan asli secara berurutan.) dengan mengambil hasil pangkat terbesar dari setiap faktor prima persekutuan. (jika keduanya sama maka ambil salah satunya).
Jadi, KPK (850, 680) = 23 × 52 × 171 = 3400.
Dengan demikian,
FPB (850, 680) = 170
KPK (850, 680) = 3400
Pernyataan Teorema
Teorema Dasar Aritmatika menyatakan bahwa kita dapat menguraikan bilangan apa pun secara unik menjadi hasil bilangan prima. Misalnya, 350 = 2*7*5², dan tidak ada cara lain untuk menulis 350 sebagai hasil kali bilangan prima.
Bukti
Bagian I: Lemma Bezout
Lemma Bezout memberitahu kita bahwa, jika dua bilangan a dan b tidak berbagi faktor prima selain 1 dan -1, maka kita dapat menemukan q dan s sehingga qa+sb=1.
Oke, mari luangkan waktu untuk mencernanya dengan contoh yang berhasil. Pertimbangkan 7, dan 9. Satu-satunya angka yang membagi 7 adalah {7,1,-1,-7}. Satu-satunya angka yang membagi 9 adalah {9,3,1,-1,-3,-9}. Jadi, 7 dan 9 tidak berbagi faktor prima. Tugas kita sekarang adalah mencari dua bilangan q dan s sehingga 7q + 9s = 1.
Bisa sajakita menebak beberapa angka, dan mungkin kita menemukan bahwa 9*3 = 27, dan 7*4 = 28. Jadi kita bisa mencoba q=4, dan s=-3. Kemudian:
7*4–9*3 = 1.
Bukti Bezout Lemma
Catatan : jika sudah meyakini pada bukti Lemma Bezout, maka tidak apa-apa untuk melompat ke bagian berikutnya. Kita akan melihat ini sangat gampang di cerna.
Sebelumnya kita tebak beberapa angka sampai diperkirakan bahwa 7*4–9*3=1.
Namun, menebak tidak membuktikan hal-hal secara umum. Kita sekarang mencoba membuktikan hasilnya lagi untuk kasus 7 dan 9. Metode sistematis ini bekerja pada semua angka!
Kita menggunakan Algoritma Euclidean. Algoritma Euclidean adalah algoritma untuk mencari PBB (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. dari dua buah bilangan bulat Artinya, kita menggunakan pembagian dengan sisa untuk menemukan pembagi persekutuan terbesar dari dua bilangan.
Ambil 7 dan 9.
9 = 7 + 2
7 = 3*2 + 1
Kita memulai lagi dari 1 dalam bentuk 7 dan 9. sebagai berikut:
1 = 7–3*2
1 = 7–3(9–7)
1=7–3*9 +3*7 = 4*7–3*9
Kita pasang angka 49 dan 51.
51 = 49 + 2
49 = 2*24 + 1
Sekarang kita merekonstruksi:
1 = 49–2*24
1 = 49–24(51–49)
1 = 25*49–24*51
Diberikan dua angka yang tidak berbagi faktor, kita dapat melalui proses yang sama, hanya berpotensi dengan lebih banyak langkah. Kita melakukan satu contoh terakhir.
Kita pasang angka 99 dan 35.
99 = 2*35 + 29
35 = 29 + 6
29 = 4*6 + 5
6 = 1*5 + 1
Sekarang mari kita rekonstruksi langsung di TKP:
1 = 6–5
1=6-(29–4*6) = 5*6–29
1=5*(35–29) — 29 = 5*35 -6*29
1=5*35 — 6*(99–2*35)=17*35–6*99
Bagian II: Lemma Euclid
Lemma Euclid mengatakan bahwa jika suatu bilangan prima p membagi x dikalikan y, maka p membagi x, atau p membagi y (dan berpotensi keduanya).
Misalnya, 3 membagi 3465=99*35. Lemma Euclid mengatakan bahwa 3 membagi 99, atau 3 membagi 35. Kita dapat melihat bahwa 3 membagi 99, sebagai 99=3*33
Misalkan p membagi xy, tetapi p itu tidak membagi x. Kemudian, dengan Lemma Bezout, kita dapat menemukan t, s sehingga:
t*p + s*x = 1
Kemudian, kalikan dengan y:
t*p*y + s*x*y = y.
Bagi dengan p:
t*y +s*xy/p = y/p
Karena xy/p adalah bilangan bulat, kita simpulkan bahwa y/p adalah bilangan bulat, dan karenanya p membagi y.
Kita mengulangi langkah-langkah ini dengan contoh yang berhasil. Katakanlah kita tahu bahwa 3 membagi 99*35, sebagai 35*99=3*1155, tetapi tidak membagi 35. Maka:
12*3 +35(-1) =12*3 -35 = 1
12*3*99 -35*99 = 99.
12*99–35*99/3 = 99/3
Seperti yang kita ketahui 35*99/3 adalah bilangan bulat, oleh karena itu kita tahu 12*99–35*99/3 adalah bilangan bulat. Jadi 3 membagi 99.
Tidak ada komentar:
Posting Komentar