ciri pembahagian euclid

20

Upload: manimeglay-rajandran

Post on 05-Oct-2015

50 views

Category:

Documents


2 download

DESCRIPTION

assignment

TRANSCRIPT

PENGENALAN

Elements oleh Euclid tidak terhad kepada geometri sahaja. Dua buah buku ( II dan IV ) yang hampir-hampir merupakan algebra eksklusif. Tiga buah buku ( VII, VIII dan IX ) merupakan kepada teori nombor. Orang Yunani sentiasa merujuk perkataan nombor kepada apa yang kita katakan nombor tabii, iaitu nombor bulat positif atau integer. Buku VII bermula dengan senarai dua puluh dua takrif yang membezakan pelbagai jenis nombor ganjil dan genap, perdana dan gubahan, satah dan padu ( iaitu nombor yang menjadi hasil darab bagi dua atau tiga integer) akhir sekali mentakrif nombor sempurna sebagai nombor yang bersamaan dengan bahagianya sendiri. Buku VII bermula dengan dua usulan yang merangkumi petua dalam teori nombor, yang hari ini dikenal sebagai algoritma Euclid untuk mencari pembahagi sepunya terbesar (ukuran) dua nombor. Ia adalah satu skema yang menyarankan penggunaan songsang berulang aksiom Eudoxus. Bilangan teori nombor ialah kajian undang-undang, khususnya sifat cawangan integer matematik. Ia adalah nombor satu cawangan yang paling purba. Ia matematik sebagai kaedah penyelidikan utama, kandungan utama adalah integer yang dibahagikan dengan teori, teori kesesuaian, teori pecahan berterusan dan persamaan tertentu yang tidak dapat ditentukan khas. Dalam erti kata lain, teori nombor adalah dengan menggunakan kaedah asas, mudah untuk mengkaji teori nombor. Teori nombor ialah satu cabang dalam matematik tulen yang membincangkan sifat-sifat nombor secara am, dan integer secara khusus, serta kesemua masalah dari kelas yang lebih luas yang muncul dari pengkajiannya.Istilah aritmetik atau "aritmetik tinggi" sebagai kata nama pernah digunakan untuk merujuk kepada teori nombor asas. Pada zaman moden, istilah ini tidak digunakan. Bagaimanapun perkataan "aritmetik" masih lagi popular digunakan sebagai adjektif. Contohnya untuk istilah geometri aritmetik dan fungsi aritmetik.Teori nombor boleh dibahagikan kepada beberapa bidang, berdasarkan kaedah yang digunakan dan jenis persoalan yang dikaji.

PENGENALAN TENTANG EUCLIDEuclid adalah seorang ahli matematik yang masyhur. Sumbangan besar Euclid adalah karya berjodol Elements of Geometry. Karya tersebut tidak terhad pada geometri sahaja. Tiga buah buku di dalam karya tersebut (iaitu VII, VIII DAN IX) mengandungi sejumlah 102 usulan tentang ciri dan sifat nombor asli. Usulan-usulan itu membentuk teori nombor euclid yang masih digunakan. Sifat tahan lama The Elements membuat Euclid menjadi guru matematik terkemuka sepanjang zaman. Namun sedikit yang diketahui tentang kehidupan Euclid kecuali beliau mengajar di Alexandria di Mesir.Maklumat lain juga diberikan tentang Euclid yang diberikan oleh penulis tertentu tetapi ia tidak dianggap boleh dipercayai. Dua jenis maklumat tambahan ini wujud. Jenis pertama maklumat tambahan yang diberikan oleh penulis Arab yang menyatakan bahawa Euclid adalah anak Naucrates dan bahawa dia dilahirkan di Tirus. Adalah dipercayai oleh ahli sejarah matematik bahawa ini adalah sepenuhnya rekaan semata-mata dan telah dicipta oleh penulis. Jenis kedua ialah maklumat Euclid dilahirkan di Megara. Ini adalah kerana kesilapan di pihak penulis yang pertama memberi maklumat ini. Malah terdapat Euclid dari Megara, yang merupakan seorang ahli falsafah yang hidup kira-kira 100 tahun sebelum Euclid dari Alexandria matematik. Ia tidak cukup kebetulan bahawa ia mungkin kelihatan seolah-olah terdapat dua ulama yang dikenali sebagai Euclid. Malah Euclid adalah nama yang sangat biasa di seluruh tempoh ini dan ini adalah salah satu komplikasi lagi yang menjadikan ia sukar untuk mencari maklumat tentang Euclid dari Alexandria kerana terdapat banyak rujukan kepada lelaki yang dipanggil Euclid dalam kesusasteraan tempoh ini.

CIRI PEMBAHAGIAN EUCLID bermaksud bahagi yang, adalahmultiple dari . Satu integer adalah perdana kalau dan hanya pembahagi positif dari n adalah 1 dan n. Nombor perdana adalah penting dalam nombor teori danaplikasinya. Division algoritma mengatakan bahawa satu integer boleh dibahagi dengan satu lagi (bukan sifar) integer, dengan quotient yang unik danbaki.

CONTOH INTUITIFKatakan pai yang mempunyai 9 keping dan mereka akan dibahagikan sama rata di kalangan 4 orang. Menggunakan bahagian Euclid, 9 dibahagikan dengan 4 adalah 2 dan selebihnya 1. Dalam erti kata lain, setiap orang menerima 2 keping pai, dan terdapat 1 keping ditinggalkan. Ini boleh disahkan menggunakan pendaraban, songsang bahagian: jika setiap satu daripada 4 orang menerima 2 keping, maka 4 2 = 8 keping telah diberikan dalam semua. Menambah 1 keping baki, hasilnya adalah 9 keping. Ringkasnya: 9 = 4 2 + 1. Secara umum, jika bilangan keping ditandakan dan bilangan orang yang adalah , seseorang boleh membahagikan pai sama rata di kalangan rakyat supaya setiap orang menerima keping (darjah) dan beberapa beberapa keping dibiarkan lebih (bakinya). Tidak kira, persamaan memegang. Jika 9 keping dibahagikan di kalangan 3 orang bukan 4, setiap akan menerima 3 keping dan tidak akan ditinggalkan. Dalam kes ini selebihnya adalah sifar, dan ia berkata, 3 sama rata membahagikan 9. Bahagian Euclid juga boleh diperluaskan kepada integer negatif menggunakan formula yang sama; contohnya 9 = 4 (3) + 3, jadi 9 dibahagikan dengan 4 adalah 3 bakinya 3. Selebihnya adalah hanya satu daripada empat nombor yang tidak boleh negatif.

Pai mempunyai 9 keping, jadi setiap satu daripada 4 orang menerima 2 keping dan 1 adalah yang ditinggalkan.

TEOREM Diberi dua integerdan , wujud integer unik dan sehinggakan dan , di mana Menandakan nilai mutlak. Empat integer yang muncul dalam teoram ini telah diberikan nama: a dipanggil dividen dipanggil pembahagi, dipanggil kecerdasan dan dipanggil bakinya. Pengiraan quotient dan selebihnya dari dividen dan pembahagi dipanggil bahagian atau dalam kes ini kekaburan, bahagian Euclidan. Teoram sering dirujuk sebagai algoritma bahagian ini, walaupun ia adalah teoram dan tidak algoritma, keran bukti sebagai diberi di bawah juga menyediakan algoritma pembahagian mudah untuk pengkomputeraan dan . Bahagian tidak ditakrifkan dalam hal jika b0; melihat bahagian dengan sifar.

CONTOHJika a 9 dan b 4, maka q 2 dan r 1, sejak 9 4 2 + 1.Jika a 9 dan b 4, maka q 2 dan r 1, sejak 7 4 (2) + 1. Jika a 9 dan b 4, maka q = 3 dan r = 3, kerana 9 = 4 (3) + 3 Jika a 9 dan b 4, maka q = 3 dan r = 3, kerana 9 = 4 3 + 3.

BUKTIBuktinya terdiri daripada dua bahagian pertama, bukti kewujudan q dan r, dan kedua, bukti keunikan q dan r.

LEMAPembahagian Euclids lema adalah kenyataan terbukti yang digunakan untuk membuktikan kenyataan lain. Pembahagian integer positif dengan nombor bulat positif katakan 20 bahagi 3. 6 3 20 18 2 Di sini, 3 adalah pembahagi, 20 adalah dividen, 6 adalah quotient dan 2 adalah bakinya. Kita boleh menulis keputusan dalam bentuk berikut Dividen pembahagiquotient baki 20 3 6 + 2; 0 2 6Bagi setiap pasangan integer positif dan, kita boleh mencari integer unik dan memuaskan hubungan Malah, ini berlaku untuk setiap pasangan integer positif sebagai terbukti dalam lema berikut. Bahagian Euclids lema: Jika dan sebarang dua integer positif. Kemudian ada wujud integer yang unik dan seperti yang Jika, maka. Jika tidak, memuaskan ketidaksamaan yang lebih kukuh

Bukti: Pertimbangkan janjang aritmetik berikut. , a 3b, a 2b, a b, a, a + b, a + 2b, a + 3b,

Jelas sekali, ia adalah satu janjang aritmetik dengan perbezaan biasadan ia meliputi tak terhingga dalam kedua-dua arah. Jika menjadi istilah yang paling kecil dan bukan negatif bagi janjang aritmetik kemudian wujudlah satu integer bukan negatif seperti itu, Seperti, r adalah integer terkecil bukan negatif memuaskan hasil di atas. Oleh itu,

Oleh itu, kita mempunyai

Sekarang kita hendaklah membuktikan bahawa dan Kita ada,

sekarang

Oleh itu, perwakilan adalah unik

CONTOH BAHAGIAN LEMA EUCLID 1) Tunjukkan bahawa 1 boleh dibahagi dengan 8, jika n ialah integer positif ganjil. penyelesaian:Kita tahu bahawa mana-mana integer positif ganjil adalah 4q + 1 atau 4q + 3 untuk beberapa integer q.Jadi, kita ada hal yang berikut: Kes I Apabila n= 4q + 1Dalam kes ini, kita mempunyai 1 1 = 16 + 8q + 1 1= 16 + 8q = 8q ( 2q + 1) 1 boleh dibahagi dengan 8 [ sejak 8q ( 2q + 1) boleh dibahagi dengan 8]

Kes II Apabila n = 4q + 3 Dalam kes ini, kita mempunyai1 = (4q + 3)2 1 = 16 + 24q + 9 1 = 16 + 24q + 8 1 = 8(2 + 3 q + 1) 1 adalah dibahagi dengan 8 [ sejak 8(2 + 3 q + 1) boleh dibahagi dengan 8] Oleh itu, - 1 boleh dibahagi dengan 8.

ALGORITMA EUCLID

Apa Euclid yang panggil "langkah biasa" dipanggil pada masa kini faktor umum atau pembahagi biasa dan kemudian menawarkan satu algoritma untuk mencari pembahagi terbesar biasa (GCD) dua integer. Tidak menghairankan, algoritma menanggung nama Euclid. Algoritma Euclidean, juga dikenali sebagai algoritma Euclid, adalah satu algoritma untuk mencari pembahagi sepunya terbesar bagi dua nombor dan Algoritma ini adalah berdasarkan kepada kedua-dua pemerhatian berikut: Jika kemudian . Ini memang begitu kerana tidak ada nombor (b, khususnya) boleh mempunyai pembahagi yang lebih besar daripada bilangan itu sendiri dan integer dan bukanya negatif. Jika , bagi integerdan , maka gcd (a, b) = gcd (b, r). Sesungguhnya, setiap pembahagi sepunya dan juga membahagikan . Oleh itu gcd (a, b) membahagikan . Tetapi, sudah tentu, gcd (a, b) | b. Oleh itu, gcd (a, b) adalah pembahagi biasa b dan r dan dengan itu gcd(a, b) gcd(b, r). Sebaliknya juga benar kerana setiap pembahagi dan juga membahagikan.

CONTOH sedangkan a = 2322, b = 654. 2322 = 6543 + 360 gcd(2322, 654) = gcd(654, 360) 654 = 3601 + 294 gcd(654, 360) = gcd(360, 294) 360 = 2941 + 66 gcd(360, 294) = gcd(294, 66) 294 = 664 + 30 gcd(294, 66) = gcd(66, 30) 66 = 302 + 6 gcd(66, 30) = gcd(30, 6) 30 = 65 gcd(30, 6) = 6Maka , gcd(2322,654) = 6.

TEOREMSedangakan z. AndaikanSelepas itu, wujudnya integer z seperti yangBUKTISaranan ini menegaskan d boleh dinyatakan sebagai gabungan linear (dengan pekali integer) m dan n. Membuktikan hasilnya dengan bekerja ke belakang dari akhir algoritma, menunjukkan berturut-turut d yang linear yang gabungan dan sebagainya, kerana adalah gabungan linear dan , d juga gabungan linear dan .Untuk memulakan dengan,Dari garis sebelumnya dalam algoritma Dengan ituTetapi sekarang, dari garis sebelumnyaDengan itu, Oleh itu, Berterusan dengan cara ini, andaikan kita telah menunjukkan bahawa

Sejak Ia mengikut bahawa Oleh ituDengan Akhirnya, di atas algoritma ,Iaitu daripada bentuk yang dikhendaki

LEMADalam teori nombor, lema Euclid (juga dikenali sebagai teorem pertama Euclid) adalah lema yang menangkap sebuahciri asas nombor perdana, iaitu: Jika perdana membahagikan produk dua nombor, ia mesti membahagikan sekurang-kurangnya salah satu daripada nombor-nombor tersebut. Contohnya sejak 133 143 = 19019 boleh dibahagikan dengan 19, satu atau kedua-dua daripada 133 atau 143 mestilah juga. Malah, 19 7 = 133. Lema ini tidak benar untuk nombor komposit. Sebagai contoh, 4 tidak membahagikan 6 dan 4 tidak membahagikan 10, namun 4 tidak membahagikan produk mereka, 60.

TEORAM ARETMETIK ASASDalam teori nombor, Teorem Asas Aritmetik (atau unik Perdana teorem pemfaktoran) menyatakan bahawa mana-mana integer lebih besar daripada 1 boleh ditulis sebagai produk yang unik (sehingga pesanan satu faktor) nombor perdana. Intuitif, teorem ini mencirikan nombor perdana unik dalam erti kata bahawa mereka adalah "nombor asas. Nombor komposit merupakan nomborintegerbukan negatif yang memilikipembahagipositif selain satu atau nombor itu sendiri. Dalam kata lain, jikaadalah integer dan terdapat integer sehinggakandengan itunmerupakan komposit.LEMA 3.1Nombor perdana adalah pemfaktoran daripada nombor komposit positif jika .BuktiKatakan adalah pemfaktoran . Oleh itu, dalam pembahagian algoritma kita mempunyai where dan . Mengikut definisi ini mengatakan .Katakan kemudian . Jika adalah perdana, kemudian kita ada pemfaktoran . Kalau adalah nombor komposit, kemudian dapat dinyatakan hasil darapan perdana: dan lagi kita mempunyai pemfaktoran yang mempunyai .LEMA 3.2Andaikan integer positif mempunyai pemfaktoran unik. Nombor perdana berbeza , muncul dalam pemfaktoran ini jika CONTOHAndaikan 180 adalah pemfaktoran unik. Nombor perdana 2, 3, 5 adalah pembahagi 180. Oleh itu, 2, 3, 5 muncul dalam pemfaktoran 180. Sebenarnya, kita boleh tulis 180 .Andaikan 28 adalah pemfaktoran unik 28 . Jadi, 2 | 28 dan 7 | 28.

TEOREMPemfaktoran integer positif adalah unik kecuali mungkin untuk ordering faktor.BUKTIKatakan N menjadi komposit: ini difaktorkan dalam hasil pendarapan nombor perdana sekurang-kurangnya satu cara. Katakan S N menjadi set komposit integer positif yang mana difaktorkan dalam perdana dengan lebih daripada satu cara. Andaikan S adalah nonempty. Menurut Well-Odering Property S mengandungi ahli terkecil . di mana , adalah perdana. tidak boleh menjadi dan sebaliknya. Sebagai contohnya, jika , oleh itu dari lema 3.1 kedua-dua pemfaktoran of akan dibahagi oleh , meninggalkan sebagai dua pemfaktoran daripada elemen baru dalam S yang kecil daripada . Ini adalah percanggahan.Sekarang mengatur dua pemfaktoran of supaya adalah yang paling kecil daripada masing-masing. Selepas itu, dan pendarapan kedua-dua belah oleh memberi Sama, kita mendapat dan kombinasi dengan ketidaksamaan yang lalu memberikan , atau secara menyebabkan .CONTOHPemfaktoran 12 adalah Oleh itu, pembahagi 12 adalah ahli dalam setnya {1, },enam bilangan. Nombor enam ini berhubung dengan initim dengan eksponen (2 dan 1) dalam pemfaktoran 12.

NOMBOR PERDANA YANG TAK TERHINGGA

Takrif nombor perdana yang tak terhingga ditunjukkan dengan menggunakan kajian contradiction. Bukti standart kerana sekiranya P merupakan nombor perdana dan bilangan ditakrifkan sebagai 1 dan darab semua nombor perdana yang kurang daripada atau sama dengan P.Teoram nombor perdana yang tak terhingga muncul sebagai Proposition 20 dalam Book IX of the Elements of Euclid ini menunjukkan kemustahilan Sieve of Eratossthenes sebagai alat untuk menyenaraikan semua nombor perdana.TEOREMBilangan nombor perdana adalah nombor tak terhinggaBUKTIAndaikan, yang berlawanan, bahawa set S adalah nombor perdana yang terhad; katakan P menjadi maksimum dalam S. Dari nombor N, mentakrif sebagaiN 2di mana hasil pendarapan termasuk semua nombor perdana dari 2 sampai P. Dengan jelas, NP, dan jika N bukan nombor komposit, maka kita telah menemui nombor perdana baru yang lebih besar daripada P, satu percanggahan.Jika N adalah bukan nombor perdana, maka itu adalah hasil darab nombor perdana.N = Tiada P yang boleh menjadi antara dalam senarai 2, 3, 5,, P kerana pembahagian algoritma menyatakan bahawa setiap ini meninggalkan baki r = 1 apabila mengangap sebagai pembahagi N. Itu mengikut bahawa salah satu mesti melebihi P, sekali lagi satu percanggahan. Ini mengatakan bahawa S adalah tidak terbatas.

CONTOHBayangkan 11 adalah menjadi nombor perdana terbesar. Maka 2 . Sejak , kita boleh mendapati bahawa 2311 tidak boleh dibahagi oleh mana -mana integer ganjil sehingga melalui 47. Oleh itu, 2311 adalah nombor perdana dan melebihi 11.

RUJUKANA. RUJUKAN DARI BUKU Joseph B. Dence & Thomas P. Dence.(1999). Elements of the theory of numbers. USA : Academic Press.

B. RUJUKAN DARI LAMAN SESAWANG Euclid of Alexandria (Januari 1999) dari http://www-history.mcs.st-and.ac.uk/Biographies/Euclid.html The Fundamental Theorem of Arithmetic dari http://www.maths.tcd.ie/pub/coursework/374/Primality.pdf