Compararea numerelor modulo

Întocmit de: Irina Zutikova

MAOU "Liceul nr. 6"

Clasa: 10 "a"

Conducător științific: Zheltova Olga Nikolaevna

Tambov

2016

• Problemă
• Scopul proiectului
• Ipoteză
• Obiectivele proiectului și planul pentru atingerea acestora
• Comparații și proprietățile lor
• Exemple de probleme și soluțiile acestora
• Site-uri folosite și literatură

Problemă:

Majoritatea studenților folosesc rareori compararea modulo a numerelor pentru a rezolva sarcini nestandard și olimpiade.

Scopul proiectului:

Arată cum poți rezolva sarcini non-standard și olimpiade comparând numere modulo.

Ipoteză:

Un studiu mai profund al subiectului „Compararea numerelor modulo” îi va ajuta pe elevi să rezolve unele sarcini nestandard și olimpiade.

Obiectivele proiectului și planul de realizare a acestora:

1. Studiază în detaliu tema „Compararea numerelor modulo”.

2. Rezolvați mai multe sarcini nestandard și olimpiade utilizând compararea modulo a numerelor.

3. Creați o notă pentru studenți pe tema „Compararea numerelor modulo”.

4. Desfășurați o lecție pe tema „Compararea numerelor modulo” în clasa a 10-a „a”.

5. Dați-le clasei teme pe tema „Comparație după modul”.

6. Comparați timpul necesar pentru finalizarea sarcinii înainte și după studierea subiectului „Comparație după modul”.

7.Trageți concluzii.

Înainte de a începe să studiez în detaliu subiectul „Compararea numerelor modulo”, am decis să compar modul în care este prezentat în diverse manuale.

• Algebra și începuturile analizei matematice. Nivel avansat. Clasa a 10-a (Yu.M. Kolyagin și alții)
• Matematică: algebră, funcții, analiza datelor. Clasa a VII-a (L.G. Peterson și alții)
• Algebra și începuturile analizei matematice. Nivel de profil. Clasa a X-a (E.P. Nelin și alții)
• Algebra și începuturile analizei matematice. Nivel de profil. Clasa a X-a (G.K. Muravin și alții)

După cum am aflat, unele manuale nici nu ating acest subiect, în ciuda nivelului avansat. Și subiectul este prezentat în modul cel mai clar și accesibil în manualul de L.G Peterson (Capitolul: Introducere în teoria divizibilității), așa că să încercăm să înțelegem „Compararea numerelor modulo”, bazându-ne pe teoria din acest manual.

Comparații și proprietățile lor.

Definiţie: Dacă două numere întregi a și b au aceleași resturi atunci când sunt împărțite la un număr întreg m (m>0), atunci ele spun căa și b sunt comparabile modulo m, si scrie:

Teorema: dacă și numai dacă diferența dintre a și b este divizibilă cu m.

Proprietăți:

1. Reflexivitatea comparațiilor.Orice număr a este comparabil cu el însuși modulo m (m>0; a,m sunt numere întregi).
2. Comparații simetrice.Dacă numărul a este comparabil cu numărul b modulo m, atunci numărul b este comparabil cu numărul a modulo la fel (m>0; a,b,m sunt numere întregi).
3. Tranzitivitatea comparațiilor.Dacă numărul a este comparabil cu numărul b modulo m, iar numărul b este comparabil cu numărul c modulo același modulo, atunci numărul a este comparabil cu numărul c modulo m (m>0; a,b,c ,m sunt numere întregi).
4. Dacă numărul a este comparabil cu numărul b modulo m, atunci numărul a n comparabil după numărul b n modulo m(m>0; a,b,m-întregi; n-număr natural).

Exemple de probleme și soluțiile acestora.

1. Găsiți ultima cifră a numărului 3 999 .

Soluţie:

Deoarece Ultima cifră a numărului este restul atunci când se împarte la 10

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

(Deoarece 34=81 1(mod 10);81 n 1(mod10) (după proprietate))

Raspuns: 7.

2.Demonstrați că 2 4n -1 este divizibil cu 15 fără rest. (Phystech2012)

Soluţie:

Deoarece 16 1(mod 15), atunci

16n-1 0(mod 15) (după proprietate); 16n= (2 4) n

2 4n -1 0 (mod 15)

3.Demonstrați că 12 2n+1 +11 n+2 Divizibil cu 133 fără rest.

Soluţie:

12 2n+1 =12*144 n 12*11 n (modul 133) (după proprietate)

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

Numărul (11n *133) se împarte la 133 fără rest, prin urmare, (12 2n+1 +11 n+2 ) este divizibil cu 133 fără rest.

4. Aflați restul numărului 2 împărțit la 15 2015 .

Soluţie:

Din 16 1(mod 15), atunci

2 2015 8 (modul 15)

Răspuns: 8.

5.Găsiți restul împărțirii după al 17-lea număr 2 2015. (Phystech2015)

Soluţie:

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

Din 16 -1(mod 17), atunci

2 2015 -8 (mod 15)

8 9 (modul 17)

Răspuns: 9.

6.Demonstrați că numărul este 11 100 -1 este divizibil cu 100 fără rest. (Phystech2015)

Soluţie:

11 100 =121 50

121 50 21 50 (mod 100) (după proprietate)

21 50 =441 25

441 25 41 25 (mod 100) (după proprietate)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (după proprietate)

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

361 6 (-39) 6 (mod 100)(după proprietate)

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

1521 3 21 3 (mod100) (după proprietate)

41*21 3 =41*21*441

441 41(mod 100) (după proprietate)

21*41 2 =21*1681

1681 -19(mod 100) (după proprietate)

21*(-19)=-399

399 1(mod 100) (după proprietate)

Deci 11 100 1 (mod 100)

11 100 -1 0(mod 100) (după proprietate)

7. Se dau trei numere: 1771,1935,2222. Găsiți un număr astfel încât, atunci când este împărțit la el, resturile celor trei numere date să fie egale. (HSE2016)

Soluţie:

Atunci numărul necunoscut să fie egal cu a

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

2222-1935 0(moda) (după proprietate); 1935-17710(moda) (după proprietate); 2222-17710(moda) (după proprietate)

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

287-164 0(moda) (după proprietate); 451-2870(moda)(după proprietate)

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

164-123 0(mod a) (după proprietate)

41

Olimpiada HSE 2016

La n dau aceleași resturi.

Formulări echivalente: a și b comparabil ca modul n dacă diferenţa lor o - b este divizibil cu n, sau dacă a poate fi reprezentat ca o = b + kn , Unde k- un număr întreg. De exemplu: 32 și −10 sunt comparabile modulo 7, deoarece

Declarația „a și b sunt comparabile modulo n” se scrie astfel:

Proprietăți de egalitate de modul

Relația de comparație modulo are proprietăți

Oricare două numere întregi oŞi b comparabil modulo 1.

În ordinea numerelor oŞi b au fost comparabile ca modul n, este necesar și suficient ca diferența lor să fie divizibilă cu n.

Dacă numerele și sunt comparabile în perechi în modul n, apoi sumele și , precum și produsele și sunt, de asemenea, comparabile în modul n.

Dacă numerele oŞi b comparabil ca modul n, apoi gradele lor o kŞi b k sunt, de asemenea, comparabile ca modul n sub orice firesc k.

Dacă numerele oŞi b comparabil ca modul n, Și nîmpărțit la m, Asta oŞi b comparabil ca modul m.

În ordinea numerelor oŞi b au fost comparabile ca modul n, prezentat sub forma descompunerii sale canonice în factori simpli p i

necesar si suficient pentru a

Relația de comparație este o relație de echivalență și are multe dintre proprietățile egalităților obișnuite. De exemplu, acestea pot fi adunate și înmulțite: dacă

Comparațiile nu pot fi însă împărțite, în general, între ele sau cu alte numere. Exemplu: , totuși, reducând cu 2, obținem o comparație eronată: . Regulile de abreviere pentru comparații sunt următoarele.

De asemenea, nu puteți efectua operații asupra comparațiilor dacă modulele lor nu se potrivesc.

Alte proprietăți:

Definiții înrudite

Clase de deducere

Mulțimea tuturor numerelor comparabile cu o modulo n numit clasa deducerii o modulo n , și este de obicei notat [ o] n sau . Astfel, comparația este echivalentă cu egalitatea claselor de reziduuri [o] n = [b] n .

Din moment ce compararea modulo n este o relație de echivalență pe mulțimea numerelor întregi, apoi clasele de reziduuri modulo n reprezintă clase de echivalență; numărul lor este egal n. Mulțimea tuturor claselor de reziduuri modulo n notat cu sau.

Operațiile de adunare și înmulțire prin induc operații corespunzătoare pe mulțime:

[o] n + [b] n = [o + b] n

În ceea ce privește aceste operații, mulțimea este un inel finit, iar dacă n simplu - câmp finit.

Sisteme de deducere

Sistemul de reziduuri vă permite să efectuați operații aritmetice pe un set finit de numere fără a depăși limitele acestuia. Sistem complet de deduceri modulo n este orice set de n numere întregi care sunt incomparabile modulo n. De obicei, cele mai mici reziduuri nenegative sunt luate ca un sistem complet de reziduuri modulo n

0,1,...,n − 1

sau cele mai mici deduceri absolute constând din numere

,

în caz de impar n si numere

în caz de chiar n .

Rezolvarea comparațiilor

Comparații de gradul I

În teoria numerelor, criptografie și în alte domenii ale științei, se pune adesea problema găsirii de soluții la comparațiile de gradul întâi ale formei:

Rezolvarea unei astfel de comparații începe cu calcularea mcd-ului (a, m)=d. În acest caz, sunt posibile 2 cazuri:

• Dacă b nu un multiplu d, atunci comparația nu are soluții.
• Dacă b multiplu d, atunci comparația are o soluție unică modulo m / d, sau, ce este la fel, d soluții modulo m. În acest caz, ca urmare a reducerii comparației inițiale cu d comparatia este:

Unde o 1 = o / d , b 1 = b / d Şi m 1 = m / d sunt numere întregi și o 1 și m 1 sunt relativ prime. Prin urmare, numărul o 1 poate fi inversat modulo m 1, adică găsiți un astfel de număr c, că (cu alte cuvinte, ). Acum soluția se găsește înmulțind comparația rezultată cu c:

Calculul practic al valorii c poate fi implementat în diferite moduri: folosind teorema lui Euler, algoritmul lui Euclid, teoria fracțiilor continue (vezi algoritmul), etc. În special, teorema lui Euler vă permite să scrieți valoarea c sub forma:

Exemplu

Pentru comparație avem d= 2, deci modulo 22 comparația are două soluții. Să înlocuim 26 cu 4, comparabil cu el modulo 22, și apoi să reducem toate cele 3 numere cu 2:

Deoarece 2 este coprim la modulo 11, putem reduce laturile stânga și dreapta cu 2. Ca rezultat, obținem o soluție modulo 11: , echivalentă cu două soluții modulo 22: .

Comparații de gradul doi

Rezolvarea comparațiilor de gradul doi se reduce la a afla dacă un număr dat este un reziduu pătratic (folosind legea reciprocității pătratice) și apoi la calcularea rădăcinii pătrate modulo.

Poveste

Teorema chineză a restului, cunoscută de multe secole, afirmă (în limbajul matematic modern) că inelul de reziduuri modulo produsul mai multor numere coprime este

O comparație de gradul întâi cu o necunoscută are forma:

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

Rezolvați comparația- înseamnă găsirea tuturor valorilor lui x care îl satisfac. Se numesc două comparații care satisfac aceleași valori ale lui x echivalent.

Dacă comparația (1) este satisfăcută de oricare x = x 1, apoi (conform 49) toate numerele comparabile cu x 1, modulo m: x x 1 (mod m). Această întreagă clasă de numere este considerată a fi o singura solutie. Cu un astfel de acord se poate trage următoarea concluzie.

66.C aliniere (1) va avea tot atâtea soluţii cât numărul de reziduuri ale sistemului complet care îl satisfac.

Exemplu. Comparaţie

6x– 4 0 (mod 8)

Dintre numerele 0, 1,2, 3, 4, 5, 6, 7, două numere satisfac sistemul complet de reziduuri modulo 8: X= 2 și X= 6. Prin urmare, această comparație are două soluții:

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

Comparația gradului I prin mutarea termenului liber (cu semnul opus) în partea dreaptă poate fi redusă la forma

topor b(mod m). (2)

Luați în considerare o comparație care îndeplinește condiția ( O, m) = 1.

Conform 66, comparația noastră are atâtea soluții câte reziduuri din sistemul complet o satisfac. Dar când x parcurge sistemul complet de resturi modulo T, Că Oh parcurge sistemul complet de deduceri (din 60). Prin urmare, pentru o singură valoare X, luate din sistemul complet, Oh va fi comparabil cu b. Aşa,

67. Când (a, m) = 1 ax de comparație b(mod m)are o singura solutie.

Lasă acum ( o, m) = d> 1. Atunci, pentru ca comparația (2) să aibă soluții, este necesar (din 55) ca bîmpărțit la d, altfel compararea (2) este imposibilă pentru orice număr întreg x . Presupunând deci b multipli d, hai sa punem o = o 1 d, b = b 1 d, m = m 1 d. Atunci comparația (2) va fi echivalentă cu aceasta (abreviată cu d): o 1 x b 1 (mod m), în care deja ( O 1 , m 1) = 1, și prin urmare va avea o soluție modulo m 1. Lasă X 1 – cel mai mic reziduu nenegativ al acestei soluții modulo m 1 , atunci toate numerele sunt x , formând această soluţie se găsesc sub formă

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

Modulul m, numerele (3) nu formează o soluție, ci mai multe, exact atâtea soluții câte numere (3) sunt în seria 0, 1, 2, ..., m – 1 cel puțin resturile modulo nenegative m. Dar următoarele numere (3) vor cădea aici:

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

aceste. total d numere (3); prin urmare comparația (2) are d decizii.

Obtinem teorema:

68. Fie (a, m) = d. Axa de comparație b ( mod m) este imposibil dacă b nu este divizibil cu d. Când b este un multiplu al lui d, comparația are d soluții.

69. O metodă de rezolvare a comparațiilor de gradul I, bazată pe teoria fracțiilor continue:

Extinderea într-o fracție continuă a relației m:a,

și uitându-ne la ultimele două fracții potrivite:

conform proprietăților fracțiilor continuate (conform 30 ) avem

Deci comparația are o soluție

a găsi, ceea ce este suficient pentru a calcula Pn– 1 conform metodei specificate la 30.

Exemplu. Să rezolvăm comparația

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

Aici (111, 321) = 3, iar 75 este un multiplu al lui 3. Prin urmare, comparația are trei soluții.

Împărțind ambele părți ale comparației și modulul la 3, obținem comparația

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

pe care trebuie mai întâi să le rezolvăm. Avem

q
P 3

Deci, în acest caz n = 4, P n – 1 = 26, b= 25 și avem o soluție la comparația (5) sub forma

x–26 ∙ 25 99 (mod 107).

Prin urmare, soluțiile pentru comparația (4) sunt prezentate după cum urmează:

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

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

Calculul elementului invers printr-un modulo dat

70.Dacă numerele sunt numere întregi oŞi n sunt coprime, atunci există un număr o', satisfacand comparatia a ∙ a′ ≡ 1 (mod n). Număr o' numit inversul multiplicativ al unui modulo n iar notația folosită pentru aceasta este o- 1 (mod n).

Calculul mărimilor reciproce modulo o anumită valoare poate fi realizat prin rezolvarea unei comparații a gradului I cu una necunoscută, în care x număr acceptat o'.

Pentru a găsi o soluție de comparație

a∙x≡ 1(mod m),

Unde ( a.m)= 1,

puteți folosi algoritmul Euclid (69) sau teorema Fermat-Euler, care afirmă că dacă ( a.m) = 1, atunci

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

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

Grupuri și proprietățile lor

Grupurile sunt una dintre clasele taxonomice folosite pentru a clasifica structurile matematice cu proprietăți caracteristice comune. Grupurile au două componente: multe (G) Și operațiuni() definit pe acest set.

Conceptele de mulțime, element și apartenență sunt conceptele de bază nedefinite ale matematicii moderne. Orice mulțime este definită de elementele incluse în el (care, la rândul lor, pot fi și mulțimi). Astfel, spunem că o mulțime este definită sau dată dacă pentru orice element putem spune dacă aparține sau nu acestei mulțimi.

Pentru două seturi A, Bînregistrări B O, B O, B∩ O, B O, B \ O, O × B respectiv înseamnă că B este un subset al multimii O(adică orice element din B este de asemenea cuprinsă în O, de exemplu, mulțimea numerelor naturale este conținută în mulțimea numerelor reale; în plus, întotdeauna O O), B este un subset propriu al multimii O(aceste. B OŞi B ≠ O), intersecția mulțimilor BŞi O(adică toate astfel de elemente care se află simultan în O, și în B, de exemplu, intersecția numerelor întregi și a numerelor reale pozitive este mulțimea numerelor naturale), uniunea mulțimilor BŞi O(adică un set format din elemente care se află fie în O, sau în B), setați diferența BŞi O(adică setul de elemente care se află în B, dar nu minți O), produsul cartezian al multimilor OŞi B(adică un set de perechi de forma ( o, b), Unde o O, b B). Prin | O| puterea multimii este intotdeauna notata O, adică numărul de elemente din set O.

O operație este o regulă conform căreia oricare două elemente ale unei mulțimi G(oŞi b) se potrivește cu al treilea element din G: a b.

O mulțime de elemente G cu o operație se numește grup, dacă sunt îndeplinite următoarele condiții.

Să luăm în considerare sistemul de comparații

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

Teorema 1. Fie M = cel mai mic multiplu comun al numerelor m1,m2,…,ms. Dacă un sistem satisface (2), atunci orice număr din clasa a modulo M satisface acest sistem.

Dovada. Fie b€ la clasa a. Deoarece a ≡ b(mod M), atunci a ≡b(mod m), i= 1,2,...,s (proprietatea de comparație 16). În consecință, b, ca și a, satisface orice comparație a sistemului, ceea ce demonstrează teorema. Prin urmare, este firesc să considerăm că soluția sistemului (2) este o clasă modulo M.

Definiţie. Rezolvarea sistemului de comparații(2) este clasa de numere modulo M = care satisfac fiecare comparație a sistemului.

12. Să observăm imediat că numerele impare nu satisfac a doua comparație. Luând numere pare din sistemul complet de reziduuri modulo 12, prin verificare directă suntem convinși că numerele 2, -2, 6 satisfac a 2-a comparație, iar sistemul are două soluții: x ≡ 2(mod l2), x ≡ - 2 (modul 12).

Să luăm în considerare sistemul de comparații de gradul I (3)

Teorema 2. Fie d=(m1,m2), M = .

Dacă c1 - c2 nu este divizibil cu d, atunci sistemul (3) nu are soluții.

Dacă (c1 -c2):d, atunci sistemul (3) are o soluție - o clasă modulo M.

Dovada. Din prima comparație x = c1+m1t, t€Z. Înlocuiți în a doua comparație: с1+ m1t ≡ c2(mod m2) sau

m1t ≡ c2-cl (mod m2). Această comparație are o soluție numai dacă (c2 – c1): d.

Iar soluția este o clasă modulo (Teorema 4 din §2).

Fie soluția , adică unde k€Z.

M== , adică x≡c1+m1t0(mod M) este soluția

Exemple.

1. :2, sistemul are o clasă soluție modulo 24. Din prima comparație x =2+6t. Înlocuind x în a 2-a comparație, avem: 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, adică x≡-4(mod 24).

2. 7-3 nu este divizibil cu 3, sistemul nu are soluții.

Corolarul 1. Sistem de comparare (4)

Fie nu are soluții, fie are o singură soluție - o clasă modulo M=.

Dovada. Dacă sistemul primelor două comparații nu are soluții, atunci (4) nu are soluții. Dacă are o soluție x ≡ a(mod), atunci prin adăugarea unei a treia comparații a sistemului la această comparație, obținem din nou un sistem de forma (3), care fie are o soluție, fie nu are soluții. Dacă are o soluție, atunci vom continua astfel până când vom epuiza toate comparațiile sistemului (4). Dacă există o soluție, atunci aceasta este o clasă modulo M.

Comentariu. Proprietatea LCM este folosită aici: =.

Corolarul 2. Dacă m1,m2,…,ms sunt coprime perechi, atunci sistemul (4) are o soluție – clasa modulo M=m1m2…ms.

Exemplu:

Deoarece modulele sunt relativ simple pe perechi, sistemul are o soluție - modulo clasa 105 = 5*3*7. De la prima comparație

În a doua comparație înlocuim: 2 +5t≡ 0(mod 3) sau 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Să înlocuim în a treia comparație:

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

Să ne întâlnim alţii metoda de rezolvare a acestui sistem, (folosim faptul că sistemul are o singură soluție.) Să înmulțim ambele părți și modulul primei comparații cu 21, a doua cu 35 și a treia cu 15: din suma celor primul și al treilea îl scadem pe al doilea:

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

Să considerăm acum un sistem de comparații de gradul întâi de formă generală

Dacă o comparație a acestui sistem nu are soluții, atunci sistemul nu are soluții. Dacă fiecare comparație a sistemului (5) este rezolvabilă, atunci o rezolvăm pentru x și obținem un sistem echivalent de forma (4):

Unde (Teorema 4, §2).

Prin corolarul 1, sistemul fie nu are soluții, fie are o singură soluție.

Exemplu:

După ce am rezolvat fiecare comparație a sistemului, obținem un sistem echivalent

Acest sistem are o soluție - clasa modulo 105. Înmulțind prima comparație și modulul cu 3, iar a doua cu 35, obținem

Scăzând prima comparație înmulțită cu 11 din a doua comparație, obținem 2x ≡-62(modl05), din care x ≡ -31(modl05).

Probleme care se rezumă la luarea în considerare a unui sistem de comparații de gradul I au fost luate în considerare în aritmetica matematicianului chinez Sun Tzu, care a trăit pe la începutul erei noastre. Întrebarea lui a fost pusă în următoarea formă: găsiți un număr care să dea resturi date atunci când este împărțit la numere date. De asemenea, oferă o soluție echivalentă cu următoarea teoremă.

Teoremă (teorema chineză a restului). Fie m1,m2,…,ms numere coprime perechi, M = mlm2...ms, β1, β2,…, βs alese astfel încât

Apoi soluția sistemului

Va arăta ca x≡x0(mod M).

Dovada. Deoarece obținem x0≡

În mod similar, verificăm că x0≡c2(mod m2),…, x0≡cs(mod ms), adică x0 satisface toate

comparații de sistem.

10. Comparații de gradul I. Ecuații incerte

§ 2. Comparaţii de gradul I. Ecuații incerte

Comparația de gradul 1 poate fi redusă la forma ax≡b(mod m).

Teorema 4. Dacă (a,m) = 1, atunci comparația ax ≡b(mod m) (2) are o soluție unică.

Dovada. Să luăm 0,1,2,...,m-1 - un sistem complet de reziduuri modulo m. Deoarece (a,m) = 1, atunci 0,a,2a,...,(m-1)a este și un sistem complet de reziduuri (Teorema 3, §2, Capitolul 2.). Conține unul și un singur număr comparabil cu b modulo m (aparținând aceleiași clase cu b). Fie acesta ax 0, adică ax 0 € clasa b sau ax 0 ≡b(mod m). x ≡x 0 (mod m) este singura soluție pentru (2). Teorema a fost demonstrată.

Teorema 5. Dacă (a, m)= 1, atunci soluția comparației ax≡b(mod m) este clasa x 0 ≡a φ (m)-1 b(mod m).

Dovada. Deoarece (a,m) = 1, atunci după principiul lui Euler a φ(m) ≡1(mod m). Este ușor de observat că x 0 ≡a φ (m)-1 b (mod m) este soluția comparației (2). Într-adevăr, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Din teorema 4 rezultă că această soluție este unică.

Să luăm în considerare metode de soluție de comparație ax ≡b(mod m).

1. Metoda de selecție. Luând sistemul complet de reziduuri modulo m, selectăm numere care satisfac comparația.

2. Folosind teorema lui Euler (Teorema 5).

3. Metoda de conversie a coeficientului. Trebuie să încercăm să transformăm coeficienții astfel încât partea dreaptă să poată fi împărțită la coeficientul lui x. Transformările în cauză sunt următoarele: înlocuirea coeficienților cu resturile absolute cele mai mici, înlocuirea numărului b cu un număr comparabil în valoare absolută (adăugarea unui număr care este multiplu al valorii absolute) astfel încât acesta din urmă să fie divizibil cu a, deplasându-se de la a și b la alte numere comparabile cu acestea, care ar avea un divizor comun etc. În acest caz, folosim proprietățile comparațiilor și teoremele pe comparații echivalente bazate pe acestea.

1) 223x ≡ 115(mod ll).

În primul rând, înlocuim coeficienții cu cele mai mici deduceri de valoare absolută: 3х ≡ 5(mod 11). Dacă folosim teorema

Euler, atunci

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

Cu toate acestea, este mai ușor să convertiți coeficienții. Să înlocuim comparația cu una echivalentă prin adăugarea în partea dreaptă a unui număr care este un multiplu al modulului:

3x ≡ 5 + 22(mod 11). Împărțind ambele părți la numărul 3, coprim la modul, obținem x ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Folosim metoda de conversie a coeficientului.

(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 (modul 34).

Teorema 6. Dacă (a, m) = d și b nu este divizibil cu d, atunci comparația (1) nu are soluții.

Dovada (prin contradictie). Fie clasa x 0 o soluție, adică ax 0 ≡b (mod m) sau (ax 0 -b):m și, prin urmare, (ax 0 -b):d. Dar a:d, atunci b:d este o contradicție. Prin urmare, comparația nu are soluții.

Teorema 7. Dacă (a,m)= d, d>1, b:d, atunci comparația(1) are d

soluții care constituie o clasă de resturi modulo și se găsesc prin formule

Unde Cu satisface comparaţia auxiliară

Comentariu. Conform teoremei, comparația (1) se rezolvă după cum urmează.

1) După ce ne-am asigurat că (a,m) = d, d> 1 și b:d, împărțim ambele părți în comparații (2) cu d și obținem o comparație auxiliară a 1 x≡b 1 (mod m 1) , unde . Comparația are o singură soluție. Fie clasa c soluția.

2) Scrieți răspunsul 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).

Dovada. Comparația auxiliară conform teoremei 2(3) este echivalentă cu comparația inițială (2). Deoarece ( 1, Atunci comparația auxiliară are o soluție unică - o clasă modulo m 1 = . Fie x≡c(mod m 1) soluția. Clasa de numere c modulo m 1 se împarte în d clase modulo m: .

Într-adevăr, orice număr din clasa x0 modulo m 1 are forma x 0 +m 1 t. Împărțiți t cu rest la d: t = dq +r, unde 0≤r

Deci, comparația (1) are d soluții modulo m: x0, x0+m1,..., x0 +(d-1)m1 (linii orizontale în partea de sus)

Exemple.

1) 20x≡ 15(mod 108). Deoarece (20.108) = 4 și 15 nu este divizibil cu 4, nu există soluții.

2) 20x≡ 44(mod 108). (20,108) = 4 și 44:4, prin urmare comparația are patru soluții. Împărțind ambele părți și modulul la 4, obținem:

5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Atunci x≡13 + 27r(mod 108), unde r = 0,1,2,3. eu jj

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

Aplicarea teoriei comparațiilor la rezolvarea ecuațiilor incerte

Să considerăm o ecuație nedeterminată sau, așa cum se numește altfel, o ecuație diofantică de gradul I cu două necunoscute ax + by = c, unde a, b, c € Z. Trebuie să rezolvați această ecuație în numere întregi. Dacă (a,b)=d și c nu este divizibil cu d, atunci este evident că comparația nu are soluții în numere întregi. Dacă c este divizibil cu d, atunci împărțiți ambele părți ale ecuației cu d. Prin urmare, este suficient să luăm în considerare cazul când (a, b) =1.

Deoarece ax diferă de c printr-un multiplu al lui b, atunci ax ≡ c(mod b) (fără pierderea generalității putem presupune că b > 0). Rezolvând această comparație, obținem x ≡x1 (mod b) sau x=x1+bt, unde t€Z. Pentru a determina valorile corespunzătoare ale lui y avem ecuația a(x1 + bt) + by = c, din care

Mai mult, - este un număr întreg, este o valoare parțială a necunoscutului y, corespunzător lui x1 (se dovedește, ca x1, la t = 0). Iar soluția generală a ecuației va lua forma unui sistem de ecuații x=x1+bt, y=y1-at, unde t este orice număr întreg.

Nota că 1) ecuația ax + by = c ar putea fi rezolvată începând cu comparația cu ≡ c(mod a), întrucât by diferă de c printr-un multiplu al lui a;

2) este mai convenabil să alegeți ca modul cel mai mic modul a și b.

Exemplu, 50x – 42y= 34.

Împărțiți ambele părți ale ecuației la 2.

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

x ≡ -1 (mod 21), adică x=-1+21t, t€Z. Să înlocuim x-ul găsit în ecuație. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t și у =-2 + 25t.