Comparație modulo un număr natural. Rezolvarea comparațiilor și aplicațiile lor Rezolvarea unui sistem de comparații modulo

unde este coeficientul binom.

Exemplu. Rezolvați comparația 7x≡ 2 (modul 11). Noi calculăm:

Lema 1 (teorema chineză a restului). Să fie dat cel mai simplu sistem de comparații de gradul întâi:

Unde m 1 ,m 2 ,...,m k sunt coprime perechi. Să, mai departe, m 1 m 2 ...m k =M s m s; doamna doamna ∇ ≡ 1 (mod m s)(Evident, care este numărul Domnișoară∇ poate fi întotdeauna ales folosind cel puțin algoritmul euclidian, deoarece (ms,Ms)=1); x 0 \u003d M 1 M 1 ∇ b1 +M2M2 ∇ b 2 +...+M k M k ∇ b k. Atunci sistemul (*) este echivalent cu o comparație X≡ x 0 (mod m 1 m 2 ...m k), adică multimea solutiilor (*) este aceeasi cu multimea solutiilor de comparatie X≡ x 0 (mod m 1 m 2 ...m k).

Exemplu. Odată, un prieten obișnuit a abordat un prieten inteligent și l-a rugat să găsească un număr care, împărțit la 4, dă restul de 1, atunci când este împărțit la 5, dă restul de 3, iar când este împărțit la 7, dă restul de 2. Prietenul mediu el însuși caută un astfel de număr de două săptămâni. Un tovarăș inteligent a compilat imediat un sistem:

pe care a început să o rezolve folosind Lema 1. Iată soluția lui:

b 1 =1; b2=3; b 3 \u003d 2; m 1 m 2 m 3, adică M 1 \u003d 35, M 2 \u003d 28, M 3 \u003d 20.

acestea. M1 ∇ =3, M2 ∇ =2, M3∇=6. Mijloace x0=35 ⋅ 3 ⋅ 1+28 ⋅ 2 ⋅ 3+20 ⋅ 6 ⋅ 2=513. După aceea, prin Lema 1, tovarășul deștept a primit imediat răspunsul:

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

acestea. cel mai mic număr pozitiv pe care îl căuta prietenul obișnuit timp de două săptămâni este 93. Așa că prietenul inteligent l-a ajutat încă o dată pe prietenul mediu.

Lema 2. Dacă b 1 ,b 2 ,...,b k rulează prin sisteme complete de reziduuri modulo m 1 ,m 2 ,...,m k respectiv, atunci x0 parcurge sistemul complet de reziduuri modulo m 1 m 2 ...m k.

Două numere întregi a și b sunt comparabile modulo un număr natural m є N dacă, împărțite la m, dau același rest. .

Teorema (criteriul de comparabilitate): . Corolarul 1: fiecare număr este congruent modulo m cu restul lui modulo m: . Corolarul 2: un număr este congruent modulo m, m. și așa., deoarece este divizibil cu acest mod.

Proprietăți de bază de comparație: 1). Comparațiile relative sunt relativ echivalente. 2). Comparațiile în același modulo se pot scădea termen cu termen: . Termenul poate fi transferat dintr-o parte în alta, în timp ce semnul este inversat. 3). În fiecare parte a comparației, puteți adăuga orice număr care este un multiplu al modulului: comparațiile cu același modulo pot fi înmulțite termen cu termen. Consecințe: 1. Ambele părți ale comparației pot fi ridicate la orice putere naturală. 2. Ambele părți ale comparației pot fi înmulțite cu orice număr natural. 4). Ambele părți ale comparației și modulul pot fi înmulțite cu același număr sau reduse cu oricare dintre divizorii lor comuni. 5). Dacă comparația are loc în mai multe module, atunci are loc și în modulo, care este egal cu cel mai mare multiplu sau cel mai mare divizor comun al acestora

6). Dacă comparația are loc modulo m, atunci are loc și modulo m

divizor al lui m. 7). Divizorul comun al unei părți a comparației și modulul este divizorul celeilalte părți a comparației: , .

Mica teoremă a lui Fermat: dacă a și m sunt numere coprime, atunci . Funcția Euler este numărul de numere pozitive care nu depășesc n și coprime la n. Dacă un întreg a este copprim cu m, atunci . teorema lui Euler: dacă un întreg a este copprim cu m, atunci . Teorema lui Fermat: 1. Dacă un întreg a nu împarte p, unde p este prim, atunci . 2. Dacă p este prim și a este orice număr întreg, atunci . Relația de comparabilitate sunt clase de echivalență. Clasele de echivalență sunt numite și clase de reziduuri, iar echivalențele lor sunt numite reziduuri.

Soluție de comparație: Fie , , mєN. Apoi se numește comparație k-putere cu o necunoscută și are cel mult m clase de soluții. Soluțiile acestei comparații vor fi clasele de reziduuri modulo m. Comparațiile de gradul I cu o necunoscută pot fi scrise astfel: dacă: 1). această comparație nu are nicio soluție (de exemplu, 5x). 2). Dacă decizia acestei comparaţii. 3). .

Teorema: Fie , , atunci , d clase de soluții mod m. Metode de rezolvare a comparațiilor: 1). Metodă de testare a unui sistem complet de deduceri. 2). Metoda de conversie a coeficientului. Orice număr care este un multiplu al modulului se adună sau se scade din partea dreaptă, înlocuind coeficienții din partea stângă cu numărul de comparații cu modulul. Este posibil să se transforme comparațiile astfel încât să poată fi reduse cu a și să obțină o soluție.

Luați î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€ să aparțină clasei a. Deoarece a ≡ b(mod M), atunci a ≡b(mod m), i= 1,2,...,s (proprietatea de comparație 16). Prin urmare, b, ca și a, satisface fiecare comparație a sistemului, ceea ce demonstrează teorema. Prin urmare, este firesc să considerăm clasa modulo M ca o soluție a sistemului (2).

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

12. 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ă ne asigurăm 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).

Luați în considerare sistemul de comparații de gradul I (3)

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

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 - clasa 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ă de soluții modulo 24. Din prima comparație x =2+6t. Înlocuind în loc de 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.

Consecința 1. Sistem de comparare (4)

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

Dovada. Dacă sistemul primelor două comparații nu are soluții, atunci (4) nu are nicio soluție. Dacă are o soluție x ≡ a(mod), atunci, adăugând la această comparație a treia comparație a sistemului, 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 continuăm în acest fel până când epuizăm toate comparațiile sistemului (4). Dacă există o soluție, atunci aceasta este o clasă modulo M.

Cometariu. Proprietatea LCM este folosită aici: =.

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

Exemplu:

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

Înlocuiți în a doua comparație: 2 +5t≡ 0(mod 3) sau 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Înlocuiți î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 cunoaștem alții mod de a rezolva acest sistem, (folosim faptul că sistemul are o singură soluție.) Să înmulțim ambele părți și modulul primei comparații cu 21, al doilea cu 35b al celui de-al treilea cu 15: scădem a doua din suma lui primul si al treilea:

(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 al unei forme generale

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:

Rezolvând fiecare comparație a sistemului, obținem un sistem echivalent

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

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

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

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

Apoi soluția la sistem

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 nedefinite

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

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

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

Dovada. Să luăm 0,1,2,...,m-1 - sistemul complet de reziduuri modulo m. Deoarece (а, m) = 1, atunci 0,а,2а,...,(m-1)а este și un sistem complet de reziduuri (Teorema 3, §2, Cap. 2.). Conține unul și un singur număr congruent cu b modulo m (aparținând aceleiași clase cu b). Fie 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ă timpul lui Euler a φ(m) ≡1(mod m). Este ușor de observat că x 0 ≡a φ (m)-1 b (mod m) este soluția de comparație (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ă.

Considera metode de decizie de comparare ax ≡b(mod m).

1. Metoda de selecție. Luând un sistem complet de reziduuri modulo m, alegem numere care satisfac comparația.

2. Utilizarea teoremei 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 de la x. Transformările în cauză sunt următoarele: înlocuirea coeficienților cu resturile absolut cele mai mici, înlocuirea numărului b cu un număr comparabil în valoare absolută (prin adăugarea unui număr care este multiplu al modulului) 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 și așa mai departe. În acest sens, folosim proprietățile congruențelor și teoremele pentru comparații echivalente bazate pe acestea.

1) 223x ≡ 115(modll).

În primul rând, înlocuim coeficienții cu cele mai puține reziduuri absolute: Зх ≡ 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 unui multiplu al modulului în partea dreaptă:

3x ≡ 5 + 22(mod 11). Împărțind ambele părți la un număr 3 coprim cu modulul, 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 congruența (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 alcătuiesc o clasă de resturi modulo și se găsesc prin formule

Unde Cu satisface o comparaţie auxiliară

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

1) După ce ne asigurăm că (a,m) = d, d> 1 și b:d, împărțim ambele părți în comparația (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ă prin Teorema 2(3) este echivalentă cu comparația inițială (2). Deoarece ( 1, Atunci congruența auxiliară are o soluție unică – clasa modulo m 1 = . Fie x≡c(mod m 1) soluția. Clasa numerelor 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 de mai 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, deci comparația are patru soluții. Împărțind ambele părți și modulul la 4, obținem:

5x≡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 soluția ecuațiilor nedefinite

Luați în considerare o ecuație nedefinită sau, cum se numește altfel, ecuație diofantică de gradul I cu două necunoscute ax + by = c, unde a, b, c € Z. Este necesar să se rezolve 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țim 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, de unde

Mai mult, este un număr întreg, este o valoare particulară a necunoscutului y, corespunzător lui x1 (se dovedește, ca x1, cu 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.

Notă 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 dintre module 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 (mod 21).

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