Nombor sebanding modulo 7. Perbandingan modulo nombor asli

Perbandingan dengan yang tidak diketahui x nampak macam

mana . Jika a n tidak boleh dibahagikan dengan m, itulah yang dinamakan ijazah perbandingan.

Dengan keputusan perbandingan ialah sebarang integer x 0 , untuk yang mana

Jika X 0 memenuhi perbandingan, maka, mengikut sifat 9 perbandingan, semua integer yang dibandingkan dengan x 0 modulo m. Oleh itu, semua penyelesaian perbandingan kepunyaan modulo kelas sisa yang sama T, kami akan menganggapnya sebagai satu penyelesaian. Oleh itu, perbandingan mempunyai banyak penyelesaian kerana terdapat unsur-unsur sistem lengkap sisa yang memenuhinya.

Perbandingan yang set penyelesaiannya bertepatan dipanggil setara.

2.2.1 Perbandingan ijazah pertama

Perbandingan ijazah pertama dengan yang tidak diketahui X nampak macam

(2.2)

Teorem 2.4. Untuk perbandingan mempunyai sekurang-kurangnya satu penyelesaian, adalah perlu dan mencukupi bahawa bilangan b dibahagikan dengan GCD( a, m).

Bukti. Mula-mula kita buktikan keperluan. biarlah d = GCD( a, m) Dan X 0 - penyelesaian perbandingan. Kemudian , iaitu perbezaannya Oh 0 − b dibahagikan dengan T. Jadi terdapat integer sedemikian q, apa Oh 0 − b = qm. Dari sini b= ah 0 − qm. Dan sejak d, sebagai pembahagi biasa, membahagi nombor A Dan T, maka minuend dan subtrahend dibahagikan dengan d, dan oleh itu b dibahagikan dengan d.

Sekarang mari kita buktikan kecukupan. biarlah d- pembahagi sepunya terbesar bagi nombor A Dan T, Dan b dibahagikan dengan d. Kemudian, mengikut takrif kebolehbahagi, wujud integer berikut a 1 , b 1 ,T 1 , apa .

Menggunakan algoritma Euclidean lanjutan, kita dapati perwakilan linear nombor 1 = gcd( a 1 , m 1 ):

bagi sesetengah orang x 0 , y 0 . Mari kita darabkan kedua-dua belah kesamaan terakhir dengan b 1 d:

atau, apa yang sama,

iaitu, dan merupakan penyelesaian kepada perbandingan. □

Contoh 2.10. Perbandingan 9 X= 6 (mod 12) mempunyai penyelesaian kerana gcd(9, 12) = 3 dan 6 boleh dibahagi dengan 3. □

Contoh 2.11. Perbandingan 6x= 9 (mod 12) tidak mempunyai penyelesaian, kerana gcd(6, 12) = 6, dan 9 tidak boleh dibahagikan dengan 6. □

Teorem 2.5. Biarkan perbandingan (2.2) boleh diselesaikan dan d = GCD( a, m). Kemudian set penyelesaian perbandingan (2.2) terdiri daripada d kelas residu modulo T, iaitu jika X 0 - salah satu daripada penyelesaian, maka semua penyelesaian lain adalah

Bukti. biarlah X 0 - penyelesaian perbandingan (2.2), iaitu Dan , . Jadi ada perkara sedemikian q, Apa Oh 0 − b = qm. Sekarang menggantikan ke dalam persamaan terakhir dan bukannya X 0 penyelesaian bentuk yang sewenang-wenangnya, di mana, kita memperoleh ungkapan

, boleh dibahagikan dengan m. □

Contoh 2.12. Perbandingan 9 X=6 (mod 12) mempunyai tepat tiga penyelesaian, kerana gcd(9, 12)=3. Penyelesaian ini: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Contoh 2.13. Perbandingan 11 X=2 (mod 15) mempunyai penyelesaian yang unik X 0 = 7, kerana GCD(11,15)=1.□

Kami akan menunjukkan kepada anda cara menyelesaikan perbandingan ijazah pertama. Tanpa kehilangan sifat umum, kami akan menganggap bahawa GCD( a, t) = 1. Kemudian penyelesaian untuk perbandingan (2.2) boleh dicari, contohnya, menggunakan algoritma Euclidean. Sememangnya, menggunakan algoritma Euclidean lanjutan, kami mewakili nombor 1 sebagai gabungan nombor linear a Dan T:

Mari kita darabkan kedua-dua belah kesamaan ini dengan b, kita dapat: b = abq + mrb, di mana abq - b = - mrb, iaitu a ∙ (bq) = b(mod m) Dan bq- penyelesaian perbandingan (2.2).

Penyelesaian lain ialah menggunakan teorem Euler. Sekali lagi kami percaya bahawa GCD(a, T)= 1. Kami menggunakan teorem Euler: . Darab kedua-dua belah perbandingan dengan b: . Menulis semula ungkapan terakhir sebagai , kami memperoleh bahawa adalah penyelesaian kepada perbandingan (2.2).

Biarkan sekarang GCD( a, m) = d>1. Kemudian a = atd, m = mtd, di mana GCD( A 1 , m 1) = 1. Di samping itu, ia adalah perlu b = b 1 d, supaya perbandingan dapat diselesaikan. Jika X 0 - penyelesaian perbandingan A 1 x = b 1 (mod m 1), dan satu-satunya, sejak GCD( A 1 , m 1) = 1, maka X 0 akan menjadi penyelesaian dan perbandingan A 1 xd = db 1 (mod m 1), iaitu perbandingan asal (2.2). Rehat d- 1 penyelesaian ditemui oleh Teorem 2.5.

Projek matematik pada topik

"Modul perbandingan"

Zaripova Aisylu

Daerah Sovetsky di Kazan

MBOU "Sekolah Menengah No. 166", gred 7a

Penyelia saintifik: Antonova N.A.

Jadual kandungan

Pengenalan________________________________________________________________3

Apakah perbandingan________________________________________________4

Mengaplikasikan perbandingan dalam penyelesaian masalah______________________________6

Penggunaan perbandingan modulo yang paling mudah ialah untuk menentukan kebolehbahagi nombor__________________________6
Satu tugas perbandingan________________________________8
Penggunaan perbandingan modulo dalam aktiviti profesional________________________________________________9

Kesimpulan_________________________________________________10

Senarai sastera terpakai________________________________________________11

pengenalan.

Topik: Perbandingan modulo.

Masalah: Ramai pelajar menghadapi masalah semasa membuat persediaan untuk Olimpik, penyelesaiannya adalah berdasarkan pengetahuan baki daripada membahagi integer dengan nombor asli. Kami berminat dengan jenis masalah ini dan kaedah yang mungkin untuk menyelesaikannya. Ternyata mereka boleh diselesaikan menggunakan perbandingan modulo.

Matlamat: Mengetahui intipati perbandingan modulo, kaedah utama bekerja dengan perbandingan modulo.

Objektif: cari bahan teori mengenai topik ini, pertimbangkan masalah yang diselesaikan menggunakan perbandingan modulo, tunjukkan kaedah yang paling biasa untuk menyelesaikan masalah tersebut, buat kesimpulan.

Objek kajian: teori nombor.

Subjek penyelidikan: teori perbandingan modulo.

Kerja ini berkaitan dengan penyelidikan teori dan boleh digunakan sebagai persediaan untuk Olimpik matematik. Kandungannya mendedahkan konsep asas perbandingan modulo dan sifat utamanya, dan menyediakan contoh penyelesaian masalah mengenai topik ini.

saya . Apakah perbandingan?

Nombor-nombor itu dan dikatakan sebanding dalam modulus jika ia boleh dibahagi dengan, dengan kata lain, a dan b mempunyai baki yang sama apabila dibahagikan dengan.

Jawatan

Contoh:

12 dan 32 adalah modulo 5 yang setanding, kerana 12 apabila dibahagikan dengan 5 mempunyai baki 2 dan 32 apabila dibahagikan dengan 2 mempunyai baki 2. Ia ditulis12 ;

101 dan 17 adalah setanding modulo 21;

Teori pembahagian sebahagian besarnya dicipta oleh Euler. Definisi perbandingan telah dirumuskan dalam buku oleh K.F Gauss "Kajian Aritmetik". Karya ini, yang ditulis dalam bahasa Latin, mula dicetak pada tahun 1797, tetapi buku itu diterbitkan hanya pada tahun 1801 kerana fakta bahawa proses percetakan pada masa itu adalah sangat intensif buruh dan panjang. Bahagian pertama buku Gauss dipanggil: "Pada perbandingan nombor." Ia adalah Gauss yang mencadangkan simbolisme perbandingan modulo yang telah menjadi mantap dalam matematik.

Jika

Bukti:

Jika kita menambah kedua kepada kesamaan pertama, kita dapat

ialah hasil tambah dua integer, oleh itu ia adalah integer, oleh itu.

Jika kita menolak yang kedua daripada kesamaan pertama, kita dapat

ini ialah perbezaan dua integer, yang bermaksud ia adalah integer, oleh itu.

Pertimbangkan ungkapan:

Ini ialah perbezaan hasil darab integer, yang bermaksud ia adalah integer, oleh itu.

Ini adalah akibat daripada sifat perbandingan ketiga.

Q.E.D.

5) Jika.

Bukti: Mari cari jumlah kedua-dua ungkapan ini:

ialah hasil tambah dua integer, oleh itu ia adalah integer, oleh itu .

Q.E.D.

6) Jika ialah integer, maka

Bukti: , di manahlm– integer, darab kesamaan ini dengan, kita dapat: . Oleh kerana adalah hasil darab integer, itulah yang perlu dibuktikan.

7) Jika

Bukti: alasannya sama dengan pembuktian harta 6.

8) Jika - nombor koprima, kemudian

Bukti: , bahagikan ungkapan ini dengan, kita dapat: - nombor koprima, yang bermaksud ia boleh dibahagi dengan integer, i.e. =. Dan ini bermakna bahawa apa yang perlu dibuktikan.

II . Mengaplikasikan perbandingan untuk menyelesaikan masalah.

2.1. Penggunaan perbandingan modulo yang paling mudah adalah untuk menentukan kebolehbahagi nombor.

Contoh. Cari baki 2 2009 pukul 7.

Penyelesaian: Pertimbangkan kuasa 2:

menaikkan perbandingan kepada kuasa 668 dan mendarab dengan, kita mendapat: .

Jawapan: 4.

Contoh. Buktikan bahawa 7+7 2 +7 3 +…+7 4 n boleh dibahagi dengan 100 untuk mana-manandaripada satu set integer.

Penyelesaian: Pertimbangkan perbandingan

dll. Sifat kitaran baki dijelaskan oleh peraturan untuk mendarab nombor dalam lajur. Menambah empat perbandingan pertama, kami mendapat:

Ini bermakna jumlah ini dibahagikan dengan 100 tanpa baki. Begitu juga, menambah perbandingan berikut kira-kira empat, kita mendapat bahawa setiap jumlah tersebut boleh dibahagikan dengan 100 tanpa baki. Ini bermakna keseluruhan jumlah yang terdiri daripada 4nsebutan boleh dibahagi dengan 100 tanpa baki. Q.E.D.

Contoh. Tentukan pada nilai apanungkapan itu boleh dibahagi dengan 19 tanpa baki.

Penyelesaian: .

Mari kita darabkan perbandingan ini dengan 20. Kita dapat.

Mari kita tambah perbandingan, kemudian. . Oleh itu, bahagian kanan perbandingan sentiasa boleh dibahagikan dengan 19 untuk sebarang nombor aslin, yang bermaksud ungkapan asal boleh dibahagikan dengan 19 dengan semula jadin.

Jawab n – sebarang nombor asli.

Contoh. Apakah digit yang berakhir dengan nombor itu?

Penyelesaian. Untuk menyelesaikan masalah ini, kami hanya akan memantau digit terakhir. Pertimbangkan kuasa nombor 14:

Anda boleh perhatikan bahawa jika eksponen adalah ganjil, nilai darjah berakhir dengan 4, dan jika eksponen adalah genap, ia berakhir dengan 6. Kemudian ia berakhir dengan 6, i.e. ialah nombor genap. Jadi ia akan berakhir dalam 6.

Jawapan 6.

2.2. Satu tugas perbandingan.

Artikel oleh N. Vilenkin "Perbandingan dan kelas sisa" membentangkan masalah yang telah diselesaikan oleh ahli fizik Inggeris terkenal Dirac semasa tahun-tahun pelajarnya.

Terdapat juga penyelesaian ringkas untuk masalah ini menggunakan perbandingan modulo. Tetapi kami menghadapi beberapa masalah yang sama. Contohnya.

Seorang pejalan kaki menjumpai longgokan epal berhampiran sebatang pokok di mana seekor monyet sedang duduk. Selepas mengira mereka, dia menyedari bahawa jika 1 epal diberikan kepada monyet, maka bilangan epal yang tinggal akan dibahagikan kepada n tanpa jejak. Setelah memberikan epal tambahan itu kepada monyet, dia mengambil 1/ n baki epal dan kiri. Kemudian, orang yang lalu lalang seterusnya menghampiri longgokan, kemudian yang seterusnya, dsb. Setiap orang yang lalu lalang, setelah mengira epal, menyedari bahawa bilangan mereka apabila dibahagikan dengan n memberikan baki 1 dan, setelah memberikan epal tambahan kepada monyet, dia mengambil 1/ n baki epal dan teruskan. Selepas yang terakhir pergi, n ke lalu, bilangan epal yang tinggal dalam longgokan dibahagikan dengan n tanpa jejak. Berapakah bilangan epal dalam longgokan pada mulanya?

Menjalankan penaakulan yang sama seperti Dirac, kami memperoleh formula umum untuk menyelesaikan kelas masalah yang serupa: , di manan– nombor asli.

2.3. Aplikasi perbandingan modul dalam aktiviti profesional.

Teori perbandingan digunakan pada teori pengekodan, jadi semua orang yang memilih profesion yang berkaitan dengan komputer akan belajar, dan mungkin menggunakan perbandingan dalam aktiviti profesional mereka. Sebagai contoh, beberapa konsep teori nombor, termasuk perbandingan modulo, digunakan untuk membangunkan algoritma penyulitan kunci awam.

Kesimpulan.

Kerja ini menggariskan konsep asas dan sifat perbandingan modulo dan menggambarkan penggunaan perbandingan modulo dengan contoh. Bahan tersebut boleh digunakan sebagai persediaan menghadapi olimpiade dalam matematik dan Peperiksaan Negeri Bersepadu.

Senarai rujukan yang diberikan membolehkan, jika perlu, untuk mempertimbangkan beberapa aspek yang lebih kompleks dari teori perbandingan modulo dan aplikasinya.

Senarai sastera terpakai.

Alfutova N.B. Algebra dan teori nombor./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 hlm.

Bukhshtab A.A. Teori nombor. /A.A.Bukhshtab. M.: Pendidikan, 1960.

Vilenkin N. Perbandingan dan kelas sisa./N. – 1978.- 10.

Fedorova N.E. Kajian algebra dan analisis matematik. darjah 10.http:// www. prosv. ru/ ebook/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedia. org/ wiki/Modul_perbandingan.

Definisi 1. Jika dua nombor ialah 1) a Dan b apabila dibahagikan dengan hlm berikan baki yang sama r, maka nombor tersebut dipanggil equiremainder atau setanding dalam modulus hlm.

Kenyataan 1. biarlah hlm beberapa nombor positif. Kemudian setiap nombor a sentiasa dan, lebih-lebih lagi, dalam satu-satunya cara boleh diwakili dalam bentuk

Tetapi nombor ini boleh diperolehi dengan menetapkan r sama dengan 0, 1, 2,..., hlm−1. Oleh itu sp+r=a akan mendapat semua nilai integer yang mungkin.

Mari kita tunjukkan bahawa perwakilan ini unik. Mari kita anggap itu hlm boleh diwakili dalam dua cara a=sp+r Dan a=s 1 hlm+r 1. Kemudian

(2)

Kerana r 1 menerima salah satu nombor 0,1, ..., hlm−1, kemudian nilai mutlak r 1 −r kurang hlm. Tetapi daripada (2) ia mengikutinya r 1 −r berbilang hlm. Oleh itu r 1 =r Dan s 1 =s.

Nombor r dipanggil tolak nombor a modulo hlm(dengan kata lain, nombor r dipanggil baki nombor a pada hlm).

Kenyataan 2. Jika dua nombor a Dan b setanding dalam modulus hlm, Itu a−b dibahagikan dengan hlm.

sungguh. Jika dua nombor a Dan b setanding dalam modulus hlm, kemudian apabila dibahagikan dengan hlm mempunyai baki yang sama hlm. Kemudian

dibahagikan dengan hlm, kerana sebelah kanan persamaan (3) dibahagikan dengan hlm.

Kenyataan 3. Jika beza dua nombor boleh dibahagi dengan hlm, maka nombor ini boleh dibandingkan dalam modulus hlm.

Bukti. Mari kita nyatakan dengan r Dan r Baki 1 bahagian a Dan b pada hlm. Kemudian

Contoh 25≡39 (mod 7), −18≡14 (mod 4).

Daripada contoh pertama ia mengikuti bahawa 25 apabila dibahagikan dengan 7 memberikan baki yang sama dengan 39. Sesungguhnya, 25 = 3 7 + 4 (baki 4). 39=3·7+4 (baki 4). Apabila mempertimbangkan contoh kedua, anda perlu mengambil kira bahawa baki mestilah nombor bukan negatif kurang daripada modulus (iaitu 4). Kemudian kita boleh menulis: −18=−5·4+2 (baki 2), 14=3·4+2 (baki 2). Oleh itu, -18 apabila dibahagikan dengan 4 meninggalkan baki 2, dan 14 apabila dibahagikan dengan 4 meninggalkan baki 2.

Sifat perbandingan modulo

Harta benda 1. Untuk sesiapa sahaja a Dan hlm Sentiasa

tidak selalu ada perbandingan

di mana λ ialah pembahagi sepunya terbesar bagi nombor m Dan hlm.

Bukti. biarlah λ pembahagi sepunya terbesar bagi nombor m Dan hlm. Kemudian

Kerana m(a−b) dibahagikan dengan k, Itu

Oleh itu

Dan m adalah salah satu pembahagi nombor hlm, Itu

di mana h=pqs.

Ambil perhatian bahawa kami boleh membenarkan perbandingan berdasarkan modul negatif, i.e. perbandingan a≡b mod( hlm) bermakna dalam kes ini bahawa perbezaan a−b dibahagikan dengan hlm. Semua sifat perbandingan kekal berkuat kuasa untuk modul negatif.

Perbandingan ijazah pertama dengan yang tidak diketahui mempunyai bentuk:

f(x) 0 (mod m); f(X) = Oh + dan n. (1)

Selesaikan perbandingan- bermakna mencari semua nilai x yang memuaskannya. Dua perbandingan yang memenuhi nilai x yang sama dipanggil setara.

Jika perbandingan (1) berpuas hati oleh mana-mana x = x 1, kemudian (mengikut 49) semua nombor yang setanding dengan x 1, modulo m: x x 1 (mod m). Keseluruhan kelas nombor ini dianggap sebagai satu penyelesaian. Dengan persetujuan sedemikian, kesimpulan berikut boleh dibuat.

66.C penjajaran (1) akan mempunyai penyelesaian sebanyak bilangan sisa sistem lengkap yang memenuhinya.

Contoh. Perbandingan

6x– 4 0 (mod 8)

Antara nombor 0, 1,2, 3, 4, 5, 6, 7, dua nombor memenuhi sistem lengkap sisa modulo 8: X= 2 dan X= 6. Oleh itu, perbandingan ini mempunyai dua penyelesaian:

x 2 (mod 8), X 6 (mod 8).

Perbandingan darjah pertama dengan memindahkan istilah bebas (dengan tanda bertentangan) ke sebelah kanan boleh dikurangkan kepada bentuk

kapak b(mod m). (2)

Pertimbangkan perbandingan yang memenuhi syarat ( A, m) = 1.

Menurut 66, perbandingan kami mempunyai banyak penyelesaian kerana terdapat sisa sistem lengkap yang memenuhinya. Tetapi apabila x berjalan melalui sistem lengkap sisa modulo T, Itu Oh berjalan melalui sistem lengkap potongan (daripada 60). Oleh itu, untuk satu dan hanya satu nilai X, diambil dari sistem yang lengkap, Oh akan setanding dengan b. Jadi,

67. Apabila (a, m) = 1 kapak perbandingan b(mod m)mempunyai satu penyelesaian.

biarkan sekarang ( a, m) = d> 1. Kemudian, untuk perbandingan (2) untuk mempunyai penyelesaian, adalah perlu (daripada 55) itu b dibahagikan dengan d, jika tidak, perbandingan (2) adalah mustahil untuk sebarang integer x . Andaikan oleh itu b gandaan d, mari letak a = a 1 d, b = b 1 d, m = m 1 d. Kemudian perbandingan (2) akan bersamaan dengan ini (disingkatkan dengan d): a 1 x b 1 (mod m), di mana sudah ( A 1 , m 1) = 1, dan oleh itu ia akan mempunyai satu modulo penyelesaian m 1. biarlah X 1 – sisa bukan negatif terkecil bagi larutan modulo m 1 ini , maka semua nombor ialah x , membentuk larutan ini terdapat dalam bentuk

x x 1 (mod m 1). (3)

Modulo m, nombor (3) membentuk bukan satu penyelesaian, tetapi lebih, sama banyak penyelesaian kerana terdapat nombor (3) dalam siri 0, 1, 2, ..., m – 1 sekurang-kurangnya sisa modulo bukan negatif m. Tetapi nombor berikut (3) akan jatuh di sini:

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

mereka. jumlah d nombor (3); oleh itu perbandingan (2) mempunyai d keputusan.

Kami mendapat teorem:

68. Biarkan (a, m) = d. Perbandingan ax b ( mod m) adalah mustahil jika b tidak boleh dibahagikan dengan d. Apabila b ialah gandaan d, perbandingan itu mempunyai penyelesaian d.

69. Kaedah untuk menyelesaikan perbandingan darjah pertama, berdasarkan teori pecahan berterusan:

Mengembangkan kepada pecahan berterusan hubungan m:a,

dan melihat dua pecahan padanan terakhir:

mengikut sifat pecahan bersambung (mengikut 30 ) kita ada

Jadi perbandingan itu ada penyelesaiannya

untuk mencari, yang cukup untuk mengira Pn– 1 mengikut kaedah yang dinyatakan dalam 30.

Contoh. Mari kita selesaikan perbandingan

111x= 75 (mod 321). (4)

Di sini (111, 321) = 3, dan 75 ialah gandaan bagi 3. Oleh itu, perbandingan mempunyai tiga penyelesaian.

Membahagikan kedua-dua belah perbandingan dan modulus dengan 3, kita mendapat perbandingan

37x= 25 (mod 107), (5)

yang mesti kita selesaikan dahulu. Kami ada

q
P 3

Jadi, dalam kes ini n = 4, P n – 1 = 26, b= 25, dan kami mempunyai penyelesaian untuk perbandingan (5) dalam bentuk

x–26 ∙ 25 99 (mod 107).

Oleh itu penyelesaian kepada perbandingan (4) dibentangkan seperti berikut:

X 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod 321).

Pengiraan unsur songsang oleh modulo tertentu

70.Jika nombor adalah integer a Dan n adalah koprime, maka terdapat nombor a', memuaskan perbandingan a ∙ a′ ≡ 1 (mod n). Nombor a' dipanggil songsangan darab bagi modulo n dan notasi yang digunakan untuknya ialah a- 1 (mod n).

Pengiraan kuantiti timbal balik modulo nilai tertentu boleh dilakukan dengan menyelesaikan perbandingan darjah pertama dengan satu yang tidak diketahui, di mana x nombor diterima a'.

Untuk mencari penyelesaian perbandingan

a∙x≡ 1(mod m),

di mana ( a,m)= 1,

anda boleh menggunakan algoritma Euclid (69) atau teorem Fermat-Euler, yang menyatakan bahawa jika ( a,m) = 1, kemudian

a φ( m) ≡ 1(mod m).

x ≡ a φ( m)–1 (mod m).

Kumpulan dan sifatnya

Kumpulan adalah salah satu kelas taksonomi yang digunakan untuk mengklasifikasikan struktur matematik dengan sifat ciri sepunya. Kumpulan mempunyai dua komponen: ramai (G) Dan operasi() ditakrifkan pada set ini.

Konsep set, unsur dan keahlian adalah konsep asas matematik moden yang tidak ditentukan. Mana-mana set ditakrifkan oleh unsur-unsur yang termasuk di dalamnya (yang, seterusnya, juga boleh menjadi set). Oleh itu, kita mengatakan bahawa set ditakrifkan atau diberikan jika untuk mana-mana elemen kita boleh memberitahu sama ada ia tergolong dalam set ini atau tidak.

Untuk dua set A, B rekod B A, B A, B∩ A, B A, B \ A, A × B masing-masing bermakna itu B ialah subset daripada set A(iaitu sebarang elemen daripada B juga terkandung dalam A, sebagai contoh, set nombor asli terkandung dalam set nombor nyata; selain itu, sentiasa A A), B ialah subset yang betul bagi set A(mereka. B A Dan B ≠ A), persilangan set B Dan A(iaitu semua elemen sedemikian yang terletak serentak dalam A, dan dalam B, sebagai contoh, persilangan integer dan nombor nyata positif ialah set nombor asli), gabungan set B Dan A(iaitu set yang terdiri daripada unsur-unsur yang terletak sama ada dalam A, atau dalam B), tetapkan perbezaan B Dan A(iaitu set elemen yang terletak di B, tetapi jangan berbohong A), hasil cartesan set A Dan B(iaitu set pasangan bentuk ( a, b), Di mana a A, b B). Melalui | A| sentiasa menunjukkan kardinaliti set A, iaitu bilangan elemen dalam set A.

Operasi ialah peraturan yang mengikut mana mana-mana dua elemen set G(a Dan b) dipadankan dengan elemen ketiga dari G: a b.

Banyak elemen G dengan operasi dipanggil kumpulan, jika syarat berikut dipenuhi.

Pada n mereka memberikan baki yang sama.

Rumusan setara: a dan b setanding dalam modulus n jika perbezaan mereka a - b boleh dibahagikan dengan n, atau jika a boleh diwakili sebagai a = b + kn , Di mana k- beberapa integer. Contohnya: 32 dan −10 ialah modulo 7 yang setanding, kerana

Pernyataan "a dan b adalah modulo n yang sebanding" ditulis sebagai:

Sifat kesamaan modulo

Hubungan perbandingan modulo mempunyai sifat

Mana-mana dua integer a Dan b modulo setanding 1.

Dalam rangka untuk nombor a Dan b adalah setanding dalam modulus n, adalah perlu dan mencukupi bahawa perbezaan mereka boleh dibahagikan dengan n.

Jika nombor dan berpasangan setanding dalam modulus n, kemudian jumlah mereka dan , serta produk dan juga boleh dibandingkan dalam modulus n.

Jika nombor a Dan b setanding dalam modulus n, kemudian ijazah mereka a k Dan b k juga boleh dibandingkan dalam modulus n di bawah mana-mana semula jadi k.

Jika nombor a Dan b setanding dalam modulus n, Dan n dibahagikan dengan m, Itu a Dan b setanding dalam modulus m.

Dalam rangka untuk nombor a Dan b adalah setanding dalam modulus n, dibentangkan dalam bentuk penguraian kanoniknya kepada faktor mudah hlm i

perlu dan mencukupi untuk

Hubungan perbandingan ialah hubungan kesetaraan dan mempunyai banyak sifat kesamaan biasa. Sebagai contoh, mereka boleh ditambah dan didarab: jika

Perbandingan, bagaimanapun, tidak boleh, secara amnya, dibahagikan dengan satu sama lain atau dengan nombor lain. Contoh: , bagaimanapun, mengurangkan sebanyak 2, kita mendapat perbandingan yang salah: . Peraturan singkatan untuk perbandingan adalah seperti berikut.

Anda juga tidak boleh melakukan operasi pada perbandingan jika moduli mereka tidak sepadan.

Ciri-ciri lain:

Takrifan berkaitan

Kelas potongan

Set semua nombor yang boleh dibandingkan dengan a modulo n dipanggil kelas potongan a modulo n , dan biasanya dilambangkan [ a] n atau . Oleh itu, perbandingan adalah bersamaan dengan kesamaan kelas sisa [a] n = [b] n .

Sejak perbandingan modulo n ialah hubungan kesetaraan pada set integer, kemudian kelas residu modulo n mewakili kelas kesetaraan; bilangan mereka adalah sama n. Set semua modulo kelas sisa n dilambangkan dengan atau.

Operasi tambah dan darab dengan mendorong operasi sepadan pada set:

[a] n + [b] n = [a + b] n

Berkenaan dengan operasi ini set adalah gelang terhingga, dan jika n mudah - medan terhingga.

Sistem potongan

Sistem sisa membolehkan anda melakukan operasi aritmetik pada set nombor terhingga tanpa melampaui hadnya. Sistem penuh potongan modulo n ialah sebarang set n integer yang tiada tandingan modulo n. Biasanya, sisa bukan negatif terkecil diambil sebagai sistem lengkap modulo n residu

0,1,...,n − 1

atau potongan terkecil mutlak yang terdiri daripada nombor

dalam kes ganjil n dan nombor

dalam kes genap n .

Menyelesaikan perbandingan

Perbandingan ijazah pertama

Dalam teori nombor, kriptografi dan bidang sains lain, masalah mencari penyelesaian kepada perbandingan peringkat pertama bentuk sering timbul:

Menyelesaikan perbandingan sedemikian bermula dengan mengira gcd (a, m)=d. Dalam kes ini, 2 kes adalah mungkin:

Jika b bukan berbilang d, maka perbandingan tidak mempunyai penyelesaian.
Jika b berbilang d, maka perbandingan mempunyai modulo penyelesaian yang unik m / d, atau, apa yang sama, d penyelesaian modulo m. Dalam kes ini, akibat mengurangkan perbandingan asal dengan d perbandingannya ialah:

di mana a 1 = a / d , b 1 = b / d Dan m 1 = m / d ialah integer, dan a 1 dan m 1 adalah agak utama. Oleh itu nombor a 1 boleh terbalik modulo m 1, iaitu, cari nombor sedemikian c, itu (dengan kata lain, ). Sekarang penyelesaiannya didapati dengan mendarabkan perbandingan yang terhasil dengan c:

Pengiraan nilai yang praktikal c boleh dilaksanakan dengan cara yang berbeza: menggunakan teorem Euler, algoritma Euclid, teori pecahan berterusan (lihat algoritma), dsb. Khususnya, teorem Euler membolehkan anda menulis nilai c dalam bentuk:

Contoh

Sebagai perbandingan kami ada d= 2, jadi modulo 22 perbandingan mempunyai dua penyelesaian. Mari kita gantikan 26 dengan 4, setanding dengannya modulo 22, dan kemudian kurangkan semua 3 nombor dengan 2:

Oleh kerana 2 adalah bersamaan dengan modulo 11, kita boleh mengurangkan bahagian kiri dan kanan sebanyak 2. Akibatnya, kita memperoleh satu penyelesaian modulo 11: , bersamaan dengan dua penyelesaian modulo 22: .

Perbandingan darjah kedua

Menyelesaikan perbandingan darjah kedua datang untuk mengetahui sama ada nombor yang diberikan ialah baki kuadratik (menggunakan undang-undang kesalingan kuadratik) dan kemudian mengira modulo punca kuasa dua.

cerita

Teorem baki Cina, yang dikenali selama berabad-abad, menyatakan (dalam bahasa matematik moden) bahawa modul gelang sisa hasil darab beberapa nombor koprima ialah