Sammenligninger med enkel og sammensatt modul. Løse sammenligninger

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. Da , altså forskjellen Oh 0 − b delt på T. Så det er et slikt heltall q, Hva Oh 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. Så, ved definisjonen av delbarhet, er det heltall som f.eks 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), dvs Og , . Så det er noe slikt q, Hva Oh 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 vil si 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 , vi får, hva er løsningen sammenligninger (2.2).

La nå GCD( en, m) = d>1. Da 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.

To heltall a og b er sammenlignbare modulo et naturlig tall m є N hvis de, når de divideres med m, gir den samme resten. .

Teorem (sammenlignbarhetskriterium): . Konsekvens 1: hvert tall er sammenlignbart modulo m med resten når de er delt på m: . Konsekvens 2: et tall er sammenlignbart modulo m, dvs. osv., siden det er delelig med denne moden.

Grunnleggende sammenligningsegenskaper: 1). Relative sammenligninger er relativt likeverdige. 2). Sammenligninger for samme modul kan trekkes fra termin for termin: . Begrepet kan overføres fra en del til en annen, og tegnet endres til det motsatte. 3). I hver del av sammenligningen kan du legge til et hvilket som helst tall som er et multiplum av modulen: sammenligninger basert på den samme modulen kan multipliseres ledd for ledd. Konsekvenser: 1. Begge deler av sammenligningen kan heves til evt naturlig grad. 2. Begge deler av sammenligningen kan multipliseres med en hvilken som helst naturlig tall. 4). Begge sider av sammenligningen og modulen kan multipliseres med samme tall eller reduseres med en av deres felles divisorer. 5). Hvis en sammenligning finner sted over flere moduler, så skjer den også over en modul som er lik deres største multiplum eller største felles divisor

6). Hvis en sammenligning finner sted modulo m, så finner den sted for evt

deler av m. 7). Fellesdeleren til den ene delen av sammenligningen og modulen er divisoren til den andre delen av sammenligningen: , .

Fermats lille teorem: hvis a og m er koprimtall, så . Eulers funksjon er et tall positive tall, som ikke overstiger n og coprime til n. Hvis et heltall a er coprime til m, så . Eulers teorem: hvis et heltall a er coprime til m, så . Fermats teorem: 1. Hvis et heltall a ikke deler p, der p er primtall, så . 2. Hvis p er et primtall og a er et hvilket som helst heltall, så . Sammenliknbarhetsforhold er ekvivalensklasser. Ekvivalensklasser kalles også restklasser, og deres ekvivalenser kalles rester.

Løsning av sammenligninger: La , , mєN. Da kalles det en sammenligning av k-grader med en ukjent og har ikke mer enn m klasser med løsninger. Løsningene til denne sammenligningen vil være klasser av rester modulo m. Sammenligninger av første grad med en ukjent kan skrives på formen: hvis: 1). denne sammenligningen har ingen løsning (for eksempel 5x ). 2). Hvis løsningen på denne sammenligningen. 3). .

Teorem: La , , da , d være klasser av løsninger mod m. Metoder for å løse sammenligninger: 1). Testmetode for et komplett fradragssystem. 2). Koeffisientkonverteringsmetode. Ethvert tall som er et multiplum av modulen legges til eller trekkes fra høyre side, og erstatter koeffisientene på venstre side med antall sammenligninger med modulen. Det er mulig å transformere sammenligningene slik at de kan reduseres til a og få en løsning.

Sammenligning av tall modulo

Utarbeidet av: Irina Zutikova

MAOU "Lyceum nr. 6"

Klasse: 10 "a"

Vitenskapelig veileder: Zheltova Olga Nikolaevna

Tambov

2016

  • Problem
  • Prosjektmål
  • 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.

Prosjektmål:

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 emnet "Sammenligning av tall modulo" i klasse 10 "a".

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 begynnelse 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 skriv:

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) dividerer 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

  • HMS Olympiade 2016

    • La oss vurdere sammenligninger av skjemaets første grad

    øks≡ b(mod m),

    Hvordan løser man en slik sammenligning? La oss vurdere to tilfeller.

    Sak 1. La EN Og m gjensidig enkelt. Deretter den irreduserbare brøken m/a selv ber om å bli utvidet til en fortsatt brøkdel:

    Denne fortsatte brøken er selvfølgelig endelig, siden m/a- rasjonelt tall. Vurder de to siste passende fraksjonene:

    La oss huske viktig eiendom tellere og nevnere for passende brøker: mQn-1-aPn-1 =(-1)n. Neste (termin mQ n-1, flere m, kan kastes ut fra venstre side

    sammenligninger):

    -aP n-1≡ (-1) n (mod m) de.

    aP n-1≡ (-1) n-1 (mod m) de.

    a[(-1) n-1 P n-1 b]≡ b(mod m)

    og den eneste løsningen på den opprinnelige sammenligningen er:

    x ≡ (-1) n-1 P n-1 b(mod m)

    Eksempel. Løs sammenligningen 111x ≡ 75(mod 322).

    Løsning.(111, 322)=1. Vi aktiverer den euklidiske algoritmen:

    322=111 2+100

    (I likheter er ufullstendige kvotienter understreket.) Derfor n=4, og den tilsvarende kjeden

    brøken er:

    La oss beregne tellerne for passende brøker ved å lage en standardtabell for dette:

    Telleren for den nest siste passende brøken er 29, derfor er den ferdige formelen

    gir svaret: x≡ (-1) 3 ⋅ 29 ⋅ 75 ≡ -2175 ≡ 79 (mod 322)

    Tilfelle 2. La (a,m)=d. I dette tilfellet, for løsbarheten til sammenligningen øks≡ b(mod m)

    det er nødvendig det d delt b, ellers kan ikke sammenligningen utføres i det hele tatt.

    Virkelig, øks≡ b(mod m) skjer da, og først da, når øks-b delt på m fullstendig, dvs.

    ax- b=t m, t∈ Z, hvorfra b=ax-t⋅ m, og høyresiden av den siste likheten er et multiplum d.

    La b=db 1, a=da 1, m=dm 1. Så begge sider av sammenligningen xa 1 d≡ b 1 d (mod m 1 d) og del modulen med d:

    xa 1≡ b 1 (mod m 1),

    hvor allerede en 1 Og m 1 gjensidig enkelt. Ifølge sak 1 i dette avsnittet har en slik sammenligning en unik løsning x 0:

    x≡ x 0 (mod m 1)(*)

    I henhold til den originale modulen m, tall (*) danner like mange løsninger til den opprinnelige sammenligningen som tallene i formen (*) er inneholdt i hele systemet med rester: 0,1,2,..., m-2, m-1. Det er åpenbart fra tallene x = x 0 + t⋅m det komplette systemet med minst ikke-negative rester inkluderer kun x 0, x 0 + m 1, x 0 +2m 1, ..., x 0 +(d-1)m 1, dvs. total d tall. Dette betyr at den opprinnelige sammenligningen har d løsninger.

    La oss oppsummere tilfellene vurdert i form av følgende teorem

    Teorem 1. La (a,m)=d. Hvis b ikke delelig med d, sammenligning øks≡ b(mod m) har ingen løsninger. Hvis b flere d, sammenligning øks≡ b(mod m) har d biter av løsninger.



    Eksempel. Løs sammenligning 111x≡ 75 (mod 321).

    Løsning.(111,321)=3 , så la oss dele sammenligningen og dens modul med 3:

    37x≡ 25 (mod 107) og allerede (37,107)=1 .

    Vi slår på den euklidiske algoritmen (som vanlig er ufullstendige kvotienter understreket):

    Vi har n=4 og den fortsatte brøken er:

    Tabell for å finne tellerne for passende brøker:

    Betyr, x≡ (-1) 3 ⋅ 26 ⋅ 25 ≡ -650 (mod 107)≡ -8 (mod 107)≡ 99 (mod 107).

    Tre løsninger på den opprinnelige sammenligningen:

    x≡ 99 (mod 321), x≡ 206 (mod 321), x≡ 313 (mod 321),

    og det er ingen andre løsninger.

    Teorem 2. La m>1, (a,m)=1 Så sammenligning øks≡ b(mod m) har en løsning: x≡ ba ϕ (m)-1 (mod m).

    Eksempel. Løs sammenligning 7x≡ 3 (mod 10). Vi beregner:

    ϕ (10)=4; x≡ 3 ⋅ 7 4-1 (mod 10)≡ 1029 (mod 10)≡ 9 (mod 10).

    Det kan sees at denne metoden for å løse sammenligninger er god (i betydningen et minimum av intellektuelle kostnader for implementeringen), men kan kreve konstruksjon av et tall EN i ganske stor grad, noe som er ganske arbeidskrevende. For å virkelig føle dette, heve tallet 24789 til makten 46728 selv.

    Teorem 3. La r– primtall, 0 Så sammenligning øks≡ b(mod p) har en løsning:

    hvor er den binomiale koeffisienten.

    Eksempel. Løs sammenligning 7x≡ 2 (mod 11). Vi beregner:

    Lemma 1 (kinesisk restteorem). La det enkleste systemet med sammenligninger av første grad gis:

    Hvor m 1 ,m 2 ,...,m k parvis relativt prime. La videre, m 1 m 2 ...m k =M s m s; M s M s ∇ ≡ 1 (mod m s)(Selvfølgelig nummeret M s∇ kan alltid velges i det minste ved å bruke den euklidiske algoritmen, fordi (m s, M s)=1); x 0 =M 1 M 1 ∇ b 1 + M 2 M 2 ∇ b 2 +...+M k M k ∇ b k. Da tilsvarer system (*) én sammenligning x≡ x 0 (mod m 1 m 2 ... m k), dvs. løsningssettet (*) samsvarer med sammenligningsløsningssettet x≡ x 0 (mod m 1 m 2 ... m k).

    Eksempel. En dag henvendte den midterste kameraten seg til en smart venn og ba ham finne et tall som, når det deles på 4, etterlater en rest av 1, når det deles på 5, gir en resten av 3, og når det deles på 7, gir en rest. av 2. Den midterste kameraten har selv lett etter et slikt nummer i to uker. Den smarte kameraten satte umiddelbart sammen et system:

    som han begynte å løse ved hjelp av Lemma 1. Her er løsningen hans:

    b 1 = 1; b 2 = 3; b3 =2; m 1 m 2 m 3, dvs. Mi=35, M2=28, M3=20.

    de. M 1 ∇ =3, M 2 ∇ =2, M 3∇ =6. Betyr x 0=35 ⋅ 3 ⋅ 1+28 ⋅ 2 ⋅ 3+20 ⋅ 6 ⋅ 2=513. Etter dette, ifølge Lemma 1, fikk den smarte vennen umiddelbart svaret:

    x≡ 513 (mod 140) ≡ 93 (mod 140),

    de. det minste positive tallet som gjennomsnittsvennen søkte i to uker er 93. Så den smarte vennen hjalp nok en gang den gjennomsnittlige vennen.

    Lemma 2. Hvis b 1 , b 2 ,..., b k kjøres gjennom komplette systemer av rester modulo m 1 ,m 2 ,...,m k følgelig altså x 0 går gjennom hele systemet av modulo-rester m 1 m 2 ...m k.

    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 møtes 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 - en klasse 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, er det 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.

    Note 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.