Løs systemet med sammenligninger. Systemer for sammenligninger. og den eneste løsningen på den opprinnelige sammenligningen er

Sammenligning av tall modulo

Utarbeidet av: Irina Zutikova

MAOU "Lyceum nr. 6"

Klasse: 10 "a"

Vitenskapelig veileder: Zheltova Olga Nikolaevna

Tambov

2016

• Problem
• Målet med prosjektet
• Hypotese
• Prosjektmål og plan for å nå dem
• Sammenligninger og deres egenskaper
• Eksempler på problemer og deres løsninger
• Brukte sider og litteratur

Problem:

De fleste studenter bruker sjelden modulo-sammenligning av tall for å løse ikke-standardiserte og olympiske oppgaver.

Målet med prosjektet:

Vis hvordan du kan løse ikke-standard og olympiske oppgaver ved å sammenligne tall modulo.

Hypotese:

En dypere studie av emnet "Sammenligning av tall modulo" vil hjelpe elevene med å løse noen ikke-standardiserte og olympiske oppgaver.

Prosjektmål og plan for å nå dem:

1. Studer i detalj emnet "Sammenligning av tall modulo".

2. Løs flere ikke-standard og olympiske oppgaver ved å bruke modulo sammenligning av tall.

3. Lag et notat for studenter om emnet "Sammenligning av tall modulo."

4. Gjennomfør en leksjon om temaet «Sammenligning av tall modulo» i klasse 10a.

5.Gi klassen lekser om emnet «Sammenligning etter modul».

6.Sammenlign tiden for å fullføre oppgaven før og etter å ha studert emnet "Sammenligning etter modul".

7. Trekk konklusjoner.

Før jeg begynte å studere i detalj emnet "Sammenligning av tall modulo", bestemte jeg meg for å sammenligne hvordan det presenteres i forskjellige lærebøker.

• Algebra og begynnelsen av matematisk analyse. Avansert nivå. 10. klasse (Yu.M. Kolyagin og andre)
• Matematikk: algebra, funksjoner, dataanalyse. 7. klasse (L.G. Peterson og andre)
• Algebra og begynnelsen av matematisk analyse. Profilnivå. 10. klasse (E.P. Nelin og andre)
• Algebra og begynnelsen av matematisk analyse. Profilnivå. 10. klasse (G.K. Muravin og andre)

Som jeg fant ut, berører noen lærebøker ikke engang dette emnet, til tross for det avanserte nivået. Og emnet er presentert på den mest klare og tilgjengelige måten i læreboken av L.G. Peterson (Kapittel: Introduksjon til teorien om delbarhet), så la oss prøve å forstå "Sammenligning av tall modulo", og stole på teorien fra denne læreboken.

Sammenligninger og deres egenskaper.

Definisjon: Hvis to heltall a og b har de samme restene når de divideres med et heltall m (m>0), så sier de ata og b er sammenlignbare modulo m, og skrive:

Teorem: hvis og bare hvis forskjellen mellom a og b er delelig med m.

Egenskaper:

1. Refleksivitet av sammenligninger.Ethvert tall a er sammenlignbart med seg selv modulo m (m>0; a,m er heltall).
2. Symmetriske sammenligninger.Hvis tallet a er sammenlignbart med tallet b modulo m, så er tallet b sammenlignbart med tallet a modulo det samme (m>0; a,b,m er heltall).
3. Transitivitet av sammenligninger.Hvis tallet a er sammenlignbart med tallet b modulo m, og tallet b er sammenlignbart med tallet c modulo samme modulo, så er tallet a sammenlignbart med tallet c modulo m (m>0; a,b,c ,m er heltall).
4. Hvis tallet a er sammenlignbart med tallet b modulo m, så tallet a n sammenlignbar med tall b n modulo m(m>0; a,b,m-heltall; n-naturlig tall).

Eksempler på problemer og deres løsninger.

1. Finn det siste sifferet i tallet 3 999 .

Løsning:

Fordi Det siste sifferet i tallet er resten når det deles på 10

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)

(Fordi 34=81 1(mod 10);81 n 1(mod10) (etter eiendom))

Svar: 7.

2. Bevis at 2 4n -1 er delelig med 15 uten en rest. (Phystech2012)

Løsning:

Fordi 16 1 (mod 15), deretter

16n-1 0(mod 15) (etter eiendom); 16n= (2 4) n

2 4n -1 0 (mod 15)

3. Bevis at 12 2n+1 +11 n+2 Delelig med 133 uten rest.

Løsning:

12 2n+1 =12*144 n 12*11 n (mod 133) (etter eiendom)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Nummer (11n *133)deler med 133 uten rest. Derfor, (12 2n+1 +11 n+2 ) er delelig med 133 uten en rest.

4. Finn resten av tallet 2 delt på 15 2015 .

Løsning:

Siden 16 1 (mod 15), da

2 2015 8 (mod 15)

Svar: 8.

5. Finn resten av divisjonen med det 17. tallet 2 2015. (Phystech2015)

Løsning:

2 2015 =2 3 *2 2012 =8*16 503

Siden 16 -1 (mod 17), da

2 2015 -8 (mod 15)

8 9 (mod 17)

Svar: 9.

6. Bevis at tallet er 11 100 -1 er delelig med 100 uten en rest. (Phystech2015)

Løsning:

11 100 =121 50

121 50 21 50 (mod 100) (etter eiendom)

21 50 =441 25

441 25 41 25 (mod 100) (etter eiendom)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (etter eiendom)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100)(etter eiendom)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (etter eiendom)

41*21 3 =41*21*441

441 41 (mod 100) (etter eiendom)

21*41 2 =21*1681

1681 -19 (mod 100) (etter eiendom)

21*(-19)=-399

399 1 (mod 100) (etter eiendom)

Så 11 100 1 (mod 100)

11 100 -1 0 (mod 100) (etter eiendom)

7. Tre tall er gitt: 1771,1935,2222. Finn et tall slik at når de divideres med det, vil restene av de tre gitte tallene være like. (HSE2016)

Løsning:

La da det ukjente tallet være lik a

2222 1935(mod a); 1935 1771 (mod a); 2222 1771 (mod a)

2222-1935 0(moda) (etter eiendom); 1935-17710(moda) (etter eiendom); 2222-17710(moda) (etter eiendom)

287 0(mod a); 164 0(mod a); 451 0(mod a)

287-164 0(moda) (etter eiendom); 451-2870(moda)(etter eiendom)

123 0(mod a); 164 0(mod a)

164-123 0(mod a) (etter eiendom)

41

La oss vurdere systemet med sammenligninger

Hvor f1(x), f2(x), …. , fs(x)€Z[x].

Teorem 1. La M = være det minste felles multiplum av tallene m1,m2,...,ms. Hvis a tilfredsstiller system (2), så tilfredsstiller et hvilket som helst tall fra klassen a modulo M dette systemet.

Bevis. La b€ til klasse a. Siden a ≡ b(mod M), så a ≡b(mod m), i= 1,2,...,s (sammenligningsegenskap 16). Følgelig tilfredsstiller b, som a, enhver sammenligning av systemet, noe som beviser teoremet. Derfor er det naturlig å vurdere løsningen av system (2) som en klasse modulo M.

Definisjon. Løsning av sammenligningssystemet(2) er klassen av tall modulo M = som tilfredsstiller hver sammenligning av systemet.

12. La oss umiddelbart merke oss at oddetall ikke tilfredsstiller den andre sammenligningen. Ved å ta partall fra hele systemet av rester modulo 12, ved direkte verifisering er vi overbevist om at tallene 2, -2, 6 tilfredsstiller den andre sammenligningen, og systemet har to løsninger: x ≡ 2(mod l2), x ≡ - 2 (mod 12).

La oss vurdere systemet med sammenligninger av 1. grad (3)

Teorem 2. La d=(m1,m2), M = .

Hvis c1 - c2 ikke er delelig med d, har system (3) ingen løsninger.

Hvis (c1 -c2):d, så har system (3) én løsning - en klasse modulo M.

Bevis. Fra den første sammenligningen x = c1+m1t, t€Z. Bytt inn i den andre sammenligningen: с1+ m1t ≡ c2(mod m2) eller

m1t ≡ c2-cl (mod m2). Denne sammenligningen har en løsning bare hvis (c2 – c1): d.

Og løsningen er en klasse modulo (Setning 4 fra §2).

La løsningen være , det vil si hvor k€Z.

M== , det vil si x≡c1+m1t0(mod M) er løsningen

Eksempler.

1. :2 har systemet én løsningsklasse modulo 24. Fra 1. sammenligning x =2+6t. Ved å erstatte x i den andre sammenligningen har vi: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t=2(mod8); t=-1 (mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, det vil si x≡-4(mod 24).

2. 7-3 er ikke delelig med 3, systemet har ingen løsninger.

Konsekvens 1. Sammenligningssystem (4)

Enten har den ingen løsninger, eller så har den én løsning - en klasse modulo M=.

Bevis. Hvis systemet med de to første sammenligningene ikke har noen løsninger, så har ikke (4) løsninger. Hvis den har en løsning x ≡ a(mod), så ved å legge til en tredje sammenligning av systemet til denne sammenligningen, får vi igjen et system av formen (3), som enten har én løsning eller ingen løsninger. Hvis det har en løsning, vil vi fortsette på denne måten til vi har brukt opp alle sammenligninger av system (4). Hvis det er en løsning, er dette en klasse modulo M.

Kommentar. LCM-egenskapen brukes her: =.

Konsekvens 2. Hvis m1,m2,…,ms er parvis coprime, så har system (4) én løsning - modulo klasse M=m1m2…ms.

Eksempel:

Siden modulene er parvis relativt enkle, har systemet én løsning - modulo klasse 105 = 5*3*7. Fra den første sammenligningen

Vi bytter inn i den andre sammenligningen: 2 +5t≡ 0(mod 3) eller 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . La oss erstatte i den tredje sammenligningen:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. deretter x=-3+15(1+7l); x=12+105l; x≡12 (mod 105).

La oss bli kjent andre metode for å løse dette systemet, (Vi bruker det faktum at systemet har én løsning.) La oss multiplisere begge delene og modulen til den første sammenligningen med 21, den andre med 35 og den tredje med 15: fra summen av første og tredje trekker vi fra den andre:

(36-35) x ≡ 75 + 42 (modl05); x=117(mod105); x≡12(mod105).

La oss nå se på et system med sammenligninger av første grad av generell form

Hvis en sammenligning av dette systemet ikke har noen løsninger, har systemet ingen løsninger. Hvis hver sammenligning av system (5) er løsbar, løser vi den for x og får et ekvivalent system av formen (4):

Hvor (setning 4, §2).

Ved konsekvens 1 har systemet enten ingen løsninger eller én løsning.

Eksempel:

Etter å ha løst hver sammenligning av systemet, får vi et ekvivalent system

Dette systemet har én løsning - klasse modulo 105. Multipliserer den første sammenligningen og modulen med 3, og den andre med 35, får vi

Trekker vi den første sammenligningen multiplisert med 11 fra den andre sammenligningen, får vi 2x ≡-62(modl05), hvorfra x ≡ -31(modl05).

Problemer som koker ned til vurderingen av et system med sammenligninger av 1. grad ble vurdert i regnestykket til den kinesiske matematikeren Sun Tzu, som levde rundt begynnelsen av vår tidsregning. Spørsmålet hans ble stilt i følgende form: finn et tall som gir gitte rester når det deles på gitte tall. Det gir også en løsning som tilsvarer følgende teorem.

Teorem (kinesisk restsetning). La m1,m2,...,ms være parvise coprimtall, M = mlm2...ms, β1, β2,..., βs valgt slik at

Deretter løsningen av systemet

Det vil se ut som x≡x0(mod M).

Bevis. Siden vi får x0≡

På lignende måte sjekker vi at x0≡c2(mod m2),..., x0≡cs(mod ms), det vil si at x0 tilfredsstiller alle

systemsammenlikninger.

10. Sammenligninger av 1. grad. Usikre ligninger

§ 2. Sammenligninger av 1. grad. Usikre ligninger

1. grads sammenligning kan reduseres til formen ax≡b(mod m).

Teorem 4. Hvis (a,m) = 1, så har sammenligningsaksen ≡b(mod m) (2) en unik løsning.

Bevis. La oss ta 0,1,2,...,m-1 - et komplett system av rester modulo m. Siden (a,m) = 1, så er 0,a,2a,...,(m-1)a også et komplett system av rester (Setning 3, §2, kapittel 2.). Den inneholder ett og bare ett tall som kan sammenlignes med b modulo m (tilhører samme klasse som b). La dette være ax 0, det vil si ax 0 € klasse b eller ax 0 ≡b(mod m). x ≡x 0 (mod m) er den eneste løsningen på (2). Teoremet er bevist.

Teorem 5. Hvis (a, m)= 1, så er løsningen til sammenligningen ax≡b(mod m) klassen x 0 ≡a φ (m)-1 b(mod m).

Bevis. Siden (a,m) = 1, så etter Eulers prinsipp a φ(m) ≡1(mod m). Det er lett å se at x 0 ≡a φ (m)-1 b (mod m) er løsningen på sammenligning (2). Faktisk, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Det følger av teorem 4 at denne løsningen er unik.

La oss vurdere sammenligningsløsningsmetoder akse ≡b(mod m).

1. Valgmetode. Ved å ta hele systemet av rester modulo m, velger vi tall som tilfredsstiller sammenligningen.

2. Bruke Eulers teorem (setning 5).

3. Koeffisientomregningsmetode. Vi må prøve å transformere koeffisientene slik at høyresiden kan deles med koeffisienten til x. Transformasjonene det er snakk om er følgende: erstatte koeffisienter med de absolutt minste restene, erstatte tallet b med et tall som er sammenlignbart i absolutt verdi (legge til et tall som er et multiplum av den absolutte verdien) slik at sistnevnte er delelig med a, flytte fra a og b til andre tall som kan sammenlignes med dem , som vil ha en felles divisor osv. I dette tilfellet bruker vi egenskapene til sammenligninger og teoremer på ekvivalente sammenligninger basert på dem.

1) 223x ≡ 115 (mod ll).

Først erstatter vi koeffisientene med de minste absolutte verdifradragene: 3х ≡ 5(mod 11). Hvis vi bruker teoremet

Euler altså

x≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Det er imidlertid lettere å konvertere koeffisientene. La oss erstatte sammenligningen med en ekvivalent ved å legge til høyre side et tall som er et multiplum av modulen:

3x ≡ 5 + 22 (mod 11). Ved å dele begge sider med tallet 3, coprime til modulen, får vi x ≡ 9(mod l1).

2) 111x≡ 8 (mod 34).

Vi bruker koeffisientkonverteringsmetoden.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16 (mod 34).

Teorem 6. Hvis (a, m) = d og b ikke er delbare med d, så har sammenligning (1) ingen løsninger.

Bevis (ved selvmotsigelse). La klassen x 0 være en løsning, det vil si ax 0 ≡b (mod m) eller (ax 0 -b):m, og derfor (ax 0 -b):d. Men a:d, da er b:d en selvmotsigelse. Derfor har sammenligningen ingen løsninger.

Teorem 7. Hvis (a,m)= d, d>1, b:d, så har sammenligning(1) d

løsninger som utgjør én klasse av modulo-rester og finnes av formlene

Hvor Med tilfredsstiller tilleggssammenligningen

Kommentar. I følge teoremet løses sammenligning (1) som følger.

1) Etter å ha forsikret oss om at (a,m) = d, d> 1 og b:d, deler vi begge delene i sammenligninger (2) med d og får en hjelpesammenligning a 1 x≡b 1 (mod m 1) , hvor . Sammenligningen har bare én løsning. La klasse c være løsningen.

2) Skriv svaret x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1) m 1 (mod m).

Bevis. Hjelpesammenlikningen i henhold til setning 2(3) tilsvarer den opprinnelige sammenligningen (2). Siden ( 1, Da har hjelpesammenligningen en unik løsning - klassen modulo m 1 = . La x≡c(mod m 1) være løsningen. Klassen med tall c modulo m 1 deler seg i d-klasser modulo m: .

Faktisk har et hvilket som helst tall fra klassen x0 modulo m 1 formen x 0 +m 1 t. Del t med resten med d: t = dq +r, hvor 0≤r

Så, sammenligning (1) har d løsninger modulo m: x0, x0+m1,..., x0 +(d-1)m1. (horisontale linjer øverst)

Eksempler.

1) 20x≡ 15 (mod 108). Siden (20,108) = 4 og 15 ikke er delbare med 4, finnes det ingen løsninger.

2) 20x≡ 44 (mod 108). (20,108) = 4 og 44:4, derfor har sammenligningen fire løsninger. Ved å dele begge delene og modulen med 4 får vi:

5х≡11(mod 27); 5 x ≡ 11-81 ≡ -70 (mod 27), x ≡ -14 ≡ 13 (mod 27). Deretter x≡13 + 27r(mod 108), hvor r = 0,1,2,3. jeg jj

Svar: x≡13(modl08); x ≡ 40(modl08); x ≡ 67(modl08); x≡94(modl08).

Anvendelse av teorien om sammenligninger for å løse usikre ligninger

La oss vurdere en ubestemt eller, som den ellers kalles, en diofantisk ligning av første grad med to ukjente ax + by = c, hvor a, b, c € Z. Du må løse denne ligningen i heltall. Hvis (a,b)=d og c ikke er delbare med d, så er det åpenbart at sammenligningen ikke har noen løsninger i heltall. Hvis c er delelig med d, så del begge sider av ligningen med d. Derfor er det nok å vurdere tilfellet når (a, b) =1.

Siden ax er forskjellig fra c med et multiplum av b, så er ax ≡ c(mod b) (uten tap av generalitet kan vi anta at b > 0). Ved å løse denne sammenligningen får vi x ≡x1 (mod b) eller x=x1+bt, hvor t€Z. For å bestemme de tilsvarende verdiene av y har vi ligningen a(x1 + bt) + by = c, hvorfra

Dessuten er - et heltall, det er en delverdi av den ukjente y, som tilsvarer x1 (det viser seg, som x1, ved t = 0). Og den generelle løsningen til ligningen vil ha form av et system av ligninger x=x1+bt, y=y1-at, hvor t er et hvilket som helst heltall.

Merk at 1) ligningen ax + by = c kunne løses ved å starte med sammenligningen med ≡ c(mod a), siden by er forskjellig fra c med et multiplum av a;

2) det er mer praktisk å velge som en modul minste modul a og b.

Eksempel, 50x – 42y= 34.

Del begge sider av ligningen med 2.

25x ≡ 17(mod2l); 4x ≡ 17 (mod 21) eller 4x ≡ 17-21 ≡ -4(mod21).

x ≡ -1 (mod 21), det vil si x=-1+21t, t€Z. La oss erstatte funnet x i ligningen. 25(-1 + 21t)-21y=17; 21у =-42 + 25* 21t og у =-2 + 25t.

Definisjon 1. Hvis to tall er 1) en Og b når delt på s gi den samme resten r, da kalles slike tall equiremainder eller sammenlignbar i modul s.

Uttalelse 1. La s et positivt tall. Deretter hvert tall en alltid og dessuten på den eneste måten kan representeres i skjemaet

Men disse tallene kan fås ved å stille inn r lik 0, 1, 2,..., s−1. Derfor sp+r=a vil få alle mulige heltallsverdier.

La oss vise at denne representasjonen er unik. La oss late som det s kan representeres på to måter a=sp+r Og a=s 1 s+r 1 . Deretter

(2)

Fordi r 1 aksepterer et av tallene 0,1, ..., s−1, deretter den absolutte verdien r 1 −r mindre s. Men av (2) følger det at r 1 −r flere s. Derfor r 1 =r Og s 1 =s.

Antall r kalt minus tall en modulo s(med andre ord, tallet r kalt resten av et nummer en på s).

Uttalelse 2. Hvis to tall en Og b sammenlignbar i modul s, Det a−b delt på s.

Egentlig. Hvis to tall en Og b sammenlignbar i modul s, så når delt på s ha den samme resten s. Deretter

delt på s, fordi høyre side av ligning (3) er delt med s.

Uttalelse 3. Hvis forskjellen på to tall er delelig med s, da er disse tallene sammenlignbare i modul s.

Bevis. La oss betegne med r Og r 1 divisjon resten en Og b på s. Deretter

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

Fra det første eksemplet følger det at 25 når deles på 7 gir den samme resten som 39. Faktisk, 25 = 3·7+4 (resten 4). 39=3·7+4 (resten 4). Når du vurderer det andre eksemplet, må du ta i betraktning at resten må være et ikke-negativt tall mindre enn modulen (dvs. 4). Da kan vi skrive: −18=−5·4+2 (rest 2), 14=3·4+2 (rest 2). Derfor vil −18 når deles på 4 etterlater en rest av 2, og 14 når de divideres med 4 gir en rest av 2.

Egenskaper til modulo-sammenligninger

Eiendom 1. For alle en Og s Alltid

det er ikke alltid en sammenligning

Hvor λ er den største felles deleren av tall m Og s.

Bevis. La λ største felles deler av tall m Og s. Deretter

Fordi m(a−b) delt på k, Det

Derfor

Og m er en av divisorene til tallet s, Det

Hvor h=pqs.

Merk at vi kan tillate sammenligninger basert på negative moduler, dvs. sammenligning a≡b mod( s) betyr i dette tilfellet at forskjellen a−b delt på s. Alle egenskapene til sammenligninger forblir i kraft for negative moduler.

Ved n gir de de samme restene.

Ekvivalente formuleringer: a og b sammenlignbar i modul n hvis deres forskjell en - b er delelig med n, eller hvis a kan representeres som en = b + kn , Hvor k- noe heltall. For eksempel: 32 og -10 er sammenlignbare modulo 7, siden

Utsagnet "a og b er sammenlignbare modulo n" er skrevet som:

Modulo likhetsegenskaper

Modulo sammenligningsrelasjonen har egenskapene

Hvilke som helst to heltall en Og b sammenlignbar modulo 1.

For tallene en Og b var sammenlignbare i modul n, er det nødvendig og tilstrekkelig at deres forskjell er delelig med n.

Hvis tallene og er parvis sammenlignbare i modul n, deretter deres summer og , samt produktene og er også sammenlignbare i modul n.

Hvis tallene en Og b sammenlignbar i modul n, deretter gradene deres en k Og b k er også sammenlignbare i modul n under enhver naturlig k.

Hvis tallene en Og b sammenlignbar i modul n, Og n delt på m, Det en Og b sammenlignbar i modul m.

For tallene en Og b var sammenlignbare i modul n, presentert i form av sin kanoniske dekomponering i enkle faktorer s Jeg

nødvendig og tilstrekkelig til

Sammenligningsrelasjonen er en ekvivalensrelasjon og har mange av egenskapene til vanlige likheter. For eksempel kan de legges til og multipliseres: if

Sammenligninger kan imidlertid generelt sett ikke deles på hverandre eller med andre tall. Eksempel: , men reduseres med 2, får vi en feilaktig sammenligning: . Forkortelsesreglene for sammenligninger er som følger.

Du kan heller ikke utføre operasjoner på sammenligninger hvis modulene deres ikke stemmer overens.

Andre eiendommer:

Beslektede definisjoner

Fradragsklasser

Settet med alle tall som kan sammenlignes med en modulo n kalt fradragsklasse en modulo n , og er vanligvis betegnet [ en] n eller . Dermed er sammenligningen ekvivalent med likheten mellom restklasser [en] n = [b] n .

Siden modulo sammenligning n er en ekvivalensrelasjon på settet med heltall, så er restklassene modulo n representere ekvivalensklasser; deres antall er likt n. Settet med alle restklasser modulo n betegnet med eller.

Operasjonene med addisjon og multiplikasjon ved å indusere tilsvarende operasjoner på settet:

Med hensyn til disse operasjonene er settet en endelig ring, og hvis n enkelt - begrenset felt.

Fradragssystemer

Restsystemet lar deg utføre aritmetiske operasjoner på et begrenset sett med tall uten å gå utover grensene. Fullt system med fradrag modulo n er ethvert sett med n heltall som er uforlignelige modulo n. Vanligvis blir de minste ikke-negative restene tatt som et komplett system av rester modulo n

eller de absolutt minste fradragene som består av tall

ved oddetall n og tall

i tilfelle jevn n .

Løse sammenligninger

Sammenligninger av første grad

I tallteori, kryptografi og andre vitenskapsfelt oppstår ofte problemet med å finne løsninger på førstegradssammenlikninger av formen:

Å løse en slik sammenligning begynner med å beregne gcd (a, m)=d. I dette tilfellet er 2 tilfeller mulig:

• Hvis b ikke et multiplum d, så har sammenligningen ingen løsninger.
• Hvis b flere d, så har sammenligningen en unik løsning modulo m / d, eller, hva er det samme, d modulo løsninger m. I dette tilfellet, som et resultat av å redusere den opprinnelige sammenligningen med d sammenligningen er:

Hvor en 1 = en / d , b 1 = b / d Og m 1 = m / d er heltall, og en 1 og m 1 er relativt gode. Derfor nummeret en 1 kan inverteres modulo m 1, det vil si finne et slikt tall c, det (med andre ord, ). Nå er løsningen funnet ved å multiplisere den resulterende sammenligningen med c:

Praktisk beregning av verdi c kan implementeres på forskjellige måter: ved hjelp av Eulers teorem, Euklids algoritme, teorien om fortsatte brøker (se algoritme), etc. Spesielt Eulers teorem lar deg skrive ned verdien c som:

Eksempel

Til sammenligning har vi d= 2, så modulo 22 har sammenligningen to løsninger. La oss erstatte 26 med 4, sammenlignet med modulo 22, og deretter redusere alle 3 tallene med 2:

Siden 2 er coprime til modulo 11, kan vi redusere venstre og høyre side med 2. Som et resultat får vi én løsning modulo 11: , tilsvarende to løsninger modulo 22:.

Sammenligninger av andre grad

Å løse sammenligninger av andre grad kommer ned til å finne ut om et gitt tall er en kvadratisk rest (ved å bruke den kvadratiske resiprositetsloven) og deretter beregne kvadratroten modulo.

Historie

Den kinesiske restsetningen, kjent i mange århundrer, sier (i moderne matematisk språk) at restringen modulo produktet av flere coprimtall er

Sammenligning med en ukjent x ser ut som

Hvor . Hvis en n ikke delelig med m, det er det som heter grad sammenligninger.

Ved avgjørelse sammenligning er et hvilket som helst heltall x 0 , for hvilket

Hvis X 0 tilfredsstiller sammenligningen, så, i henhold til egenskapen til 9 sammenligninger, er alle heltall sammenlignbare med x 0 modulo m. Derfor er alle sammenligningsløsninger som tilhører samme restklasse modulo T, vil vi vurdere det som én løsning. Dermed har sammenligningen like mange løsninger som det er elementer i det komplette systemet av rester som tilfredsstiller den.

Sammenligninger hvis løsningssett faller sammen kalles tilsvarende.

2.2.1 Sammenligninger av første grad

Første grads sammenligning med en ukjent X ser ut som

(2.2)

Teorem 2.4. For at en sammenligning skal ha minst én løsning, er det nødvendig og tilstrekkelig at antallet b delt på GCD( en, m).

Bevis. Først beviser vi nødvendigheten. La d = GCD( en, m) Og X 0 - sammenligningsløsning. Deretter , altså forskjellen Åh 0 − b delt på T. Så det er et slikt heltall q, Hva Åh 0 − b = qm. Herfra b= ah 0 − qm. Og siden d, som en felles divisor, deler tall EN Og T, så deles minuend og subtrahend med d, og derfor b delt på d.

La oss nå bevise tilstrekkeligheten. La d- største felles deler av tall EN Og T, Og b delt på d. Da, ved definisjonen av delbarhet, eksisterer det følgende heltall en 1 , b 1 ,T 1 , Hva .

Ved å bruke den utvidede euklidiske algoritmen finner vi en lineær representasjon av tallet 1 = gcd( en 1 , m 1 ):

for noen x 0 , y 0 . La oss multiplisere begge sider av den siste likheten med b 1 d:

eller, hva er det samme,

,

det vil si, og er løsningen på sammenligningen. □

Eksempel 2.10. Sammenligning 9 X= 6 (mod 12) har en løsning siden gcd(9, 12) = 3 og 6 er delelig med 3. □

Eksempel 2.11. Sammenligning 6x= 9 (mod 12) har ingen løsninger, siden gcd(6, 12) = 6, og 9 ikke er delelig med 6. □

Teorem 2.5. La sammenligning (2.2) være løsbar og d = GCD( en, m). Da består settet med sammenligningsløsninger (2.2) av d modulo restklasser T, nemlig hvis X 0 - en av løsningene, så er alle andre løsninger

Bevis. La X 0 - sammenligningsløsning (2.2), altså Og , . Så det er noe slikt q, Hva Åh 0 − b = qm. Nå erstatter inn i den siste likestillingen i stedet for X 0 en vilkårlig løsning av formen, hvor vi får uttrykket

, delelig med m. □

Eksempel 2.12. Sammenligning 9 X=6 (mod 12) har nøyaktig tre løsninger, siden gcd(9, 12)=3. Disse løsningene: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Eksempel 2.13. Sammenligning 11 X=2 (mod 15) har en unik løsning X 0 = 7, siden GCD(11,15)=1.□

Vi viser deg hvordan du løser førstegradssammenlikninger. Uten tap av generalitet, vil vi anta at GCD( en, t) = 1. Deretter kan løsningen til sammenligning (2.2) søkes, for eksempel ved hjelp av den euklidiske algoritmen. Faktisk, ved å bruke den utvidede euklidiske algoritmen, representerer vi tallet 1 som en lineær kombinasjon av tall en Og T:

La oss multiplisere begge sider av denne likheten med b, vi får: b = abq + mrb, hvor abq - b = - mrb, det er en ∙ (bq) = b(mod m) Og bq- sammenligningsløsning (2.2).

En annen løsning er å bruke Eulers teorem. Igjen tror vi at GCD(a, T)= 1. Vi bruker Eulers teorem: . Multipliser begge sider av sammenligningen med b: . Omskriver det siste uttrykket som , får vi som er en løsning på sammenligning (2.2).

La nå GCD( en, m) = d>1. Deretter en = entd, m = mtd, hvor GCD( EN 1 , m 1) = 1. I tillegg er det nødvendig b = b 1 d, for at sammenligningen skal kunne løses. Hvis X 0 - sammenligningsløsning EN 1 x = b 1 (mod m 1), og den eneste, siden GCD( EN 1 , m 1) = 1, da X 0 vil være løsningen og sammenligningen EN 1 xd = db 1 (mod m 1), altså den opprinnelige sammenligningen (2.2). Hvile d- 1 løsninger er funnet av teorem 2.5.