Pirmojo laipsnio palyginimas su nežinomu turi tokią formą:

f(x) 0 (mod m); f(X) = Oi + a n. (1)

Išspręskite palyginimą reiškia rasti visas x reikšmes, kurios jį tenkina. Vadinami du palyginimai, atitinkantys tas pačias x reikšmes lygiavertis.

Jei palyginimas (1) kai kuriuos tenkina x = x 1, tada (pagal 49) visi skaičiai, palyginami su x 1, modulis m: x x 1 (mod m). Visa ši skaičių klasė skaičiuojama kaip vienas sprendimas. Su šiuo susitarimu galima padaryti tokią išvadą.

66.S lygiavimas (1) turės tiek sprendimų, kiek bus ją tenkinančios visos sistemos likučių.

Pavyzdys. Palyginimas

6x– 4 0 (8 mod.)

tarp visos modulio 8 likučių sistemos skaičių 0, 1,2, 3, 4, 5, 6, 7, du skaičiai tenkina: X= 2 ir X= 6. Todėl šis palyginimas turi du sprendimus:

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

I laipsnio palyginimas perkeliant laisvą terminą (su priešingu ženklu) į dešinę pusę gali būti sumažintas iki formos

kirvis b(mod m). (2)

Apsvarstykite palyginimą, kuris tenkina sąlygą ( a, m) = 1.

Pagal 66 mūsų palyginimas turi tiek sprendimų, kiek yra ją tenkinančių visos sistemos likučių. Bet kai x eina per visą modulo likučių sistemą t, tada Oi eina per visą atskaitymų sistemą (iš 60). Todėl už vieną ir tik vieną vertę X, paimta iš visos sistemos, Oi bus palyginama su b. Taigi,

67. Jei (a, m) = 1 palyginimo ašis b(mod m)turi vieną sprendimą.

Leisk dabar ( a, m) = d> 1. Tada palyginimui (2), kad būtų sprendiniai, būtina (iš 55), kad b padalintas į d, kitu atveju palyginimas (2) neįmanomas bet kuriam sveikajam skaičiui x . Darant prielaidą, kad todėl b daugkartinis d,įdėkime a = a 1 d, b = b 1 d, m = m 1 d. Tada palyginimas (2) bus lygiavertis šiam (sumažintas d): a 1 x b 1 (mod m), kuriame jau ( a 1 , m 1) = 1, ir todėl jis turės vieną sprendimą modulo m vienas . Leisti X 1 yra mažiausia neneigiama šio tirpalo liekana modulo m 1 , tada visi skaičiai x , formuojant šį sprendimą galima rasti formoje

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

Modulo, skaičiai (3) sudaro ne vieną sprendinį, o daugiau, lygiai tiek sprendinių, kiek skaičių (3) yra eilutėje 0, 1, 2, ..., m 1 mažiausiai neneigiamų liekanų modulio m. Tačiau čia sumažės šie skaičiai (3):

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

tie. Iš viso d skaičiai (3); taigi palyginimas (2) turi d sprendimus.

Gauname teoremą:

68. Tegul (a, m) = d. palyginimo ax b ( mod m) neįmanoma, jei b nesidalija iš d. Kai b yra d kartotinis, palyginimas turi d sprendinių.

69. Pirmojo laipsnio palyginimo sprendimo būdas, remiantis tęstinių trupmenų teorija:

Santykį išplečiant į tęstinę dalį m:a,

ir atsižvelgiant į paskutinius du konvergentus:

pagal tęstinių frakcijų savybes (pagal 30 ) mes turime

Taigi palyginimas turi sprendimą

paieškai, kurios pakanka apskaičiuoti P n- 1 pagal 30 punkte nurodytą metodą.

Pavyzdys. Išspręskime palyginimą

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

Čia (111, 321) = 3, o 75 yra 3 kartotinis. Todėl palyginimas turi tris sprendinius.

Padalinę abi palyginimo dalis ir modulį iš 3, gauname palyginimą

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

kurį pirmiausia turime nuspręsti. Mes turime

q
P 3

Taigi, šiuo atveju n = 4, P n - 1 = 26, b= 25, ir mes turime palyginimo (5) sprendimą formoje

x–26 ∙ 25 99 (mod. 107).

Taigi palyginimo (4) sprendiniai pateikiami taip:

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

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

Atvirkštinio elemento modulo a skaičiavimas

70.Jei sveikieji skaičiai a ir n koprime, tada yra skaičius a′, tenkinantis palyginimą a ∙ a′ ≡ 1 (mod n). Skaičius a′ paskambino dauginamasis atvirkštinis modulio n ir tam naudojamas žymėjimas a- 1 (mod n).

Kai kurių atvirkštinių dydžių modulio skaičiavimas gali būti atliktas pirmojo laipsnio palyginimo su vienu nežinomu sprendimu, kuriame x priimtas numeris a′.

Norėdami rasti palyginimo sprendimą

a x≡ 1 (mod m),

kur ( esu)= 1,

galima naudoti Euklido algoritmą (69) arba Fermat-Eulerio teoremą, kuri teigia, kad jei ( esu) = 1, tada

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

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

Grupės ir jų savybės

Grupės yra viena iš taksonominių klasių, naudojamų klasifikuojant matematines struktūras, turinčias bendras charakteristikas. Grupės susideda iš dviejų dalių: daug (G) ir operacijos() apibrėžta šiame rinkinyje.

Aibės, elemento ir narystės sąvokos yra pagrindinės neapibrėžtos šiuolaikinės matematikos sąvokos. Bet kurią aibę apibrėžia joje esantys elementai (kurie, savo ruožtu, taip pat gali būti aibės). Taigi, mes sakome, kad aibė yra apibrėžta arba duota, jei bet kuriam elementui galime pasakyti, ar jis priklauso šiai aibei, ar ne.

Dviems komplektams A, Bįrašų B A, B A, B∩ A, B A, B \ A, A × B reiškia, atitinkamai, kad B yra aibės poaibis A(t. y. bet koks elementas iš B taip pat yra įtraukta į A, pavyzdžiui, natūraliųjų skaičių aibė yra realiųjų skaičių aibėje; be to, visada A A), B yra tinkamas rinkinio poaibis A(tie. B A ir B ≠ A), daugelio sankirta B ir A(t. y. visi tokie elementai, kurie yra vienu metu ir viduje A, ir į B, pavyzdžiui, sveikųjų skaičių ir teigiamų realiųjų skaičių sankirta yra natūraliųjų skaičių aibė), aibių sąjunga B ir A(t. y. rinkinys, sudarytas iš elementų, kurie yra arba A, arba viduje B), nustatykite skirtumą B ir A(t. y. elementų rinkinys, esantis B, bet nemeluok A), Dekarto aibių sandauga A ir B(t. y. formos porų rinkinys ( a, b), kur a A, b B). Per | A| visada žymimas aibės kardinalumas A, t.y. elementų skaičius rinkinyje A.

Operacija yra taisyklė, pagal kurią bet kurie du aibės elementai G(a ir b) yra susietas su trečiuoju elementu iš G: a b.

Daug elementų G su operacija, vadinama grupė jei tenkinamos toliau nurodytos sąlygos.

Ties n jie duoda tą pačią likutį.

Lygiavertės formulės: a ir b panašus modulis n jei jų skirtumas a - b dalijasi iš n , arba jei a galima pavaizduoti kaip a = b + kn , kur k yra tam tikras sveikasis skaičius. Pavyzdžiui: 32 ir −10 yra suderinti modulio 7, nes

Teiginys "a ir b yra suderinti modulio n" parašytas taip:

Modulo lygybės savybės

Modulinio palyginimo santykis turi savybių

Bet kurie du sveikieji skaičiai a ir b yra palyginami modulo 1.

Dėl skaičių a ir b buvo palyginami modulo n, būtina ir pakanka, kad jų skirtumas dalytųsi iš n.

Jei skaičiai ir yra poromis palyginami modulo n, tada jų sumos ir , taip pat produktai ir taip pat yra palyginami modulo n.

Jei skaičiai a ir b panašus modulis n, tada jų laipsniai a k ir b k taip pat yra palyginami modulo n bet kokiam natūraliam k.

Jei skaičiai a ir b panašus modulis n, ir n padalytą m, tada a ir b panašus modulis m.

Dėl skaičių a ir b buvo palyginami modulo n, vaizduojamas kaip jo kanoninis skaidymas į pirminius veiksnius p i

būtinas ir pakankamas

Lyginimo santykis yra lygiavertiškumas ir turi daug įprastų lygybių savybių. Pavyzdžiui, juos galima sudėti ir padauginti: jei

Tačiau palyginimų, paprastai kalbant, negalima padalyti vienas į kitą arba iš kitų skaičių. Pavyzdys: , tačiau sumažinę 2, gauname klaidingą palyginimą: . Palyginimų mažinimo taisyklės yra tokios.

Taip pat negalite atlikti palyginimų operacijų, jei jų moduliai nesutampa.

Kitos savybės:

Susiję apibrėžimai

Išskaičiavimo klasės

Visų skaičių, palyginamų su a modulo n paskambino atskaitymo klasė a modulo n , ir paprastai žymimas [ a] n arba . Taigi palyginimas yra lygiavertis likučių klasių lygybei [a] n = [b] n .

Nes modulo palyginimas n yra lygiavertiškumo santykis sveikųjų skaičių aibėje, tada liekanų klasės modulo n yra lygiavertiškumo klasės; jų skaičius yra n. Visų likučių klasių rinkinys modulo nžymimas arba .

Sudėjimo ir daugybos operacijos indukuoja atitinkamas aibės operacijas:

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

Šių operacijų atžvilgiu aibė yra baigtinis žiedas, o jei n paprastas galutinis laukas .

Išskaičiavimo sistemos

Likučių sistema leidžia atlikti aritmetines operacijas su baigtiniu skaičių rinkiniu, neperžengiant jo ribų. Pilna atskaitymų sistema modulo n yra bet koks n sveikųjų skaičių rinkinys, kuris yra nepalyginamas modulo n. Paprastai, kaip visa modulio likučių sistema, paimami mažiausi neneigiami likučiai

0,1,...,n − 1

arba absoliučiai mažiausios liekanos, susidedančios iš skaičių

,

esant nelyginiam n ir skaičiai

esant net n .

Palyginimo sprendimas

Pirmojo laipsnio palyginimai

Skaičių teorijoje, kriptografijoje ir kitose mokslo srityse dažnai iškyla problema ieškant sprendimų, kaip palyginti pirmąjį formos laipsnį:

Tokio palyginimo sprendimas prasideda gcd skaičiavimu (a, m) = d. Šiuo atveju galimi 2 atvejai:

• Jeigu b ne kartotinis d, tada palyginimas neturi sprendimų.
• Jeigu b daugkartinis d, tada palyginimas turi unikalų sprendimo modulį m / d, arba, kuris yra tas pats, d moduliniai sprendimai m. Šiuo atveju, sumažinus pradinį palyginimą d palyginimo rezultatai:

kur a 1 = a / d , b 1 = b / d ir m 1 = m / d yra sveikieji skaičiai ir a 1 ir m 1 yra koprime. Todėl skaičius a 1 galima apversti moduliu m 1 , tai yra rasti tokį skaičių c kad (kitaip tariant, ). Dabar sprendimas randamas gautą palyginimą padauginus iš c:

Praktinis vertės skaičiavimas c galima atlikti įvairiais būdais: naudojant Eulerio teoremą, Euklido algoritmą, tęstinių trupmenų teoriją (žr. algoritmą) ir tt Konkrečiai, Eulerio teorema leidžia parašyti reikšmę c kaip:

Pavyzdys

Palyginimui turime d= 2 , taigi modulo 22 palyginimas turi du sprendinius. Pakeiskime 26 skaičiumi 4, kuris yra panašus į modulo 22, ir panaikinkime visus 3 skaičius 2:

Kadangi 2 yra santykinai pirminis moduliui 11, kairę ir dešinę puses galime sumažinti 2. Dėl to gauname vieną sprendinį modulo 11: , kuris atitinka du sprendinius modulo 22: .

Antrojo laipsnio palyginimai

Antrojo laipsnio palyginimų sprendimas sumažinamas iki išsiaiškinimo, ar tam tikras skaičius yra kvadratinė liekana (naudojant kvadratinį abipusiškumo dėsnį), ir tada apskaičiuojama kvadratinė šaknis modulio tai.

Istorija

Kinų liekanos teorema, žinoma daugelį šimtmečių, teigia (šiuolaikine matematine kalba), kad liekanos žiedas yra kelių pirminių skaičių sandauga.

Turinys.

Įvadas

§ vienas. Modulo palyginimas

§2. Palyginimo savybės

1. Nuo modulio nepriklausomos palyginimo savybės
2. Konkrečios modulio palyginimo savybės

§3. Išskaitymo sistema

1. Pilna atskaitymų sistema
2. Sumažinta atskaitymų sistema

§ ketvirta. Eilerio teorema ir Fermat

1. Eulerio funkcija
2. Eilerio teorema ir Fermat

2 skyrius. Palyginimo su kintamuoju teorija

§ vienas. Pagrindinės sąvokos, susijusios su palyginimų sprendimu

1. Palyginimo šaknys
2. Palyginimų lygiavertiškumas
3. Wilsono teorema

§2. Pirmojo laipsnio ir jų sprendimų palyginimai

1. Atrankos metodas
2. Eulerio metodai
3. Euklido algoritmo metodas
4. Tęsinys trupmenos metodas

§3. 1-ojo laipsnio palyginimo su nežinomuoju sistemos

§ ketvirta. Aukštesnių jėgų palyginimų skirstymas

§5. Primityvios šaknys ir indeksai

1. Išskaitymo klasės tvarka
2. Primityviosios šaknys modulo prime
3. Indeksai modulo pirminis

3 skyrius Palyginimų teorijos taikymas

§ vienas. Dalyvavimo požymiai

§2. Aritmetinių operacijų rezultatų tikrinimas

§3. Paprastosios trupmenos keitimas į baigtinę

dešimtainė trupmena

Išvada

Literatūra

Įvadas

Mūsų gyvenime dažnai tenka susidurti su sveikaisiais skaičiais ir su jais susijusiomis užduotimis. Šiame darbe nagrinėju sveikųjų skaičių palyginimo teoriją.

Du sveikieji skaičiai, kurių skirtumas yra tam tikro natūraliojo skaičiaus kartotinis m vadinami palyginamuoju moduliu m.

Žodis „modulis“ kilęs iš lotyniško modulio, kuris rusų kalba reiškia „matas“, „vertė“.

Teiginys „a yra suderinamas su b modulo m“ paprastai rašomas kaip ab (mod m) ir vadinamas palyginimu.

Lyginimo apibrėžimas buvo suformuluotas K. Gausso knygoje „Aritmetiniai tyrimai“. Šis lotynų kalba parašytas kūrinys pradėtas spausdinti 1797 m., tačiau knyga išleista tik 1801 m., nes spausdinimo procesas tuo metu buvo itin sunkus ir ilgas. Pirmasis Gausso knygos skyrius vadinasi „Apie skaičių palyginimą apskritai“.

Palyginimus labai patogu naudoti tais atvejais, kai bet kokiame tyrime pakanka žinoti skaičius iki tam tikro skaičiaus kartotinių.

Pavyzdžiui, jei mus domina, kokiu skaitmeniu baigiasi sveikojo skaičiaus kubas, tada mums pakanka žinoti a tik iki 10 kartotinių ir galime naudoti palyginimus modulo 10.

Šio darbo tikslas – išnagrinėti palyginimų teoriją ir ištirti pagrindinius palyginimų su nežinomaisiais sprendimo būdus, taip pat ištirti palyginimų teorijos taikymą mokyklinėje matematikoje.

Darbą sudaro trys skyriai, kurių kiekvienas skirstomas į pastraipas, o pastraipos – į pastraipas.

Pirmame skyriuje nagrinėjami bendrieji palyginimų teorijos klausimai. Čia nagrinėjama modulinio palyginimo samprata, palyginimų savybės, visa ir redukuota likučių sistema, Eilerio funkcija, Eilerio ir Fermato teorema.

Antrasis skyrius skirtas palyginimų su nežinomybe teorijai. Nubrėžiamos pagrindinės sąvokos, susijusios su palyginimų sprendimu, aptariami pirmojo laipsnio palyginimų sprendimo būdai (atrankos metodas, Eilerio metodas, Euklido algoritmo metodas, tęstinių trupmenų metodas, naudojant indeksus), pirmojo laipsnio palyginimų sistemos. vienas nežinomas, aukštesnių laipsnių palyginimai ir pan.

Trečiame skyriuje pateikiami kai kurie skaičių teorijos pritaikymai mokyklinei matematikai. Nagrinėjami dalijimosi ženklai, veiksmų rezultatų patikrinimas, paprastųjų trupmenų konvertavimas į sistemines dešimtaines trupmenas.

Teorinės medžiagos pristatymą lydi daugybė pavyzdžių, atskleidžiančių įvestų sąvokų ir apibrėžimų esmę.

1 skyrius. Bendrieji palyginimų teorijos klausimai

§ vienas. Modulo palyginimas

Tegul sveikųjų skaičių z žiedas, m fiksuotas sveikasis skaičius ir m z aibė visų sveikųjų skaičių, dalijamų iš m.

1 apibrėžimas. Sakoma, kad du sveikieji skaičiai a ir b yra vienodi modulio m, jei m dalija a-b.

Jei skaičiai a ir b yra palyginami modulio m, tada parašykite a b (modas m).

Būklė a b (mod m) reiškia, kad a-b dalijasi iš m.

a b (mod m)↔(a-b) m

Apibrėžiame, kad palyginamumo modulo m santykis sutampa su palyginamumo modulo (-m) ryšiu (dalumas iš m yra lygiavertis dalumui iš –m). Todėl neprarandant bendrumo galime daryti prielaidą, kad m>0.

Pavyzdžiai.

Teorema. (dvasinių skaičių palyginamumo ženklas modulo m): Du sveikieji skaičiai a ir b yra palyginami modulo m tada ir tik tada, kai a ir b liekana yra tokia pati, padalijus iš m.

Įrodymas.

Tegul liekanos dalijant a ir b iš m yra lygios, tai yra, a=mq₁+r,(1)

B=mq₂+r, (2)

Kur 0≤r≥m.

Iš (1) atėmus (2) gauname a-b= m(q1- q₂), t.y. a-b m arba a b (mod m).

Ir atvirkščiai, tegul a b (modas m). Tai reiškia a-b m arba a-b = mt, t z (3)

B padalinti iš m; (3) gausime b=mq+r, turėsime a=m(q+t)+r, tai yra a dalijant iš m gaunama tokia pati liekana, kaip ir dalijant b iš m.

Pavyzdžiai.

5=4 (-2)+3

23=4 5+3

24=3 8+0

10=3 3+1

2 apibrėžimas. Du ar daugiau skaičių, kurie, padalijus iš m, suteikia tą pačią liekaną, vadinami vienodais arba palyginamaisiais modulio m.

Pavyzdžiai.

Turime: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², o (- m²) dalijasi iš m => mūsų palyginimas teisingas.

1. Įrodykite, kad šie palyginimai yra klaidingi:

Jei skaičiai yra palyginami modulo m, tada jie turi tą patį gcd su juo.

Turime: 4 = 2 2, 10 = 2 5, 25 = 5 5

gcd(4,10) = 2, gcd(25,10) = 5, todėl mūsų palyginimas neteisingas.

§2. Palyginimo savybės

1. Nuo modulio nepriklausomos palyginimo savybės.

Daugelis palyginimo savybių yra panašios į lygybių savybes.

a) refleksyvumas: aa (mod m) (bet koks sveikasis skaičius a yra panašus į save modulo m);

C) simetrija: jei a b (mod m), tada b a (mod m);

C) tranzityvumas: jei a b (mod m) ir b su (mod m), tada a su (mod m).

Įrodymas.

Pagal sąlygą m/(a-b) ir m/ (c-d). Todėl m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b + d (mod m).

Pavyzdžiai.

Dalindami raskite likutį 13 val.

Sprendimas: -1 (mod 13) ir 1 (mod 13), tada (-1)+1 0 (mod 13), tai yra likusi dalis iki 13 yra 0.

a-c b-d (mod m).

Įrodymas.

Pagal sąlygą m/(a-b) ir m/(c-d). Todėl m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (1, 2, 3 savybių pasekmė). Prie abiejų palyginimo dalių galite pridėti tą patį sveikąjį skaičių.

Įrodymas.

Tegul a b (mod m) ir k yra bet koks sveikasis skaičius. Pagal refleksyvumo savybę

k=k (mod m), o pagal savybes 2 ir 3 turime a+k b + k (mod m).

a c d (mod m).

Įrodymas.

Pagal sąlygą a-b є mz, c-d є mz. Taigi a c-b d = (a c - b c)+(b c- b d)=(a-b) c+b (c-d) є mz, t.y. a c d (mod m).

Pasekmė. Abi palyginimo dalys gali būti padidintos iki vienodo sveikojo skaičiaus neneigiamos galios: jei ab (mod m) ir s yra neneigiamas sveikasis skaičius, tada a s b s (mod m).

Pavyzdžiai.

Sprendimas: akivaizdžiai 13 1 (mod 3)

2-1 (3 mod.)

5 -1 (3 mod.), tada

– 1–1 0 (13 mod.)

Atsakymas: norima liekana lygi nuliui, o A dalijasi iš 3.

Sprendimas:

Įrodykime, kad 1+ 0 (mod13) arba 1+ 0 (mod 13)

1+ =1+ 1+ =

Kadangi 27 yra 1 (mod 13), tai reiškia, kad 1+ 1+1 3+1 9 (mod 13).

h.t.d.

3. Raskite likutį dalindami su likusia skaičiaus dalimi 24 val.

Turime: 1 (mod. 24), taigi

1 (24 mod.)

Prie abiejų palyginimo dalių pridėjus 55, gauname:

(24 mod.).

Mes turime: (mod 24), taigi

(mod. 24) bet kuriam k є N.

Vadinasi (24 mod.). Nuo (-8)16 (mod. 24), norima likusi dalis yra 16.

1. Abi palyginimo dalys gali būti padaugintos iš to paties sveikojo skaičiaus.

2.Palyginimo savybės priklausomai nuo modulio.

Įrodymas.

Kadangi a b (mod t), tada (a - b) t. Ir kadangi t n , tada dėl dalijamumo santykio tranzityvumo(a - b n) , tai yra a b (mod n).

Pavyzdys.

Raskite likutį padalijus 196 iš 7.

Sprendimas:

Žinant, kad 196= , galime parašyti 196(14 mod.). Pasinaudokime ankstesne savybe, 14 7, gauname 196 (7 mod.), tai yra 196 7.

1. Abi palyginimo dalis ir modulį galima padauginti iš to paties teigiamo sveikojo skaičiaus.

Įrodymas.

Tegu a b (mod m ) ir c yra teigiamas sveikasis skaičius. Tada a-b = mt ir ac-bc = mtc arba ac bc (mod mc).

Pavyzdys.

Patikrinkite, ar išraiškos reikšmė yra visas skaičius.

Sprendimas:

Pavaizduokime trupmenas palyginimų forma: 4(3 mod.)

1 (9 mod.)

31 (27 mod.)

Sudedame šiuos palyginimus pagal terminą (2 savybė), gauname 124(mod. 27) Matome, kad 124 nėra sveikasis skaičius, dalinamas iš 27, taigi ir išraiškos reikšmėtaip pat nėra sveikasis skaičius.

1. Abi palyginimo dalys gali būti padalytos pagal jų bendrą koeficientą, jei jis yra santykinai aukščiausias modulio atžvilgiu.

Įrodymas.

Jei ca cb (mod m), ty m/c(a-b) ir skaičius Su koprime į m, (c,m)=1, tada m dalijasi a-b. Vadinasi, a b (mod t ).

Pavyzdys.

60 9 (mod. 17), padalijus abi palyginimo dalis iš 3 gauname:

20 (mod. 17).

Paprastai tariant, neįmanoma padalyti abiejų palyginimo dalių iš skaičiaus, kuris nesutampa su moduliu, nes padalijus galima gauti skaičius, kurie šiame modulyje yra nepalyginami.

Pavyzdys.

8 (mod. 4), bet 2 (mod. 4).

1. Abi palyginimo dalis ir modulį galima padalyti pagal jų bendrą daliklį.

Įrodymas.

Jei ka kb (mod km), tada k (a-b) dalijasi iš km. Todėl a-b dalijasi iš m, tai yra a b (mod t ).

Įrodymas.

Tegu P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n . Pagal sąlygą a b (mod t), tada

a k b k (mod m), kai k = 0, 1, 2, …,n. Padauginus abi kiekvieno gauto n + 1 palyginimo dalis iš c n-k , gauname:

c n-k a k c n-k b k (mod m), kur k = 0, 1, 2, …,n.

Sudėjus paskutinius palyginimus, gauname: P (a) P(b) (mod m). Jei a (mod m) ir c i d i (mod m), 0 ≤ i ≤ n, tada

(mod. m). Taigi, esant kongruencijai modulo m, atskirus terminus ir veiksnius galima pakeisti skaičiais kongruentais modulo m.

Kartu reikia atkreipti dėmesį į tai, kad lygindami sutinkami rodikliai negali būti pakeisti tokiu būdu: nuo

a n c(mod m) ir n k(mod m) nereiškia, kad a k su (mod m).

11 nuosavybė turi daug svarbių programų. Visų pirma, jis gali būti naudojamas teoriniam dalijimosi ženklų pagrindimui. Iliustracijai, kaip pavyzdį, pateiksime dalijimosi iš 3 testo išvedimą.

Pavyzdys.

Bet kuris natūralusis skaičius N gali būti pavaizduotas kaip sisteminis skaičius: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

Apsvarstykite daugianarį f (x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Nes

10 1 (mod. 3), tada pagal ypatybę 10 f (10) f(1) (modas 3) arba

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a n (mod 3), t.y., kad N dalytųsi iš 3, būtina ir pakanka, kad šio skaičiaus skaitmenų suma dalytųsi iš 3.

§3. Išskaičiavimo sistemos

1. Pilna atsiskaitymo sistema.

Lygiaverčiai skaičiai arba, kas yra tas pats, palyginamieji modulo m sudaro skaičių klasę modulo m.

Iš šio apibrėžimo išplaukia, kad ta pati liekana r atitinka visus klasės skaičius, ir gausime visus klasės skaičius, jei priversime q eiti per visus sveikuosius skaičius forma mq + r.

Atitinkamai, su m skirtingomis r reikšmėmis, turime m skaičių klasių modulo m.

Bet koks klasės skaičius vadinamas likučiu modulo m visų tos pačios klasės skaičių atžvilgiu. Lieka, gauta esant q=0, lygi likusiai r daliai, vadinama mažiausia neneigiama liekana.

Likutis ρ, mažiausia pagal absoliučią vertę, vadinama absoliučiai mažiausia likučiais.

Akivaizdu, kad r turime ρ=r; kai r> turime ρ=r-m; galiausiai, jei m lygus ir r=, tada ρ galima imti bet kurį iš dviejų skaičių ir -m= - .

Mes pasirenkame iš kiekvienos likučių klasės modulo t vienu numeriu. Gauk m sveikieji skaičiai: x 1 ,…, x m . Iškviečiama aibė (x 1, ..., x t). pilna likučių sistema modulo m.

Kadangi kiekvienoje klasėje yra nesuskaičiuojamas likučių rinkinys, galima sudaryti nesuskaičiuojamą skirtingų modulio m likučių sistemų rinkinį, kurių kiekvienoje yra t atskaitymai.

Pavyzdys.

Sudarykite kelias pilnas likučių modulio sistemas t = 5. Turime klases: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Padarykime kelias pilnas išskaičiavimų sistemas, paimdami po vieną išskaičiavimą iš kiekvienos klasės:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

ir tt

Dažniausiai naudojamas:

1. Visa mažiausių neneigiamų likučių sistema: 0, 1, t -1 Aukščiau pateiktame pavyzdyje: 0, 1, 2, 3, 4. Tokia likučių sistema paprasta: reikia užrašyti visas neneigiamas liekanas, gautas padalijus iš m.
2. Visiška mažiausiai teigiamų likučių sistema(iš kiekvienos klasės imamas mažiausias teigiamas atskaitymas):

1, 2, …, m. Mūsų pavyzdyje: 1, 2, 3, 4, 5.

1. Pilna sistema, kurioje yra visiškai mažiausiai likučių.Nelyginio m atveju absoliučiai mažiausios liekanos atsiranda greta.

- ,…, -1, 0, 1,…, ,

o lyginio m atveju – viena iš dviejų eilučių

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

Pateiktame pavyzdyje: -2, -1, 0, 1, 2.

Dabar panagrinėkime pagrindines visos likučių sistemos savybes.

1 teorema . Bet koks sveikųjų m skaičių rinkinys:

x l ,x 2 ,…,х m (1)

poromis nepalyginamas modulo m, sudaro pilną likučių sistemą modulo m.

Įrodymas.

1. Kiekvienas aibėje (1) esantis skaičius priklauso kokiai nors klasei.
2. Bet kurie du skaičiai x i ir x j iš (1) yra nepalyginami vienas su kitu, t. y. priklauso skirtingoms klasėms.
3. Iš viso (1) yra m skaičių, t.y. tiek, kiek yra modulo klasių t.

x 1, x 2,…, x t yra visa modulo m likučių sistema.

2 teorema. Tegul (a, m) = 1, b - savavališkas sveikasis skaičius; tada jei x 1, x 2,…, x t -visa likučių sistema modulo m, tada skaičių rinkinys ax 1 + b, ax 2 + b,…, ax m + b taip pat yra visa modulo m likučių sistema.

Įrodymas.

Apsvarstykite

Ax 1 + b, ax 2 + b, ..., ax m + b (2)

1. Kiekvienas aibėje (2) esantis skaičius priklauso kokiai nors klasei.
2. Bet kurie du skaičiai ax i +b ir ax j + b iš (2) yra nepalyginami vienas su kitu, tai yra, jie priklauso skirtingoms klasėms.

Iš tiesų, jei (2) būtų du skaičiai, tokie

ax i + b ax j + b (mod m), (i = j), tada gautume ax i ax j (mod m). Nuo (a, t) = 1, tada palyginimų savybė gali sumažinti abi palyginimo dalis a . Gauname x i x j (mod m).

Pagal sąlygą x i x j (mod m) už (i = j) , nes x 1, x 2, ..., x m - pilna atskaitymų sistema.

1. Skaičių aibėje (2) yra t skaičių, tai yra tiek, kiek yra klasių modulo m.

Taigi, ax 1 + b, ax 2 + b, ..., ax m + b yra visa modulo m likučių sistema.

Pavyzdys.

Tegul m = 10, a = 3, b = 4.

Paimkime visą 10 modulio likučių sistemą, pavyzdžiui: 0, 1, 2, ..., 9. Sudarykime formos skaičius kirvis + b. Gauname: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Gautas skaičių rinkinys yra visa modulo 10 likučių sistema.

1. Pateikta atskaitymų sistema.

Įrodykime tokią teoremą.

1 teorema.

Tos pačios liekanų klasės modulo m skaičiai turi tą patį didžiausią bendrą daliklį su m: jei a b (mod m), tada (a, m) = (b, m).

Įrodymas.

Tegu a b (mod m). Tada a = b + mt, kur t z. Iš šios lygybės išplaukia, kad (a, m) = (b, m).

Iš tiesų, tegul yra δ bendras a ir m daliklis, tada aδ, m δ. Kadangi a = b + mt, tada b=a-mt, taigi bδ. Todėl bet kuris bendras a ir m daliklis yra bendras m ir b daliklis.

Ir atvirkščiai, jei m δ ir b δ, tai a = b + mt dalijasi iš δ, todėl bet kuris bendras m ir b daliklis yra bendras a ir m daliklis. Teorema įrodyta.

1 apibrėžimas. Didžiausias bendras modulio daliklis t ir bet koks skaičius a iš šios klasės atskaitymų už t vadinamas didžiausiu bendruoju dalikliu t ir šios klasės liekanų.

2 apibrėžimas. Likučių klasė a modulo m vadinamas koprime su moduliu m jei didžiausias bendras daliklis a ir t lygus 1 (tai yra, jei m ir bet kuris skaičius iš a yra koprime).

Pavyzdys.

Tegul t = 6. 2 likučių klasė susideda iš skaičių (..., -10, -4, 2, 8, 14, ...). Didžiausias bet kurio iš šių skaičių ir 6 modulio bendras daliklis yra 2. Vadinasi, (2, 6) = 2. Didžiausias bet kurio skaičiaus iš 5 klasės ir 6 modulio bendras daliklis yra 1. Vadinasi, 5 klasė yra santykinai pirminis moduliui. 6.

Iš kiekvienos likučių klasės parinksime koprimą su modulo m vienu skaičiumi. Gauname atskaitymų sistemą, kuri yra visos atskaitymų sistemos dalis. Jie jai skambinasumažinta likučių sistema modulo m.

3 apibrėžimas. Likučių rinkinys modulo m, paimtas po vieną iš kiekvieno koprime su t likučių klasė modulo šis modulis vadinamas sumažintų likučių sistema.

3 apibrėžimas reiškia metodą, kaip gauti sumažintą likučių modulio sistemą t: reikia išrašyti kažkokią pilną likučių sistemą ir iš jos pašalinti visas liekanas, kurios nėra koprime su m. Likęs atskaitymų rinkinys yra sumažinta atskaitymų sistema. Akivaizdu, kad yra begalinis skaičius redukuotų likučių modulo m sistemų.

Jei imsime pilną mažiausiai neneigiamų arba absoliučiai mažiausiai likučių sistemą kaip pradinę, tai nurodytu būdu gausime atitinkamai sumažintą mažiausiai neneigiamų arba absoliučiai mažiausiai likučių sistemą modulo m.

Pavyzdys.

Jeigu T = 8, tada 1, 3, 5, 7 - sumažinta mažiausiai neneigiamų likučių sistema, 1, 3, -3, -1- sumažinta visiškai mažiausiai likučių sistema.

2 teorema.

Leisti klasių, santykinai pirminių su m, skaičius lygus k.Tada bet koks k sveikųjų skaičių rinkinys

poromis nepalyginamas modulo m ir santykinai pirminis iki m, yra redukuota likučių sistema modulo m.

Įrodymas

A) Kiekvienas skaičius aibėje (1) priklauso kokiai nors klasei.

1. Visi skaičiai iš (1) yra nepalyginami poromis modulio t, tai yra, jie priklauso skirtingoms modulo m klasėms.
2. Kiekvienas skaičius iš (1) yra bendras su t, tai yra, visi šie skaičiai priklauso skirtingoms klasėms coprime su modulo m.
3. Iš viso (1) turi k skaičių, tai yra tiek, kiek turėtų būti sumažintoje likučių sistemoje modulo m.

Todėl skaičių aibė(1) - sumažinta likučių modulo sistema t.

§ ketvirta. Eulerio funkcija.

Eilerio ir Ferma teoremos.

1. Eulerio funkcija.

Pažymėkite φ(t) likučių klasių skaičius modulo m coprime su m, tai yra redukuotos likučių sistemos elementų skaičius modulo t. Funkcija φ (t) yra skaitinis. Jie jai skambinaEulerio funkcija.

Mes pasirenkame likučių klasių atstovus modulo t skaičiai 1, ... , t - 1, t. Tada φ (t) yra tokių skaičių koprime su t. Kitaip tariant, φ (t) - teigiamų skaičių, neviršijančių m ir santykinai pirminių iki m.

Pavyzdžiai.

1. Tegul t = 9. Visą likučių modulo 9 sistemą sudaro skaičiai 1, 2, 3, 4, 5, 6, 7, 8, 9. Iš jų skaičiai 1,2,4, 5, 7, 8 yra pirminiai skaičiai iš 9. Taigi kadangi šių skaičių skaičius yra 6, tai φ (9) = 6.
2. Tegu t = 12. Visą likučių sistemą sudaro skaičiai 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Iš jų skaičiai 1, 5, 7, 11 yra pirminiai skaičiai iš 12. Taigi,

φ(12) = 4.

Prie t = 1, visa likučių sistema susideda iš vienos klasės 1. Skaičių 1 ir 1 bendras natūralusis daliklis yra 1, (1, 1) = 1. Tuo remdamiesi dedame φ(1) = 1.

Pereikime prie Eulerio funkcijos skaičiavimo.

1) Jei m = p yra pirminis skaičius, tada φ(p) = p-1.

Įrodymas.

Likučiai 1, 2, ... , p- 1 ir tik jie yra kopirminiai su pirminiu skaičiumi R. Todėl φ (p) = p - 1.

2) Jei m = p k - pirminio skaičiaus laipsnis p, tada

φ(t) = (p - 1) . (vienas)

Įrodymas.

Pilna likučių modulo sistema t = p k susideda iš skaičių 1,..., p k - 1, p k natūralūs dalikliai t yra laipsniai R. Todėl skaičius agali turėti bendrą daliklį su m, išskyrus 1, tik tada, kaiapadalytąR.Tačiau tarp skaičių 1, ... , pk -1 antRdalijant tik skaičiusp, 2p, ... , p2 , ... Rį, kurių skaičius yraRį: p = pk-1. Vadinasi, koprime sut = pįpoilsisRį– Rk-1=pkl(p-1)numeriai. Taigi įrodyta, kad

φ (Rį) = pk-1(r-1).

Teorema1.

Eulerio funkcija yra dauginamoji, tai yra kopirminiams skaičiams m ir n turime φ (mn) = φ(m) φ (n).

Įrodymas.

Pirmasis dauginamosios funkcijos apibrėžimo reikalavimas įvykdytas trivialiai: Eulerio funkcija apibrėžiama visiems natūraliems skaičiams, o φ (1) = 1. Mums tereikia tai parodyti, jeitipassantykinai pirminiai skaičiai

φ (tp)= φ (t) φ (P).(2)

Sutvarkykite visą likučių sistemą modulotpkaipPXt -matricos

1 2 t

t+1 t+2 2t

………………………………

(P -1) t+1 (P -1) m +2 Penk

NestirPkoprime, tada skaičiusXabipusiai paprasta sutpJeigu, ir tik jeiguXabipusiai paprasta sutirXabipusiai paprasta suP. Bet skaičiuskm + tabipusiai paprasta sutJeigu, ir tik jeigutabipusiai paprasta sut.Todėl skaičiai, santykinai pirminiai iki m, yra tuose stulpeliuose, kuriemsteina per sumažintą likučių sistemą modulot.Tokių stulpelių skaičius yra φ(t).Kiekviename stulpelyje pateikiama visa modulio likučių sistemaP.Iš šių likučių φ(P)koprime suP.Vadinasi, bendras skaičių koprime ir suto su n lygus φ(t)φ(n)

(φ (t)stulpeliai, kurių kiekvienas užima φ(P)skaičiai). Šie skaičiai ir tik jie yra koprime suir ttTaigi įrodyta, kad

φ (tp)= φ (t) φ (P).

Pavyzdžiai.

№1 . Įrodykite šias lygybes

φ(4n) =

Įrodymas.

№2 . išspręsti lygtį

Sprendimas:nes(m) =, tada= , tai yra=600, =75, =3, tada x-1=1, x=2,

y-1 = 2, y = 3

Atsakymas: x=2, y=3

Galime apskaičiuoti Eulerio funkcijos reikšmę(m), žinant kanoninį skaičiaus m vaizdavimą:

m=.

Dėl daugikliom) mes turime:

(m) =.

Bet pagal formulę (1) gauname tai

-1), todėl

(3)

Lygybė (3) gali būti perrašyta taip:

Nes=m, tada(4)

Formulė (3) arba, kuri yra ta pati, (4) yra norima.

Pavyzdžiai.

№1 . Kokia suma

Sprendimas:,

, =18 (1- ) (1- =18 , tada= 1+1+2+2+6+6=18.

№2 . Remdamiesi Eulerio skaičių funkcijos savybėmis, įrodykite, kad natūraliųjų skaičių sekoje yra begalinė pirminių skaičių aibė.

Sprendimas:Išlyginus pirminių skaičių skaičių baigtine aibe, tarkimeyra didžiausias pirminis skaičius ir tegul a=yra visų pirminių skaičių sandauga, pagrįsta viena iš Eulerio skaičių funkcijos savybių

Kadangi a≥, tada a yra sudėtinis skaičius, bet kadangi jo kanoniniame vaizde yra visi pirminiai skaičiai, tada=1. Mes turime:

=1 ,

o tai neįmanoma, todėl įrodoma, kad pirminių skaičių aibė yra begalinė.

№3 .Išspręskite lygtį, kur x=ir=2.

Sprendimas:Mes naudojame Eulerio skaitinės funkcijos savybę,

,

ir pagal sąlygą=2.

Ekspresas iš=2 , mes gauname, pakeisime

:

(1+ -1=120, =11 =>

Tada x =, x=11 13=143.

Atsakymas:x = 143

2. Eilerio teorema ir Fermat.

Palyginimų teorijoje svarbų vaidmenį vaidina Eilerio teorema.

Eilerio teorema.

Jei sveikasis skaičius a yra santykinai pirminis m, tada

(1)

Įrodymas.Leisti

(2)

yra sumažinta likučių sistema modulo m.

Jeiguayra sveikasis skaičius, palyginti su m, tada

(3)

Apibrėžimas 1. Jei du skaičiai 1) a ir b dalijant iš p duoti tą patį likutį r, tada tokie skaičiai vadinami vienodais atstumais arba galima palyginti su moduliu p.

pareiškimas 1. Leisti p kažkoks teigiamas skaičius. Tada bet koks skaičius a visada ir, be to, unikaliu būdu gali būti pavaizduotas formoje

Bet šiuos skaičius galima gauti paklausus r lygus 0, 1, 2,..., p-1. Vadinasi sp+r=a paima visas įmanomas sveikųjų skaičių reikšmes.

Parodykime, kad šis vaizdas yra unikalus. Apsimeskime tai p gali būti pavaizduotas dviem būdais a=sp+r ir a=s 1 p+r vienas . Tada

(2)

Nes r 1 užima vieną iš skaičių 0,1, ..., p−1, tada absoliuti reikšmė r 1 −r mažiau p. Tačiau iš (2) išplaukia, kad r 1 −r daugkartinis p. Vadinasi r 1 =r ir s 1 =s.

Skaičius r paskambino minusas numeriai a modulo p(kitaip tariant, skaičius r vadinama skaičiaus dalybos liekana a ant p).

pareiškimas 2. Jei du skaičiai a ir b panašus modulis p, tada a-b padalytą p.

Tikrai. Jei du skaičiai a ir b panašus modulis p, tada padalijus iš p turi tą patį likutį p. Tada

padalytą p, nes (3) lygties dešinioji pusė yra padalinta iš p.

pareiškimas 3. Jei dviejų skaičių skirtumas dalijasi iš p, tada šie skaičiai yra palyginami modulo p.

Įrodymas. Pažymėti r ir r 1 likutis iš padalijimo a ir b ant p. Tada

Pavyzdžiai 25≡39 (7 mod.), –18≡14 (4 mod.).

Iš pirmojo pavyzdžio matyti, kad 25 padalijus iš 7, gaunama tokia pati liekana kaip ir 39. Iš tiesų, 25=3 7+4 (likęs 4). 39=3 7+4 (likęs 4). Nagrinėdami antrąjį pavyzdį, atminkite, kad likusi dalis turi būti neneigiamas skaičius, mažesnis už modulį (ty 4). Tada galime rašyti: −18=−5 4+2 (likutis 2), 14=3 4+2 (likutis 2). Todėl −18, padalijus iš 4, lieka 2, o 14, padalijus iš 4, lieka 2.

Modulo palyginimų savybės

Nuosavybė 1. Bet kam a ir p visada

lyginti ne visada būtina

kur λ yra didžiausias bendras skaičių daliklis m ir p.

Įrodymas. Leisti λ didžiausias bendras skaičių daliklis m ir p. Tada

Nes m(a-b) padalytą k, tada

Vadinasi

ir m yra vienas iš skaičiaus daliklių p, tada

kur h=pqs.

Atkreipkite dėmesį, kad galime leisti palyginimus neigiamuose moduliuose, t.y. palyginimas a≡b mod ( p) šiuo atveju reiškia skirtumą a-b padalytą p. Visos palyginimo savybės galioja neigiamiems moduliams.

Apsvarstykite formos palyginimą x 2 ≡a(mod pα), kur p yra paprastas nelyginis skaičius. Kaip parodyta 4 skyriaus 4 dalyje, šios sutapimo sprendimą galima rasti išsprendus kongruenciją x 2 ≡a(mod p). Ir palyginimas x 2 ≡a(mod pα) turės du sprendinius, jei a yra kvadratinės liekanos modulis p.

Pavyzdys:

Išspręskite kvadratinį palyginimą x 2 ≡86 (mod. 125).

125 = 5 3 , 5 yra pirminis skaičius. Patikrinkime, ar 86 yra kvadratinis modulis 5.

Pradiniame palyginime yra 2 sprendimai.

Raskime palyginimo sprendimą x 2 ≡86 (5 mod.).

x 2 ≡1 (mod. 5).

Šį palyginimą būtų galima išspręsti ankstesnėje pastraipoje nurodytu būdu, tačiau naudosime tai, kad 1 modulio kvadratinė šaknis yra ±1, o palyginimas turi lygiai du sprendinius. Taigi modulo 5 kongruencijos sprendimas yra

x≡±1 (5 mod.) arba, kitaip, x=±(1+5 t 1).

Pakeiskite gautą sprendimą palyginimo modulyje 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 (25 mod.)

2t 1 ≡2 (5 mod.)

t 1 ≡1 (mod. 5) arba lygiavertis, t 1 =1+5t 2 .

Tada modulo 25 kongruencijos sprendimas yra x=±(1+5(1+5 t 2))=±(6+25 t 2). Pakeiskite gautą sprendimą palyginimo modulyje 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 (125 mod.)

12t 2 ≡2 (5 mod.)

2t 2 ≡2 (5 mod.)

t 2 ≡1 (mod. 5), arba t 2 =1+5t 3 .

Tada palyginimo modulo 125 sprendimas yra x=±(6+25(1+5 t 3))=±(31+125 t 3).

Atsakymas: x≡±31 (mod. 125).

Dabar apsvarstykite formos palyginimą x 2 ≡a(mod2α). Toks palyginimas ne visada turi du sprendimus. Tokiam moduliui galimi šie atvejai:

1) α=1. Tada palyginimas turi sprendimą tik tada, kai a≡1(mod 2), o sprendimas yra x≡1 (mod 2) (vienas sprendimas).

2) α=2. Palyginimas turi sprendimus tik tada, kai a≡1(mod 4), o sprendimas yra x≡±1 (mod. 4) (du sprendimai).

3) α≥3. Palyginimas turi sprendimus tik tada, kai a≡1(mod 8), ir bus keturi tokie sprendimai. Palyginimas x 2 ≡a(mod 2 α) α≥3 išsprendžiama taip pat kaip formos palyginimai x 2 ≡a(mod pα), tik modulo 8 sprendimai veikia kaip pradinis sprendimas: x≡±1 (8 mod.) ir x≡±3 (8 mod.). Jie turėtų būti lyginami modulio 16, tada modulo 32 ir tt iki modulo 2 α.

Pavyzdys:

Išspręskite palyginimą x 2 ≡ 33 (mod. 64)

64=26. Patikrinkime, ar pirminis palyginimas turi sprendimą. 33≡1(mod 8), todėl palyginimas turi 4 sprendimus.

Modulo 8 šie sprendimai bus: x≡±1 (8 mod.) ir x≡±3 (mod. 8), kuris gali būti pavaizduotas kaip x=±(1+4 t vienas). Pakeiskite šią išraišką palyginimo modulyje 16

x 2 ≡ 33 (16 mod.)

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

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

8t 1 ≡0 (16 mod.)

t 1 ≡0 (2 mod.)

Tada sprendimas įgaus formą x=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Pakeiskite gautą sprendimą kongruence modulio 32:

x 2 ≡ 33 (32 mod.)

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

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

16t 2 ≡0 (32 mod.)

t 2 ≡0 (2 mod.)

Tada sprendimas įgaus formą x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Pakeiskite gautą sprendimą palyginimo modulyje 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 (64 mod.)

t 3 ≡1 (2 mod.)

Tada sprendimas įgaus formą x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t keturi). Taigi, modulo 64, pradinis palyginimas turi keturis sprendimus: x≡±17 (mod. 64) ir x≡±49 (64 mod.).

Dabar apsvarstykite bendrą palyginimą: x 2 ≡a(mod m), (a,m)=1, - kanoninis modulio išskaidymas m. Pagal §4 4 punkto teoremą šis palyginimas yra lygiavertis sistemai

Jei kiekvienas šios sistemos palyginimas yra sprendžiamas, tada visa sistema yra sprendžiama. Radę kiekvieno šios sistemos palyginimo sprendimą, gauname pirmojo laipsnio palyginimų sistemą, kurią išsprendę, pasitelkę kinų liekanos teoremą, gauname pirminio palyginimo sprendinį. Be to, skirtingų pradinio palyginimo sprendinių skaičius (jei jis yra išsprendžiamas) yra 2 k, jei α=1, 2 k+1, jei α = 2, 2 k+2, jei α≥3.

Pavyzdys:

Išspręskite palyginimą x 2 ≡4 (mod. 21).