Teori nombor kecil. Teori nombor: teori dan amalan

Teori nombor atau aritmetik yang lebih tinggi ialah cabang matematik yang mengkaji integer dan objek yang serupa.

Teori nombor berkaitan dengan kajian sifat-sifat integer. Pada masa ini, teori nombor merangkumi pelbagai isu yang lebih luas yang melangkaui kajian nombor asli.

Dalam teori nombor, bukan sahaja nombor asli dipertimbangkan, tetapi juga set semua integer, set nombor rasional, set nombor algebra. Teori nombor moden dicirikan oleh penggunaan sangat pelbagai kaedah penyelidikan. Dalam teori nombor moden, kaedah digunakan secara meluas analisis matematik.

Teori moden nombor boleh dipecahkan kepada bahagian berikut:

1) Teori nombor asas. Bahagian ini merangkumi soalan teori nombor, iaitu pembangunan secara langsung teori pembahagian dan soalan tentang kebolehwakilan nombor dalam bentuk tertentu. Masalah yang lebih umum ialah masalah menyelesaikan sistem persamaan Diophantine, iaitu persamaan di mana nilai yang tidak diketahui mestilah integer.

2) Teori algebra nombor. Bahagian ini merangkumi soalan yang berkaitan dengan kajian pelbagai kelas nombor algebra.

3) Anggaran diophantine. Bahagian ini merangkumi soalan yang berkaitan dengan kajian penghampiran nombor nyata pecahan rasional. Berkait rapat dengan bulatan idea yang sama, penghampiran Diophantine berkait rapat dengan kajian sifat aritmetik pelbagai kelas nombor.

4) Teori analisis nombor. Bahagian ini termasuk soalan-soalan teori nombor, untuk kajian yang perlu menggunakan kaedah analisis matematik.

Konsep asas:

1) Kebolehbahagiaan adalah salah satu konsep asas aritmetik dan teori nombor yang dikaitkan dengan operasi bahagi. Dari sudut pandangan teori set, kebolehbahagi integer ialah hubungan yang ditakrifkan pada set integer.

Jika bagi sesetengah integer a dan integer b terdapat integer q sehingga bq = a, maka kita katakan bahawa nombor a boleh dibahagi dengan b atau b membahagi a. Dalam kes ini, nombor b dipanggil pembahagi nombor a, dividen a akan menjadi gandaan nombor b, dan nombor q dipanggil hasil bagi a dibahagikan dengan b.

2) Nombor mudah? ialah nombor asli yang mempunyai dua yang berbeza pembahagi semula jadi: unit dan diri sendiri. Semua nombor lain kecuali satu dipanggil nombor komposit.

3) Nombor sempurna? (Yunani kuno ἀριθμὸς τέλειος) - nombor asli, sama dengan jumlah semua pembahaginya sendiri (iaitu semua pembahagi positif, berbeza dengan dirinya sendiri? nombor).

Nombor sempurna pertama ialah 6 (1 + 2 + 3 = 6), seterusnya ialah 28 (1 + 2 + 4 + 7 + 14 = 28). Apabila bilangan asli bertambah, nombor yang sempurna semakin kurang biasa.

4) Pembahagi sepunya terbesar (GCD) untuk dua integer m dan n ialah pembahagi sepunya terbesar. Contoh: untuk nombor 70 dan 105 yang terbesar pembahagi biasa sama dengan 35.

Pembahagi sepunya terbesar wujud dan ditentukan secara unik jika sekurang-kurangnya satu daripada nombor m atau n bukan sifar.

5) Gandaan sepunya terkecil (LCM) bagi dua integer m dan n ialah nombor asli terkecil yang boleh dibahagi dengan m dan n.

6) Nombor m dan n dipanggil coprime jika mereka tidak mempunyai pembahagi sepunya selain daripada satu. Untuk nombor tersebut GCD(m,n) = 1. Sebaliknya, jika GCD(m,n) = 1, maka nombor tersebut adalah koprime.

7) Algoritma Euclidean - algoritma untuk mencari pembahagi sepunya terbesar bagi dua integer atau ukuran sepunya terbesar bagi dua kuantiti homogen.

Anda juga boleh mendapatkan maklumat yang anda minati dalam enjin carian saintifik Otvety.Online. Gunakan borang carian:

Lebih lanjut mengenai topik No. 17. Konsep asas teori nombor:

Teori nombor ialah cabang matematik yang mengkaji sifat-sifat nombor.

Objek utama teori nombor ialah nombor asli (lihat Nombor). Harta utama mereka, yang dianggap oleh teori nombor, adalah kebolehbahagi. Julat pertama masalah dalam teori nombor ialah pemfaktoran nombor. "Blok bangunan" utama dalam penguraian ini ialah nombor perdana, i.e. nombor hanya boleh dibahagikan dengan 1 dan sendiri; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - ini adalah sepuluh yang pertama nombor perdana(nombor 1 tidak dianggap perdana). Teorem yang mengagumkan, dipanggil teorem asas aritmetik, menyatakan: setiap nombor asli boleh diuraikan menjadi faktor utama, dan satu-satunya cara(sehingga susunan lokasi mereka). Dengan memfaktorkan dua nombor menjadi faktor perdana, adalah mudah untuk menentukan sama ada satu daripadanya boleh dibahagikan dengan yang lain atau tidak. Tetapi masih sukar untuk mengetahui sama ada ini bilangan yang besar mudah, iaitu sama ada ia boleh dibahagi dengan sebarang nombor selain daripada dirinya dan satu.

Siri yang dikaitkan dengan pemfaktoran nombor menjadi faktor perdana ialah fungsi aritmetik. Mari kita tunjukkan sebahagian daripada mereka. φ(n) - Fungsi Euler - bilangan nombor dari 1 hingga n yang bersamaan dengan nombor n (iaitu tidak berkongsi dengan n faktor biasa, kecuali satu); α(n) ialah bilangan pembahagi nombor n, t(n) ialah hasil tambah semua pembahagi nombor n, π(n) ialah fungsi Chebyshev - bilangan nombor perdana tidak melebihi n. Fungsi ini menyatakan banyak sifat nombor asli. Teorem Euclid menyatakan bahawa terdapat banyak nombor perdana yang tidak terhingga. Ini bermakna π(n)→∞ apabila nombor n bertambah. Adalah mungkin untuk mengetahui seberapa cepat fungsi π(n) cenderung kepada infiniti. Ternyata ia lebih kurang sama dengan fungsinya

Teorem ini dipanggil hukum asimptotik taburan nombor perdana. Ia telah dirumuskan dan sebahagian besarnya dibuktikan oleh P. L. Chebyshev (1849), dan terbukti sepenuhnya hanya 50 tahun kemudian.

Hukum taburan nombor perdana asimptotik adalah hasil daripada teori nombor analitik, yang secara meluas menggunakan kaedah analisis matematik untuk mengkaji fungsi teori nombor. Ditemui pada separuh kedua abad ke-19. fakta perkaitan antara objek diskret seperti integer dan sifat dalam fungsi mempunyai pengaruh yang besar terhadap perkembangan teori nombor.

Pemfaktoran nombor hanya mengambil kira struktur set nombor asli yang dikaitkan dengan pendaraban, terdalam dan tugas yang sukar teori nombor timbul daripada perbandingan penambahan dan pendaraban. Masalah sedemikian termasuk, sebagai contoh, masalah Goldbach - adakah mungkin untuk melakukan apa-apa? nombor genap mewakilinya sebagai hasil tambah dua nombor perdana; teorem yang hebat Fermat (lihat teorem terakhir Fermat) - adakah mungkin kuasa ke- mewakili nombor sebagai jumlah n kuasa mana-mana dua nombor, dsb.

Teori nombor menarik kerana ia mengandungi banyak rumusan mudah, tetapi sukar dan tugasan yang menarik. Banyak masalah ini, diselesaikan dan tidak diselesaikan, telah terkumpul, dan teori nombor sering kelihatan seperti koleksi teka-teki elegan yang berbeza. Walau bagaimanapun, ini tidak benar. Teori nombor telah mencipta kaedah sendiri yang menarik, dan kebanyakannya telah dibangunkan secara aktif dalam beberapa dekad kebelakangan ini, yang telah menyuntik arus hidup baru ke dalam ini. bahagian kuno matematik.

Kaedah klasik teori nombor ialah kaedah perbandingan. Dengan mengenal pasti nombor yang memberikan baki yang sama apabila dibahagikan dengan nombor yang dipilih, selalunya mungkin untuk mewujudkan kemustahilan sebarang hubungan. Sebagai contoh, mempertimbangkan baki pembahagian dengan 3 (atau, seperti yang mereka katakan, modulo 3), adalah mudah untuk membuktikan ketakbolehpecahan persamaan 3x 2 + 4y 2 = 5z 2 dalam nombor asli.

Kaedah analisis terdiri, seperti yang telah kita katakan, dalam fakta bahawa, bermula dari nombor, mereka membina fungsi yang dikaji dengan kaedah analisis matematik. Ya, Soviet ahli akademik saintis I.M. Vinogradov membuktikan versi masalah Goldbach - kebolehwakilan nombor ganjil yang cukup besar sebagai jumlah tiga nombor perdana.

Kami menggambarkan kaedah geometri teori nombor menggunakan teorem terakhir Fermat sebagai contoh. Dalam teorem ini kita bercakap tentang pada kebolehlarutan persamaan x n + y n = z n dalam integer. Membahagikan kedua-dua belah persamaan dengan z n dan menggantikan x/z dengan m dan y/z dengan v, kita memperoleh persamaan u n + v n = 1. Persamaan ini mentakrifkan lengkung tertentu pada satah dengan koordinat (u, v). Penyelesaian kepada persamaan asal dalam integer sepadan dengan penyelesaian kepada persamaan baharu dalam nombor rasional. Setiap penyelesaian tersebut (u, v) boleh disebut sebagai titik dengan koordinat rasional pada satah ini. Sekarang kita boleh cuba memohon kaedah geometri ke lengkung u n + v n = 1 untuk mengkaji set titik dengan koordinat rasional di atasnya.

Sebilangan besar teori nombor, berurusan dengan mencari penyelesaian kepada persamaan dalam integer dan nombor rasional, dipanggil teori persamaan Diophantine, dinamakan sempena saintis Yunani purba Diophantus (abad ke-3).

Salah satu masalah yang sangat lama dan terkenal dalam teori nombor ialah masalah mewakili nombor dengan jumlah kuasa dua. Kami menyenaraikan beberapa keputusan yang diperoleh:

setiap integer boleh diwakili sebagai hasil tambah empat kuasa dua integer (contohnya: 7 = 2 2 + 1 2 + 1 2 + 1 2);

setiap nombor perdana bagi bentuk 4n + 1 boleh diwakili sebagai hasil tambah dua kuasa dua integer (contohnya: 5 = 2 2 + 1 2, 41 = 4 2 + 5 2, dsb.), tetapi bukan satu integer ( bukan hanya perdana) bilangan bentuk 4n + 3 tidak boleh diwakili dalam bentuk ini;

Setiap nombor perdana, kecuali nombor dalam bentuk 8n - 1, boleh diwakili sebagai hasil tambah tiga kuasa dua integer.

Identiti algebra mudah

(a 2 + b 2) (x 2 + y 2) = (ax + by) 2 + (ay - bx) 2

membolehkan kita membuat kesimpulan: jika dua nombor boleh diwakili sebagai hasil tambah dua kuasa dua, maka hasil darabnya juga boleh diwakili sebagai hasil tambah dua kuasa dua. Kaedah algebra V kebelakangan ini digunakan secara meluas dalam teori nombor. Ini difasilitasi oleh pembangunan konsep algebra umum seperti medan, yang rupanya sebahagian besarnya dirangsang oleh masalah dalam teori nombor.

Mengapakah teori nombor begitu berharga? Lagipun, sukar untuk mencari aplikasi langsung keputusannya. Namun begitu, masalah teori nombor telah menarik minat golongan muda dan saintis yang ingin tahu selama berabad-abad. Apa masalah di sini? Pertama sekali, masalah ini, seperti yang telah disebutkan, sangat menarik dan cantik. Pada setiap masa, orang telah kagum itu soalan mudah Sukar untuk mencari jawapan tentang nombor. Pencarian untuk jawapan ini sering membawa kepada penemuan yang kepentingannya jauh melebihi skop teori nombor. Cukuplah untuk menyebut apa yang dipanggil teori cita-cita ahli matematik Jerman abad XIX E. Kummer, yang dilahirkan berkaitan dengan percubaan untuk membuktikan teorem terakhir Fermat.

nama: Teori nombor. 2008.

Buku teks adalah berdasarkan keputusan teori asas nombor, dibentuk dalam karya klasik - Fermat, Euler, Gauss dan lain-lain Isu seperti nombor perdana dan komposit, fungsi aritmetik, teori perbandingan, punca dan indeks primitif, pecahan berterusan, nombor algebra dan transendental dipertimbangkan. Sifat nombor perdana, teori persamaan Diophantine, aspek algoritma teori nombor dengan aplikasi dalam kriptografi (menguji nombor perdana yang besar untuk primaliti, pemfaktoran bilangan yang besar kepada faktor, logaritma diskret) dan menggunakan komputer.
Bagi pelajar institusi pengajian tinggi.

Subjek kajian teori nombor ialah nombor dan sifatnya, iaitu nombor muncul di sini bukan sebagai cara atau instrumen, tetapi sebagai objek kajian. Siri semula jadi
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- set nombor asli - adalah bidang penyelidikan yang paling penting, sangat bermaklumat, penting dan menarik.
Kajian nombor asli bermula pada tahun Yunani Purba. Euclid dan Eratosthenes menemui sifat kebolehbahagi nombor, membuktikan ketakterhinggaan set nombor perdana dan mencari cara untuk membinanya. Masalah yang berkaitan dengan penyelesaian persamaan tak tentu dalam nombor bulat, adalah subjek penyelidikan oleh Diophantus, serta saintis India Purba dan China Purba, negara Asia Tengah.

Jadual kandungan
pengenalan
Bab 1. Mengenai pembahagian nombor
1.1. Sifat Bahagi bagi Integer
1.2. Gandaan sepunya terkecil dan pembahagi sepunya terbesar
1.3. Algoritma Euclid
1.4. Penyelesaian integer persamaan linear

Bab 2. Nombor perdana dan komposit
2.1. Nombor perdana. Penapis Eratosthenes. Ketakterhinggaan set nombor perdana
2.2. Teorem Asas Aritmetik
2.3. Teorem Chebyshev
2.4. Riemann Zeta Fungsi dan Sifat Nombor Perdana
Masalah untuk diselesaikan secara bebas
Bab 3. Fungsi Aritmetik
3.1. Fungsi pendaraban dan sifatnya
3.2. Fungsi Möbius dan formula penyongsangan
3.3. Fungsi Euler
3.4. Jumlah pembahagi dan bilangan pembahagi nombor asli
3.5. Anggaran nilai min bagi fungsi aritmetik
Masalah untuk diselesaikan secara bebas
Bab 4: Perbandingan Berangka
4.1. Perbandingan dan sifat asasnya
4.2. Kelas potongan. Cincin kelas sisa untuk modul tertentu
4.3. Sistem potongan yang lengkap dan dikurangkan
4.4. Teorem Wilson
4.5. Teorem Euler dan Fermat
4.6. Perwakilan nombor rasional sebagai tak terhingga perpuluhan
4.7. Menguji keperibadian dan membina nombor perdana yang besar
4.8. Pemfaktoran integer dan aplikasi kriptografi
Masalah untuk diselesaikan secara bebas
Bab 5. Perbandingan dengan yang tidak diketahui
5.1.Takrifan asas
5.2 Perbandingan ijazah pertama
5.3.Teorem baki bahasa Cina
5.4. Perbandingan polinomial oleh modul mudah
5.5. Perbandingan polinomial oleh modul kompositMasalah untuk penyelesaian bebas
Bab 6. Perbandingan darjah kedua
6.1. Perbandingan modulo perdana darjah kedua
6.2. Simbol Legendre dan sifatnya
6.3. Undang-undang timbal balik kuadratik
6.4.Simbol Jacobi dan sifat-sifatnya
6.5. Jumlah petak dua dan empat
6.6. Perwakilan sifar bentuk kuadratik daripada tiga pembolehubah
Masalah untuk diselesaikan secara bebas
Bab 7. Akar dan indeks antiterbitan
7.1. Penunjuk nombor untuk modul yang diberikan
7.2. Kewujudan akar primitif modulo prima
7.3. Pembinaan akar primitif menggunakan modul pk dan 2pk
7.4. Teorem tentang ketiadaan akar primitif dalam moduli selain daripada 2, 4, pk dan 2pk
7.5. Indeks dan sifatnya
7.6. Logaritma diskret
7.7. Perbandingan binomial
Masalah untuk diselesaikan secara bebas
Bab 8. Pecahan Bersambung
8.1. Teorem Dirichlet tentang penghampiran nombor nyata dengan nombor rasional
8.2. Pecahan berterusan terhingga
8.3. Pecahan berterusan nombor sebenar
8.4. Anggaran Terbaik
8.5. Nombor yang setara
8.6. Ketidakrasionalan kuadratik dan pecahan berterusan
8.7. Menggunakan pecahan berterusan untuk menyelesaikan beberapa persamaan Diophantine
8.8 Penguraian nombor e kepada pecahan bersambung
Masalah untuk diselesaikan secara bebas
Bab 9. Nombor algebra dan transendental
9.1.Bidang nombor algebra
9.2. Penghampiran nombor algebra mengikut nombor rasional. Kewujudan nombor transendental
9.3. Ketidakrasionalan nombor er dan n
9.4. Transendensi nombor e
9.5. Transendensi nombor n
9.6. Kemustahilan mengkuadratkan bulatan
Masalah untuk diselesaikan secara bebas
Jawapan dan arahan
Rujukan

Muat turun percuma e-buku dalam format yang mudah, tonton dan baca:
Muat turun buku Teori Nombor - Nesterenko Yu.V. - fileskachat.com, muat turun pantas dan percuma.

Muat turun djvu
Di bawah ini anda boleh membeli buku ini pada harga terbaik dengan diskaun dengan penghantaran ke seluruh Rusia.

Teori nombor1

1. Konsep asas teori pembahagian

Î DEFINISI Nombor a boleh dibahagi dengan nombor b bukan sifar jika terdapat integer c supaya kesamaan a = b · c dipegang.

Jawatan:

1) a .b a dibahagikan dengan b ;

2) b | a b membahagikan a;

3) a ialah gandaan (berbilang) b , b pembahagi a .

Bahagian dengan baki

Biarkan dua nombor a èb ,a Z ,b N diberikan, biarkan Z ialah set integer, dan N ialah set nombor asli. íàb boleh bahagi dengan baki a =b · q +r , ãäår terletak pada selang 0≤ r< b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Teorem 1. Bagi sebarang integer a dan nombor asli b, perwakilan

a = b q+ r,0 ≤ r< b

sahaja.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Kewujudan.

Mari kita pertimbangkan set tak terhingga nombor (a − tb) , ãäåa ,b nombor tetap, t sebarang nombor, t Z . Daripadanya kita akan memilih nombor bukan negatif terkecil r =a − q · b. Mari kita buktikan bahawa r terletak di dalam

0 ≤ r< b.

Biarkan nombor ini bukan milik selang ini. Maka ia lebih besar daripada atau sama dengan b. Mari bina nombor baharu r ′ =r−b =a−q·b−b =a−b (q +1).

Daripada ini kita dapat melihat perkara berikut:

1) r ′ (a − tb);

2) r ' bukan negatif;

1 S.V. Fedorenko. September 2012. Kursus kuliah dan tugasan. Diedarkan secara bebas. Kursus ini diajar di Universiti Pentadbiran Penerbangan Negeri St. Petersburg (1997 1999; 2008 2011) dan Universiti Pedagogi Negeri St. Petersburg (2002 2005).

3) r ′< r .

Oleh itu, tidak r , a r ' ialah yang terkecil nombor bukan negatif daripada set (a − tb) , maka andaian r ≥ b adalah palsu.

Kewujudan telah terbukti.

2. Keunikan.

Biar ada perwakilan lain a =bq ′ +r′ , dengan syarat 0≤r′< b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Memindahkan syaratñq dalam satu arah, dan сr dalam arah yang lain, kita memperoleh b (q − q ′ ) =r ′ − r . nampaknya

÷òî (r ′ − r ) .b . Setiap baki adalah kurang daripada b и

(r′ − r) . b. |r′ − r|< b

Akibatnya, r ′ − r = 0, yang bermaksud r ′ =r èq =q ′ . Jadi, kami telah buktikan

bahawa satu nombor boleh dibahagikan dengan yang lain dalam satu cara sahaja. Teorem telah terbukti.

Teorem 2. Jika a .b èb .c , tòa .c , ãäåb, c ≠ 0.

a = b · q. b=c t

Oleh itu, a =c · qt. Mengikut definisi adalah jelas bahawa a .c .

Teorem 3. Biarkan kesamaan a 1 +a 2 =b 1 +b 2 dan nombor a 1, a 2, b 1 .d dipuaskan, kemudian b 2 .d.

Ä î ê à ç à ò å ë ü ñ ò â î

a 1 =d · t 1 ,a 2 =d · t 2 ,b 1 =d · t 3 . Mari kita ungkapkan b 2 daripada keadaan teorem b 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ). Dengan takrifan kebolehbahagiaan adalah jelas bahawa b 2 .d .

2. Pembahagi sepunya terbesar

Î definisi c ialah pembahagi nombor a èb , maka nombor c dipanggil pembahagi sepunya bagi nombor a èb .

Definisi. Pembahagi sepunya terbesar bagi nombor a èb dipanggil pembahagi sepunya terbesar (GCD) bagi nombor a èb.

Notasi: (a, b) =d, ãäåa èb nombor, iklan ialah yang paling biasa

pembahagi nombor ini.

Mari kita lihat contoh untuk nombor 12 dan 9. Mari kita tulis semua pembahagi 12 dan semua pembahagi 9. Untuk 12: 1, 2, 3, 4, 6 dan 12; untuk 9: 1, 3 dan 9; adalah jelas bahawa mereka mempunyai pembahagi sepunya 1 dan 3. Mari kita pilih yang terbesar daripada mereka ialah 3. Oleh itu, (12, 9) = 3.

Takrifan Dua nombor a dan b dipanggil coprime jika gcdnya sama dengan 1.

Contoh. Kerana (10,9)=1, maka 10 dan 9 ialah nombor perdana secara relatif.

Takrifan ini boleh diperluaskan kepada sebarang bilangan nombor. Jika (a, b, c, . . . ) = 1, maka nombor a, b, c, . . . saling sederhana. Contohnya:

Î ï ð å ä ë å í è å. (a 1 , a 2 , ...a n ) ialah nombor koprima berpasangan jika gcd mana-mana pasangan sama dengan satu(a i , a j ) = 1,i ≠ j .

Contohnya: 12,17,11 bukan sahaja relatif perdana, tetapi juga koprime berpasangan.

Teorem 1. Jika a .b , maka (a, b ) =b .

Ä î ê à ç à ò å ë ü ñ ò â î

Nombor b tidak boleh dibahagikan dengan nombor yang lebih besar daripada dirinya. Oleh itu, b ialah GCD bagi èb .

Teorem 2. Biarkan terdapat perwakilan a =bq +r (r tidak semestinya baki), maka (a, b) = (b, r).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Pertimbangkan mana-mana pembahagi biasa a èb c . Åñëa .c èb .c , tî

oleh Teorem 1.3 r .c , t.å.c juga merupakan pembahagi biasa bagi b èr . Mana-mana pembahagi biasa a èb ialah pembahagi biasa b èr.

2. Mana-mana pembahagi sepunya b èr ialah pembahagi a. Ini bermakna pembahagi biasa a, b èb, r bertepatan. Ini juga berlaku untuk GCD.

3. Algoritma Euclid

Untuk sebarang nombor èb menggunakan algoritma Euclidean seseorang boleh mencari

Biarkan a,b N ialah data input bagi algoritma, dan (a, b) =d N ialah output.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R 2 q 2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n+1	r n−1 = r nq n

Langkah 1. Bahagikan íàb dengan baki a =bq 0 +r 1 , ãäå 0< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Langkah 2. Bahagikan b íàr 1 dengan baki b =r 1 q 1 +r 2 , ãäå 0< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

Begitulah seterusnya sehingga terbahagi sepenuhnya. Daripada rantaian persamaan

(a, b) = (b, r 1) = (r 1, r 2) = (r 2, r 3) =... = (r n− 2, r n− 1) = (r n− 1, r n) =r n

ia berikutan bahawa baki bukan sifar terakhir r n akan menjadi yang paling biasa pembahagi =r n = (a, b ). Kerana baki berkurangan, maka algoritma akan selesai dalam nombor akhir langkah.

Teorem yang berkaitan dengan algoritma Euclidean

Teorem 1. Gcd bagi dua nombor boleh dibahagi dengan mana-mana pembahagi sepunya bagi ini

Åñëè (a, b ) =d , òî (a c , c b ) =d c , ãäå c pembahagi sepunya a èb .

Ä î ê à ç à ò å ë ü ñ ò â î

Â entri algoritma Euclidean a, b и âñår saya akan bahagikan kita. Kami dapat

rakaman algoritma Euclidean dengan data input a b

nama a		c èc . Daripadanya jelas
nama a
	è c	sama c.

Teorem 2. Jika dua nombor dibahagikan dengan gcdnya, kita memperoleh nombor perdana secara relatif (a d, d b) = 1.

Ä î ê à ç à ò å ë ü ñ ò â î

Teorem 3. Jika

Daripada c (dari Teorem 1) kita gantikan d.

(a, b) = 1, tòîc .b .ac . b

Ä î ê à ç à ò å ë ü ñ ò â î

Untuk nombor relatif perdana a èb, menurut Teorem 7.1, terdapat perwakilan ax +by = 1. Mendarab kesamaan ini dengan c, kita mempunyai ac ·x +byc =c,

íî ac =bq ,bqx +byc =c ,b (qx +yc ) =c . Oleh itu, c .b .

GCD beberapa nombor

(a1 , a2 , . . . , an ) = dn (a1 , a2 ) = d2

(d 2 , a 3 ) = d 3

(d n− 1 , a n ) =d n

4. Gandaan sepunya terkecil

Î DEFINISI: Gandaan sepunya bagi dua nombor a èb ialah nombor yang boleh dibahagi dengan kedua-dua nombor ini a èb.

Î DEFINISI: Gandaan sepunya terkecilèb dipanggil gandaan sepunya terkecil (LCM) bagi èb.

Biarkan M .a èM .b , maka M ialah gandaan sepunya bagi suatu èb . Kami menandakan gandaan sepunya terkecil bagi suatu èb sebagai .

Teorem 1. LCM bagi dua nombor sama dengan nisbah karya mereka ke

=(a, ab b) .

Ä î ê à ç à ò å ë ü ñ ò â î

Mari kita nyatakan beberapa gandaan sepunya bagi nombor a èb dengan M, kemudian M.

a èM .b . Selain itu,d = (a, b),a =a ′ d,b =b ′ d, dan (a ′, b ′) = 1. Mengikut takrif kebolehbahagiM =a · k, ãäåk Z




					a′ dk				a′ k
					b′ d				b′

a ′ tidak boleh dibahagikan dengan b ′ , kerana mereka secara relatifnya prima, oleh itu k .b ′ daripada Teorem 3.3

k = b′ t=




M = a · k=
					(a, b)

bentuk mana-mana gandaan sepunya èb. Ïðèt = 1M ialah LCM bagi nombor a èb .

LCM beberapa nombor

[a1, a2, . . . , an ] = Mn [ a1 , a2 ] = M2

M 3 = M 4

Åñëè (a, b) = 1, tòî =ab. Pr (a i , a j ) = 1,i ≠ j ,M =a 1 a 2 · . . . · a n .

5. Nombor perdana dan komposit

Sebarang nombor boleh dibahagi dengan 1 dan nombor itu sendiri. Kita panggil pembahagi ini remeh.

Definisi: Nombor dipanggil perdana jika ia tidak mempunyai pembahagi bukan remeh. Nombor dipanggil komposit jika ia mempunyai pembahagi bukan remeh. Nombor 1 bukan perdana mahupun komposit.

Teorem 1. Bagi sebarang nombor asli a dan nombor perdana p

berpuas hati atau (a, p ) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

Nombor perdana p mempunyai dua pembahagi remeh. mungkin

dua pilihan: a .p èëèa ̸ .p . Åñëèa ̸ .p , maka GCD bagi èp ialah 1. Oleh itu, (a, p ) = 1.

Teorem 2. Pembahagi terkecil bagi integer berbeza daripada satu, lebih besar daripada satu, ialah nombor perdana.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , ãäåp ialah pembahagi bukan remeh terkecil. Mari kita andaikan bahawa p ialah nombor komposit. Ini bermakna ada

nombor sedemikian s , ÷òîp .s , tetapi kemudian a .s èp bukan kurangnya pembahagi, yang bercanggah dengan syarat tersebut. T.o.p ialah nombor perdana.

Teorem 3. Pembahagi bukan remeh terkecil nombor komposit tidak melebihi akarnya.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q b, q ≤ b, q2 ≤ bq= a, q ≤ a.

Penapis Eratosthenes

Mari kita tuliskan set nombor asli

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

Unit ialah nombor khas. Kami meneruskan dengan nombor yang tinggal seperti berikut: ambil nombor, isytiharkan nombor perdana dan potong gandaannya.

Sebagai contoh, 2 ialah nombor perdana, kita memotong nombor yang merupakan gandaan dua, oleh itu, tidak akan ada nombor genap yang tinggal. Mari kita lakukan perkara yang sama dengan ketiga-tiganya. Anda perlu memotong 6, 9, 12, 15, 18, dsb. Semua nombor yang tinggal adalah perdana.

Teorem 4. Set nombor perdana adalah tak terhingga. Bukti

Biarkan ( 2, 3, 5, . . . , P) menjadi set terhingga nombor perdana dan N = 2· 3· 5·. . .·P +1.N tidak boleh dibahagikan dengan mana-mana nombor perdana, kerana apabila dibahagikan, bakinya ialah 1. Tetapi pembahagi bukan remeh terkecil N mengikut Teorem 2 ialah nombor perdana 2(, 3, 5, . . . , P). Akibatnya, bilangan nombor perdana bukanlah set terhingga, tetapi satu set tak terhingga.

6. Bentuk kanonik nombor

Teorem 1 (Teorem Asas Aritmetik). Sebarang nombor selain daripada 1 hanya boleh diwakili sebagai hasil darab nombor perdana.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Kewujudan.

Nombor n, mengikut Teorem 5.2, mempunyai pembahagi utama p 1

n n 1 = p 1 .

Penaakulan yang sama adalah sah untuk nombor n 1

n2 = n 1 ,p 2

ãäå p 2 pembahagi utama n 1. Jadi kita akan teruskan sehingga kita mendapat n i = 1.

2. Keunikan.

Biarkan nombor n mempunyai dua penguraian nombor perdana

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.

Tanpa kehilangan keluasan, kami menerima l ≤ s. Jika sebelah kiri kesamaan boleh dibahagi dengan 1, maka yang betul juga boleh dibahagi dengan 1. Ini bermakna beberapa q i =p 1 . Biarkan ia q 1 =p 1 . Bahagikan kedua-dua belah kesamaan dengan 1

Begitu juga mari kita terima q 2 = p 2 . Kami akan meneruskan prosedur ini sehingga ungkapan mengambil bentuk

1 = ql +1 · . . . · qs.

Åñëè l< s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åsëè s =l , tòp i =q i äëÿi dan kedua-dua pengembangan bertepatan. Teorem telah terbukti.

Sebarang nombor n N boleh ditulis dalam bentuk kanonik

n = p1 s 1 · . . . · pl s l ,

L p i ialah nombor perdana, s i N .

Perwakilan kanonik membolehkan anda menulis semua pembahagi nombor dan menentukan GCD dan LCM.

Semua pembahagi c nombor n mempunyai bentuk

c = p1 i 1 · p2 i 2 . . . pl i l ,ãäå ij .

Mencari GCD dan LCM

Biarkan nombor a dan b diwakili dalam bentuk

a = p1 s 1 · p2 s 2 · . . . · pl s l b= p1 t 1 · p2 t 2 · . . . · pl t l .

Perwakilan ini berbeza daripada perwakilan kanonik kerana beberapa s i и t i boleh sama dengan 0.

Kemudian pembahagi sepunya terbesar a èb

(a, b) = p1 min (s 1 ,t 1 ) · p2 min (s 2 ,t 2 ) · . . . · pl min (s l ,t l ),

dan gandaan sepunya terkecil ialah:

[ a, b] = p1 maks (s 1 ,t 1 ) · p2 max (s 2 ,t 2 ) · . . . · pl maks (s l ,t l ) .

Dari sini juga jelas bahawa (a, b) boleh dibahagikan dengan mana-mana pembahagi sepunya a èb.

7. Persamaan Diophantine Linear dengan dua yang tidak diketahui

Î D e finisi Persamaan Diophantine linear dengan dua yang tidak diketahui ialah persamaan bentuk

ax + by= c,

di mana pekali a, b, c dan x, y yang tidak diketahui ialah integer, aa dan b tidak sama dengan sifar pada masa yang sama.

Teorem 1 (Mengenai perwakilan linear GCD). Untuk mana-mana pasangan nombor (a, b) ((a, b) ≠ (0, 0)) terdapat x, y Z, ÷òîax +by =(a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

Pertimbangkan set nombor (ax + by) dan pilih minimum daripadanya nombor positif d =ax 0 +oleh 0 .

Mari kita buktikan bahawa d ialah pembahagi bagi b.

Biarkan d tidak menjadi pembahagi, oleh itu, b =d q +r, ãäå 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). Adalah jelas bahawa:

1) nombor r (ax +by) ;

2) r adalah positif;

3) r< d .

Tetapi kami mengandaikan bahawa d ialah nombor positif terkecil daripada set ini, maka andaian kami bahawa r< d неверно, значитd делительb .

Begitu juga, kita boleh membuktikan bahawa a .d .

Daripada semua ini, ia mengikuti bahawa d ialah pembahagi biasa bagi èb.

a. (a, b)

Kostak, b. (a, b) d. (a, b), íîd ialah pembahagi biasa bagi èb, oleh itu, d ÍÎÄ a è b.

Teorem 2. Persamaan ax +by =c mempunyai penyelesaian jika dan hanya ifc boleh dibahagi dengan (a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

1. biarlahc. (a, b), kemudian dengan Teorem 1 kapak+oleh= (a, b). Mari kita darabkan persamaan dengan c

( a,b )

a (a,xcb) + b (a,ycb) = c.

Sepasang nombor ( x0 , y0 ) akan menjadi penyelesaian kepada persamaan asal

{ x0 = (a,bxc)y0 = (a,byc).

2. Mari kita buktikan bahawa jika persamaan mempunyai penyelesaian, maka c. (a, b).

a. (a, b) , oleh itu, c mesti juga boleh dibahagikan dengan ( a, b).

b . ( a, b )