Miks on vaja mooduleid numbreid võrrelda? Esimese astme võrdluste lahendamine

Matemaatika projekt teemal

"Võrdlusmoodul"

Zaripova Aisylu

Kaasani Sovetski rajoon

MBOU "Keskkool nr 166", 7a klass

Teaduslik juhendaja: Antonova N.A.

Sisukord

Sissejuhatus_________________________________________________________________________3

Mis on võrdlused__________________________________________________4

Võrdluste rakendamine ülesannete lahendamisel___________________________________6

Moodulite võrdluste lihtsaim kasutamine on arvude jaguvuse määramine___________________________6
Üks võrdlusülesanne___________________________________8
Moodulite võrdluste kasutamine kutsetegevuses_____________________________________________________9

Järeldus______________________________________________________________________________________________________________________________________________________________________________________________________________10

Kasutatud kirjanduse loetelu_______________________________________________11

Sissejuhatus.

Teema: Modulo võrdlused.

Probleem: Paljud õpilased seisavad olümpiaadiks valmistumisel silmitsi probleemidega, mille lahendamise aluseks on teadmine jääkide kohta, mis saadakse täisarvude jagamisel naturaalarvuga. Meid huvitasid seda tüüpi probleemid ja nende lahendamise võimalikud meetodid. Selgub, et neid saab lahendada moodulvõrdluste abil.

Eesmärk: Selgitada välja moodulvõrdluste olemus, peamised meetodid moodulivõrdlustega töötamiseks.

Eesmärgid: leida sellel teemal teoreetilist materjali, kaaluda probleeme, mida lahendatakse moodulvõrdluste abil, näidata selliste probleemide lahendamise levinumaid meetodeid, teha järeldusi.

Õppeobjekt: arvuteooria.

Uurimisaine: moodulvõrdluste teooria.

Töö on seotud teoreetilise uurimistööga ja seda saab kasutada matemaatikaolümpiaadideks valmistumisel. Selle sisu paljastab moodulite võrdluse põhimõisted ja nende peamised omadused ning toob näiteid selleteemaliste probleemide lahendamisest.

I . Mis on võrdlused?

Arvud ja peetakse moodulis võrreldavateks, kui need on jagatavad ehk teisisõnu, a ja b jäägid on samad, kui need jagatakse.

Määramine

Näited:

12 ja 32 on võrreldavad mooduliga 5, kuna 12 jagatuna 5-ga on jääk 2 ja 32, kui jagatakse 2-ga, on jääk 2. See on kirjutatud12 ;

101 ja 17 on võrreldavad moodulid 21;

Jaguvuse teooria lõi suures osas Euler. Võrdluse määratluse sõnastas K.F. Gauss “Aritmeetilised uuringud”. Seda ladina keeles kirjutatud teost hakati trükkima 1797. aastal, kuid raamat ilmus alles 1801. aastal, kuna tolleaegne trükiprotsess oli äärmiselt töömahukas ja pikk. Gaussi raamatu esimene osa kannab nime: "Arvude võrdlusest". Just Gauss pakkus välja matemaatikas kinnistunud moodulvõrdluste sümboolika.

Kui

Tõestus:

Kui liidame esimesele võrdsusele teise, saame

on kahe täisarvu summa, seega on see täisarv.

Kui lahutame esimesest võrdsusest teise, saame

see on kahe täisarvu erinevus, mis tähendab, et see on täisarv.

Mõelge väljendile:

See on täisarvude korrutiste erinevus, mis tähendab, et see on täisarv.

See on võrdluste kolmanda omaduse tagajärg.

Q.E.D.

5) Kui.

Tõestus: Leiame nende kahe avaldise summa:

on kahe täisarvu summa, seega on see täisarv, seega .

Q.E.D.

6) Kui on täisarv, siis

Tõestus: , kuslk– täisarv, korrutage see võrdus arvuga, saame: . Kuna see on täisarvude korrutis, tuli seda tõestada.

7) Kui

Tõestus: Põhjendus sarnaneb 6. vara tõendiga.

8) Kui - koaprarvud siis

Tõestus: , jagame selle avaldise arvuga, saame: - koalgarvud, mis tähendab, et need jaguvad täisarvuga, s.t. =. Ja see tähendab, et mida oli vaja tõestada.

II . Võrdluste rakendamine probleemide lahendamisel.

2.1. Moodulite võrdluste lihtsaim kasutamine on arvude jaguvuse määramine.

Näide. Leidke ülejäänud 2 2009 kell 7.

Lahendus: kaaluge 2 võimsusi:

tõstes võrdluse astmeni 668 ja korrutades sellega, saame: .

Vastus: 4.

Näide. Tõesta, et 7+7 2 +7 3 +…+7 4 n mis tahes jaoks jagub 100-gantäisarvude hulgast.

Lahendus: kaaluge võrdlusi

jne. Jääkide tsüklilisus on seletatav arvude korrutamise reeglitega veerus. Kui liita kokku neli esimest võrdlust, saame:

See tähendab, et see summa jagatakse 100-ga ilma jäägita. Samamoodi, lisades järgmised võrdlused umbes nelja kohta, saame, et iga selline summa jagub 100-ga ilma jäägita. See tähendab, et kogu summa, mis koosneb 4-stnterminid jaguvad 100-ga ilma jäägita. Q.E.D.

Näide. Määrake, mis väärtusesnavaldis jagub 19-ga ilma jäägita.

Lahendus:.

Korrutame selle võrdluse 20-ga. Saame.

Liidame siis võrdlused kokku. . Seega jagub võrdluse parem pool mis tahes naturaalarvu puhul alati 19-gan, mis tähendab, et algne avaldis jagub naturaalarvuga 19-gan.

Vastus n – mis tahes naturaalarv.

Näide. Mis numbriga number lõpeb?

Lahendus. Selle probleemi lahendamiseks jälgime ainult viimast numbrit. Mõelge arvu 14 jõududele:

Võite märgata, et kui astendaja on paaritu, lõpeb astme väärtus 4-ga ja kui astendaja on paaris, siis 6. Siis lõpeb see 6-ga, s.t. on paarisarv. Nii et see lõpeb 6.

Vastus 6.

2.2. Üks võrdlusülesanne.

N. Vilenkini artikkel “Jääkide võrdlused ja klassid” esitab probleemi, mille lahendas kuulus inglise füüsik Dirac oma tudengipõlves.

Sellele probleemile on ka lühike lahendus, kasutades moodulvõrdlusi. Kuid puutusime kokku mitmete sarnaste probleemidega. Näiteks.

Üks mööduja leidis puu juurest õunuhunniku, millel istus ahv. Pärast nende lugemist mõistis ta, et kui ahvile antakse 1 õun, jagatakse ülejäänud õunte arv n jäljetult. Andnud ahvile lisaõuna, võttis ta 1/ n ülejäänud õunad ja lahkus. Hiljem lähenes hunnikule järgmine mööduja, siis järgmine jne. Iga järgnev mööduja, olles õunu lugenud, märkas, et nende arv on jagatud n annab ülejäänu 1 ja pärast lisaõuna ahvile andmist võttis ta endale 1 n ülejäänud õunad ja liikus edasi. Pärast viimase lahkumist n mööduja, jagati hunnikusse jäänud õunte arv arvuga n jäljetult. Mitu õuna oli alguses hunnikus?

Läbi samade arutluste nagu Dirac, saime üldvalemi sarnaste ülesannete klassi lahendamiseks: , kusn– naturaalarv.

2.3. Moodulite võrdluste rakendamine kutsetegevuses.

Võrdlusteooriat rakendatakse kodeerimise teooriale, nii et kõik inimesed, kes valivad arvutiga seotud elukutse, õpivad ja võimalusel rakendavad ka võrdlusi oma kutsetegevuses. Näiteks kasutatakse avaliku võtmega krüpteerimisalgoritmide väljatöötamiseks mitmeid arvuteooria kontseptsioone, sealhulgas moodulite võrdlusi.

Järeldus.

Töös tuuakse välja moodulvõrdluse põhimõisted ja omadused ning illustreeritakse näidetega moodulvõrdluse kasutamist. Materjali saab kasutada matemaatikaolümpiaadideks ja ühtseks riigieksamiks valmistumisel.

Antud kirjanduse loetelu võimaldab vajadusel kaaluda mõningaid keerukamaid aspekte moodulvõrdluste teooriast ja selle rakendustest.

Kasutatud kirjanduse loetelu.

Alfutova N.B. Algebra ja arvuteooria./N.B.Alfutova, A.V.Ustinov. M.: MCNMO, 2002, 466 lk.

Bukhshtab A.A. Arvuteooria. /A.A.Bukhshtab. M.: Haridus, 1960.

Vilenkin N. Jääkide võrdlused ja klassid./N Vilenkin.//Kvant. – 1978.- 10.

Fedorova N.E. Algebra ja matemaatilise analüüsi õpe. 10. klass.http:// www. prosv. ru/ e-raamatud/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedia. org/ wiki/Võrdluse_moodul.

Punktis n annavad nad samad jäägid.

Samaväärsed koostised: a ja b mooduli poolest võrreldav n kui nende erinevus a - b jagub n-ga või kui a saab esitada kui a = b + kn , Kus k- mõni täisarv. Näiteks: 32 ja −10 on võrreldavad moodul 7, kuna

Väide “a ja b on võrreldavad mooduli n” on kirjutatud järgmiselt:

Modulo võrdsuse omadused

Mooduli võrdlusrelatsioonil on omadused

Suvalised kaks täisarvu a Ja b võrreldav moodul 1.

Et numbrid a Ja b olid mooduli poolest võrreldavad n, on vajalik ja piisav, et nende erinevus jagub n.

Kui arvud ja on moodulis paarikaupa võrreldavad n, siis nende summad ja , samuti produktid ja on ka moodulis võrreldavad n.

Kui numbrid a Ja b mooduli poolest võrreldav n, siis nende kraadid a k Ja b k on ka mooduli poolest võrreldavad n mis tahes loomuliku all k.

Kui numbrid a Ja b mooduli poolest võrreldav n, Ja n poolt jagatud m, See a Ja b mooduli poolest võrreldav m.

Et numbrid a Ja b olid mooduli poolest võrreldavad n, mis on esitatud selle kanoonilise lagunemise kujul lihtsateks teguriteks lk i

vajalik ja piisav

Võrdlusseos on ekvivalentsuhe ja sellel on palju tavaliste võrdsuste omadusi. Näiteks saab neid liita ja korrutada: kui

Võrdlusi ei saa aga üldiselt jagada üksteise või muude arvudega. Näide: 2 võrra vähendades saame aga eksliku võrdluse: . Võrdluste lühendireeglid on järgmised.

Samuti ei saa te võrdlustega toiminguid teha, kui nende moodulid ei ühti.

Muud omadused:

Seotud määratlused

Mahaarvamise klassid

Kõikide arvude kogum, mis on võrreldav a modulo n helistas mahaarvamise klass a modulo n ja on tavaliselt tähistatud [ a] n või . Seega on võrdlus samaväärne jäägiklasside võrdsusega [a] n = [b] n .

Alates mooduli võrdlusest n on ekvivalentsusseos täisarvude hulgal, siis jääkklassid modulo n esindavad samaväärsuse klasse; nende arv on võrdne n. Kõikide jäägiklasside komplekt modulo n tähistatakse või.

Liitmise ja korrutamise toimingud indutseerivad hulgal vastavaid tehteid:

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

Nende operatsioonide puhul on hulk piiratud ring ja kui n lihtne – lõplik väli.

Mahaarvamise süsteemid

Jääksüsteem võimaldab sooritada aritmeetilisi tehteid piiratud arvude hulgaga, ületamata selle piire. Täielik mahaarvamiste süsteem moodul n on mis tahes hulk n täisarvu, mis on võrreldamatud mooduli n. Tavaliselt võetakse väikseimad mittenegatiivsed jäägid tervikliku jääkide süsteemina mooduli n

0,1,...,n − 1

või absoluutselt väikseimad arvudest koosnevad mahaarvamised

paaritu korral n ja numbrid

paaritu korral n .

Võrdluste lahendamine

Esimese astme võrdlused

Arvuteoorias, krüptograafias ja teistes teadusvaldkondades kerkib sageli vormide esimese astme võrdlustele lahenduste leidmise probleem:

Sellise võrdluse lahendamine algab gcd arvutamisega (a, m)=d. Sel juhul on võimalikud 2 juhtumit:

Kui b mitte mitmik d, siis pole võrdlusel lahendusi.
Kui b mitmekordne d, siis on võrdlusel ainulaadne lahendusmoodul m / d, või mis on sama, d moodullahendused m. Sel juhul esialgse võrdluse vähendamise tulemusena d võrdlus on järgmine:

Kus a 1 = a / d , b 1 = b / d Ja m 1 = m / d on täisarvud ja a 1 ja m 1 on suhteliselt parimad. Seetõttu number a 1 saab modulo ümber pöörata m 1, st leida selline arv c, et (teisisõnu ). Nüüd leitakse lahendus, korrutades saadud võrdluse arvuga c:

Praktiline väärtuse arvutamine c saab realiseerida erineval viisil: kasutades Euleri teoreemi, Eukleidese algoritmi, jätkuvate murdude teooriat (vt algoritm) jne. Eelkõige võimaldab Euleri teoreem väärtuse üles kirjutada c kujul:

Näide

Võrdluseks on meil d= 2, seega moodul 22 on võrdlusel kaks lahendust. Asendame 26 4-ga, mis on võrreldav mooduliga 22, ja seejärel vähendame kõiki 3 arvu 2 võrra:

Kuna 2 on mooduli 11 kaasauk, saame vasakut ja paremat poolt vähendada 2 võrra. Selle tulemusena saame ühe lahendi moodul 11: , mis on võrdne kahe lahendusega moodul 22: .

Teise astme võrdlused

Teise astme võrdluste lahendamine taandub sellele, et välja selgitada, kas antud arv on ruutjääk (kasutades ruutjuure vastastikkuse seadust), ja seejärel ruutjuure mooduli arvutamine.

Lugu

Hiina jäägiteoreem, mis on tuntud juba sajandeid, väidab (tänapäevases matemaatilises keeles), et jääkrõngas mooduli mitme koalgarvu korrutis on

Mõelge vormi võrdlusele x 2 ≡a(mod lkα), kus lk– lihtne paaritu arv. Nagu selgus §4 lõikest 4, saab sellele võrdlusele lahenduse leida võrdluse lahendamisega x 2 ≡a(mod lk). Pealegi võrdlus x 2 ≡a(mod lkα) on kaks lahendit, kui a on ruutjägi moodul lk.

Näide:

Lahenda ruutvõrdlus x 2 ≡86 (mod 125).

125 = 5 3, 5 on algarv. Kontrollime, kas 86 on ruutmoodul 5.

Algses võrdluses on 2 lahendust.

Leiame võrdlusele lahenduse x 2 ≡86 (mod 5).

x 2 ≡1 (mod 5).

Selle võrdluse saab lahendada eelmises lõigus näidatud viisil, kuid me kasutame seda, et 1 mooduli ruutjuur on ±1 ja võrdlusel on täpselt kaks lahendit. Seega on võrdlusmooduli 5 lahendus

x≡±1 (mod 5) või muul juhul x=±(1+5 t 1).

Asendame saadud lahenduse võrdlusmooduliga 5 2 =25:

x 2 ≡86 (mod 25)

x 2 ≡11 (mod 25)

(1+5t 1) 2 ≡11 (mod 25)

1+10t 1 +25t 1 2 ≡11 (mod 25)

10t 1 ≡ 10 (mod 25)

2t 1 ≡2 (mod 5)

t 1 ≡1 (mod 5) või mis on sama, t 1 =1+5t 2 .

Siis võrdlusmooduli 25 lahendus on x=±(1+5(1+5 t 2))=±(6+25 t 2). Asendame saadud lahenduse võrdlusmooduliga 5 3 =125:

x 2 ≡86 (mod 125)

(6+25t 2) 2 ≡86 (mod 125)

36+12·25 t 2 +625t 2 2 ≡86 (mod 125)

12·25 t 2 ≡50 (mod 125)

12t 2 ≡2 (mod 5)

2t 2 ≡2 (mod 5)

t 2 ≡1 (mod 5) või t 2 =1+5t 3 .

Siis on võrdlusmooduli 125 lahendus x=±(6+25(1+5 t 3))=±(31+125 t 3).

Vastus: x≡±31 (mod 125).

Vaatleme nüüd vormi võrdlust x 2 ≡a(mod 2 α). Sellisel võrdlusel ei ole alati kahte lahendust. Sellise mooduli puhul on võimalikud järgmised juhtumid:

1) α=1. Siis on võrdlusel lahendus alles siis, kui a≡1(mod 2) ja lahendus on x≡1 (mod 2) (üks lahendus).

2) α=2. Võrdlusel on lahendused ainult siis, kui a≡1(mod 4) ja lahendus on x≡±1 (mod 4) (kaks lahendust).

3) α≥3. Võrdlusel on lahendused ainult siis, kui a≡1(mod 8) ja selliseid lahendusi on neli. Võrdlus x 2 ≡a(mod 2 α) α≥3 puhul lahendatakse samamoodi nagu vormi võrdlused x 2 ≡a(mod lkα), ainult lahendused moodul 8 toimivad alglahendusena: x≡±1 (mod 8) ja x≡±3 (mod 8). Neid tuleks võrrelda mooduliga 16, seejärel mooduliga 32 jne kuni mooduli 2 α-ni.

Näide:

Lahendage võrdlus x 2 ≡33 (mod 64)

64 = 2 6 . Kontrollime, kas algsel võrdlusel on lahendus. 33≡1(mod 8), mis tähendab, et võrdlusel on 4 lahendust.

Modulo 8 on need lahendused: x≡±1 (mod 8) ja x≡±3(mod 8), mida saab esitada kui x=±(1+4 t 1). Asendame selle avaldise võrdlusmooduliga 16

x 2 ≡33 (mod 16)

(1+4t 1) 2 ≡1 (mod 16)

1+8t 1 +16t 1 2 ≡1 (mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Siis saab lahendus vormi x=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Asendame saadud lahenduse võrdlusmooduliga 32:

x 2 ≡ 33 (mod 32)

(1+8t 2) 2 ≡1 (mod 32)

1+16t 2 +64t 2 2 ≡1 (mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Siis saab lahendus vormi x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Asendame saadud lahenduse võrdlusmooduliga 64:

x 2 ≡33 (mod 64)

(1+16t 3) 2 ≡33 (mod 64)

1+32t 3 +256t 3 2 ≡33 (mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Siis saab lahendus vormi x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t 4). Niisiis, moodul 64, on algsel võrdlusel neli lahendust: x≡±17 (mod 64)i x≡±49 (mod 64).

Vaatame nüüd üldist võrdlust: x 2 ≡a(mod m), (a,m)=1, - mooduli kanooniline laiendamine m. Paragrahvi 4 lõike 4 teoreemi kohaselt on see võrdlus samaväärne süsteemiga

Kui selle süsteemi iga võrdlus on lahendatav, siis on lahendatav ka kogu süsteem. Olles leidnud lahenduse selle süsteemi igale võrdlusele, saame esimese astme võrdluste süsteemi, mille lahendamisel Hiina jäägiteoreemi abil saame lahenduse algsele võrdlusele. Pealegi on esialgse võrdluse erinevate lahenduste arv (kui see on lahendatav) 2 k, kui α = 1, 2 k+1, kui α = 2, 2 k+2, kui α≥3.

Näide:

Lahendage võrdlus x 2 ≡4 (mod 21).

Võrdlus ühe tundmatuga x näeb välja nagu

Kus. Kui a n ei jagatav m, seda nimetatakse kraadi võrdlused.

Otsuse järgi võrdlus on suvaline täisarv x 0 , mille jaoks

Kui X 0 rahuldab võrdlust, siis 9 võrdluse omaduse järgi on kõik täisarvud võrreldavad x 0 modulo m. Seega kõik võrdluslahendused, mis kuuluvad samasse jäägiklassi moodulisse T, käsitleme seda ühe lahendusena. Seega on võrdlusel nii palju lahendusi, kui palju on jääkide terviksüsteemi elemente, mis seda rahuldavad.

Võrdlusi, mille lahendushulgad langevad kokku, nimetatakse samaväärne.

2.2.1 Esimese astme võrdlused

Esimese astme võrdlus ühe tundmatuga X näeb välja nagu

(2.2)

Teoreem 2.4. Selleks, et võrdluses oleks vähemalt üks lahendus, on vajalik ja piisav, et arv b jagatud GCD( a, m).

Tõestus. Kõigepealt tõestame vajalikkust. Lase d = GCD( a, m) Ja X 0 - võrdluslahendus. Siis , see tähendab erinevust Oh 0 − b poolt jagatud T. Seega on selline täisarv q, Mida Oh 0 − b = qm. Siit b= ah 0 − qm. Ja sellest ajast peale d, ühisjagajana jagab numbreid A Ja T, siis minuend ja alajaotus jagatakse d, ja seetõttu b poolt jagatud d.

Nüüd tõestame piisavust. Lase d- arvude suurim ühisjagaja A Ja T, Ja b poolt jagatud d. Siis on jaguvuse definitsiooni järgi täisarvud nagu a 1 , b 1 ,T 1 , Mida .

Laiendatud Eukleidilise algoritmi abil leiame arvu 1 = gcd() lineaarse esituse a 1 , m 1 ):

mõne jaoks x 0 , y 0 . Korrutame viimase võrdsuse mõlemad pooled arvuga b 1 d:

või mis on sama,

see tähendab ja on võrdluse lahendus. □

Näide 2.10. Võrdlus 9 X= 6 (mod 12) omab lahendust, kuna gcd(9, 12) = 3 ja 6 jagub 3-ga. □

Näide 2.11. Võrdlus 6x= 9 (mod 12) ei sisalda lahendeid, kuna gcd(6, 12) = 6 ja 9 ei jagu 6-ga. □

Teoreem 2.5. Olgu võrdlus (2.2) lahendatav ja d = GCD( a, m). Siis koosneb võrdluslahendite hulk (2.2). d mooduli jäägiklassid T, nimelt kui X 0 - üks lahendustest, siis on kõik teised lahendused

Tõestus. Lase X 0 - võrdluslahend (2.2), st Ja , . Nii et selline asi on olemas q, Mida Oh 0 − b = qm. Nüüd asendades selle asemel viimase võrdsuse X 0 vormi suvaline lahend, kus, saame avaldise

, jagatav m. □

Näide 2.12. Võrdlus 9 X=6 (mod 12) omab täpselt kolm lahendit, kuna gcd(9, 12)=3. Need lahendused: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Näide 2.13. Võrdlus 11 X=2 (mod 15) omab ainulaadset lahendust X 0 = 7, kuna GCD(11,15)=1,□

Näitame teile, kuidas lahendada esimese astme võrdlusi. Ilma üldistust kaotamata eeldame, et GCD( a, t) = 1. Seejärel saab otsida lahendust võrdlusele (2.2) näiteks eukleidilise algoritmi abil. Tõepoolest, kasutades laiendatud Eukleidilise algoritmi, esitame arvu 1 lineaarse numbrikombinatsioonina a Ja T:

Korrutame selle võrdsuse mõlemad pooled arvuga b, saame: b = abq + mrb, kus abq - b = - mrb, see tähendab a ∙ (bq) = b(mod m) Ja bq- võrdluslahend (2.2).

Teine lahendus on kasutada Euleri teoreemi. Jällegi usume, et GCD(a, T)= 1. Rakendame Euleri teoreemi: . Korrutage võrdluse mõlemad pooled arvuga b: . Viimase avaldise ümberkirjutamine kui , saame, et on lahendus võrdlusele (2.2).

Las nüüd GCD( a, m) = d>1. Siis a = atd, m = mtd, kus GCD( A 1 , m 1) = 1. Lisaks on vaja b = b 1 d, et võrdlus oleks lahendatav. Kui X 0 - võrdluslahendus A 1 x = b 1 (mod m 1) ja ainus, kuna GCD( A 1 , m 1) = 1, siis X 0 on lahendus ja võrdlus A 1 xd = db 1 (mod m 1), ehk algne võrdlus (2.2). Puhka d- Lause 2.5 abil leitakse 1 lahendus.