Un set de numere comparabil cu A modulo m numit clasa de numere modulo m(sau clasa de echivalență). Toate numerele unei clase au forma mt+ r la fix r.

Pentru un dat m, r poate lua valori de la 0 la m-1, adică totul există m clase de numere modulo m, și orice număr întreg va intra într-una dintre clasele modulo m. Prin urmare,

Z= m m … [m-1]m, Unde [ r]m={X Z: X≡r(mod m)}

Orice număr de clasă [ r]m numit minus modulo mîn raport cu toate numerele aceleiaşi clase. Număr egal cu restul r, numit cea mai mică deducere nenegativă.

Se numește deducerea care este cea mai mică în valoare absolută absolut cea mai mică deducere.

Exemplu

Să luăm modulul m=5. Lăsați-l să plece A=8. Să împărțim A pe m cu rest:

Rest r=3. Aceasta înseamnă 8 5, iar cel mai mic reziduu nenegativ al numărului 8 modulo 5 este 3.

Cea mai mică deducere absolută poate fi găsită calculând r-m=3-5=-2 și comparând valorile absolute |-2| și |3|. |-2|<|3|, значит -2 – абсолютно наименьший вычет числа 8 по модулю 5.

Luând o deducere din fiecare clasă, obținem sistem complet de deduceri modulo m. Dacă toate aceste numere sunt cele mai mici resturi modulo nenegative m, atunci se numește un astfel de sistem de deduceri sistem complet de reziduuri cel puțin nenegative, și este notat cu Z m.

{0; 1;…; m-1) = Z m– un sistem complet de reziduuri cel puțin nenegative.

(– ;…; 0;…; ) (dacă m-numar impar) ;

(- ,…,-1, 0, 1,…, ) sau (- ,…, -1, 0, 1,…, ) (dacă m număr par) este un sistem complet de reziduuri absolut minime.

Exemplu

Dacă m=11, atunci sistemul complet al celor mai puține reziduuri nenegative este (0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10), iar sistemul complet al celor mai puține reziduuri este (–5 ; –4; –3; –2; –1; 0; 1; 2; 3; 4; 5).

Afirmația 1

Orice m numere care sunt perechi incomparabile ca modul m, formează un sistem complet de reziduuri pentru acest modul.

Dovada:

Într-adevăr, din cauza incomparabilității, aceste numere aparțin unor clase diferite, și de atunci al lor m piese, atunci fiecare clasă existentă conține exact un număr.

Afirmația 2

Dacă ( A, m) = 1 și X parcurge sistemul complet de resturi modulo m, Acea topor+b, Unde b– orice număr din Z trece și prin sistemul complet de resturi modulo m.

Dovada:

Numerele topor+b va fi neted m lucruri. Rămâne de demonstrat că orice 2 numere topor 1 +bȘi topor 2 +b incomparabil ca modul m, Dacă X 1 X 2 (mod m)

Dovada prin contradictie. Să ne prefacem că topor 1 +b≡ topor 2 +b(mod m) datorita sfintei a 4-a a comparatiilor, topor 1 ≡ topor 2 (mod m) datorită naturii comparațiilor nr. 9 și a faptului că ( A, m) = 1, avem X 1 ≡ X 2 (mod m). Avem o contradicție cu faptul că X 1 X 2 (mod m). Prin urmare, presupunerea este falsă, ceea ce înseamnă că contrariul este adevărat. Acesta este topor 1 +bȘi topor 2 +b incomparabil ca modul m, Dacă X 1 X 2 (mod m), ceea ce trebuia dovedit.

Ecuația de împărțire (), discutată în secțiunea anterioară, are două intrări (a și n) și două ieșiri (q și r). În aritmetica modulară ne interesează doar una dintre ieșiri, restul r. Nu ne pasă de q privat. Cu alte cuvinte, când împărțim a la n, ne interesează doar ce valoarea restului este r. Aceasta implică faptul că putem reprezenta imaginea ecuației de mai sus ca operator binar cu două intrări a și n și o ieșire r.

Operații cu modul

Cele de mai sus operator binar numit operator moduloși se notează ca mod. A doua intrare (n) este numită modul. Ieșirea r este numită minus. Figura 2.9 prezintă relația de divizare față de operatorul modulo.

Orez. 2.9.

Orez. 2.13.

De fapt, se folosesc două seturi de operatori: primul set este unul dintre operatori binari; al doilea este operatori modulo. Trebuie să folosim paranteze pentru a sublinia ordinea operațiilor. După cum se arată în Fig. 2.13, intrările (a și b) pot fi membri ai lui Z sau Zn.

Exemplul 2.16

Executați următoarele afirmații (care provin de la Zn):

A. Adăugând 7 și 14 la Z 15

b. Scăzând 11 din 7 în Z 13

V. Înmulțind 11 cu 7 în Z 20

Soluţie

(14+7) mod 15 -> (21) mod 15 = 6 (7–11) mod 13 -> (-4) mod 13 = 9 (7x11) mod 20 -> (77) mod 20 = 17

Exemplul 2.17

Efectuați următoarele operații (care provin din Zn):

A. Adăugarea 17 și 27 în Z 14

b. Scăzând 43 de la 12 la Z 13

c. Înmulțind 123 cu -10 în Z 19

Soluţie

Mai jos sunt doi pași pentru fiecare operație:

(17 + 27) mod 14 -> (44) mod 14 = 2 (12 – 43) mod 13 -> (–31) mod 13 = 8 ((123) x (–10)) mod 19 -> (–1230) ) mod 19 = 5

Proprietăți

Am menționat deja că două intrări pentru trei operatori binari comparațiile modulo pot folosi date de la Z sau Zn. Următoarele proprietăți ne permit să afișăm mai întâi două intrări la Z n (dacă provin de la Z ) înainte de a executa cele trei

Clase de deducere. Sisteme de deducere

Scurte informații din teorie

Folosind teorema împărțirii cu rest, puteți împărți o mulțime de numere întregi într-un număr de clase. Să ne uităm la un exemplu. Lăsa m = 6. Atunci avem șase clase de partiții ale mulțimii de întregi modulo 6:

r = 1;

r = 2;

r = 3;

r = 4;

r = 5;

unde prin r indică restul la împărțirea unui număr întreg la 6.

Să ne amintim teorema despre împărțirea cu rest:

Teorema: Împărțirea unui număr la numărul , , cu un rest înseamnă găsirea unei perechi de numere întregi qȘi r, astfel încât să fie îndeplinite următoarele condiții: .

Este ușor de demonstrat că pentru orice număr întreg A iar împărțirea cu un rest este posibilă și pentru numere q Și r sunt determinate fără ambiguitate. În exemplul nostru, sistemul complet al resturilor cel mai puțin nenegative este mulțimea (0, 1, 2, 3, 4, 5); sistem complet de reziduuri cel mai puțin pozitive – set (0, 1, 2, 3, 4, 5); un sistem complet de reziduuri cu cea mai mică valoare absolută – set (-2,-1, 0, 1, 2, 3); sistemul redus de reziduuri este multimea (1,5), deoarece ; set de factori

O metodă de a efectua operații aritmetice pe numere întregi date se bazează pe principii simple ale teoriei numerelor. Ideea acestei metode este că numerele întregi sunt reprezentate într-unul dintre sistemele nepoziționale - în sistemul de clase reziduale. Și anume: în loc de operații pe numere întregi, acestea operează cu resturi de la împărțirea acestor numere în numere prime preselectate - module .

Cel mai adesea numere alege dintr-un set de numere prime.

Lăsa …, .

Deoarece în inelul întregilor este valabilă teorema împărțirii cu rest, adică unde , atunci inelul Z, prin definiție, este euclidiană.

Astfel, ca numere puteți alege resturile din împărțirea unui număr A pe p i respectiv.

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- orice set de n modul incomparabil pe perechi n numere întregi. De obicei, ca un sistem complet de deducții modulo n se iau cele mai mici reziduuri nenegative

Împărțirea numerelor întregi A Și m rezultă coeficientul q iar restul r , astfel încât

a = m q + r, 0 r m-1. Rest r numit DEDUCERE ohm modulo m.

De exemplu, pentru m = 3 și pentru m =5 obținem:

a = m q + r, m = 3	a = m q + r, m = 5
0 = 3 + 0	0 = 5 + 0
1 = 3 + 1	1 = 5 + 1
2 = 3 + 2	2 = 5 + 2
3 = 3 + 0	3 = 5 + 3
4 = 3 + 1	4 = 5 + 4
5 = 3 + 2	5 = 5 + 0
6 = 3 + 0	6 = 5 + 1
7 = 3 + 1	7 = 5 + 2

Dacă restul este zero ( r=0 ), apoi spun asta m desparte A complet (sau m multiplu A ), ceea ce înseamnă m A , și numerele q Și m numiti divizori A . Evident 1 A Și A A . Dacă A nu are alți divizori decât 1 Și A , Acea A – număr prim, în caz contrar A numit număr compus. Cel mai mare divizor pozitiv d doua numere A Și m se numește cel mai mare divizor comun (MCD) și denotă d = (a,m). Dacă gcd (a,m)= 1 , Acea A Și m nu au divizori comuni cu excepția 1 , și se numesc coprime unul față de celălalt.

Pentru fiecare DEDUCERE la r = 0, 1, 2,…, m-1 corespunde unui set de numere întregi a, b,… Ei spun că numerele cu aceleași DEDUCERE om sunt comparabile ca modul și notate cu a b(mod m) sau (a b) m.

De exemplu, când m = 3 :

De exemplu, când m = 5 :

Numerele A , care sunt comparabile ca modul m , formează o clasă proprie DEDUCERE r și sunt definite ca a = m q+r.

Numerele A numit si CU DEDUCERI modulo m . Nenegativ DEDUCERI a = r (la q=0 ), luând valori din interval , formează un sistem complet de resturi minime modulo m.

DEDUCERI A , luând valori din interval [-( ,…,( ] , la ciudat m sau din interval [- la chiar m formează un sistem complet de absolut cel mai mic DEDUCERE ov modulo m.

De exemplu, când m = se formează 5 clase de cele mai mici reziduuri

r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Ambele seturi date de numere formează sisteme complete deducere ov modulo 5 .

Clasă DEDUCERI, ale căror elemente sunt coprime cu modulul m

numit redus. Funcția lui Euler determină cât DEDUCERI din sistemul complet al deducțiilor mai puțin modulo m coprime cu m . Cu simplu m=p avem = p-1.

Definiție. Setul maxim de module incomparabile pe perechi m numere coprime la m , numit sistem dat de deduceri modulo m. Orice sistem redus de resturi modulo m conține elemente în care este funcția Euler.

Definiție. Orice număr din clasa de echivalență є m vom suna deducere ohm modulo m. Totalitate deducere s, luată câte una din fiecare clasă de echivalență є m, se numește sistem complet deducere ov modulo m(în sistem complet deducere ov, astfel, în total m bucăți de numere). Resturile în sine atunci când sunt împărțite cu m sunt numite cele mai mici nenegative deducere ami și, desigur, formează un sistem complet deducere ov modulo m. Deducere r este numit absolut cel mai mic dacă ïrï este cel mai mic dintre module deducere ov din această clasă.

Exemplu. Verificați dacă numerele 13, 8, - 3, 10, 35, 60 formează un sistem complet de reziduuri modulo m=6.

Soluţie: Prin definiție, numerele formează un sistem complet de resturi modulo m, dacă sunt exact m dintre ele și sunt incomparabile în perechi ca modul m.

Incomparabilitatea perechilor poate fi verificată prin înlocuirea fiecărui număr cu cel mai mic reziduu nenegativ; dacă nu există repetări, atunci acesta este un sistem complet de deduceri.

Să aplicăm teorema împărțirii cu rest: a = m q+r.

13 = 6 2 + 1 13 1(mod 6); 8 = 6 1 + 2 8 2(mod 6);

3 = 6 (-1) + 3 -3 3(mod 6); 10 = 6 1 + 4 10 4(mod 6);

35 = 6 5 + 5 35 5(mod 6); 60 = 6 10 + 0 60 0(mod 6).

Am obținut o succesiune de numere: 1, 2, 3, 4, 5, 0, sunt exact 6, nu există repetări și sunt incomparabile în perechi. Adică formează un sistem complet de reziduuri modulo m = 6.

Exemplu. Înlocuiți cu cea mai mică valoare absolută, precum și cu cel mai mic reziduu pozitiv 185 modulo 16.

Soluţie. Să aplicăm teorema împărțirii cu rest:

185 = 16 11 + 9 185 9(mod 16).

Exemplu. Verificați dacă numerele se formează (13, -13, 29, -9) sistem redus de reziduuri modulo m=10.

Rezolvare: Orice sistem redus de resturi modulo m conține elemente în care este funcția Euler. În cazul nostru =4, deoarece dintre numerele naturale doar 1, 3, 7, 9 sunt coprime la 10 și nu îl depășesc. Adică, este posibil ca aceste patru numere să alcătuiască sistemul dorit. Să verificăm aceste numere pentru incomparabilitatea lor pe perechi: =4, deoarece dintre numerele naturale doar 1, 3, 7, 9 sunt coprime cu 10 și nu o depășesc. Adică, este posibil ca aceste patru numere să alcătuiască sistemul dorit. Să verificăm aceste numere pentru incomparabilitatea lor pe perechi: m .

Opțiunea 1. A= 185, m = 12; Opțiunea 2. a = 84, m = 9;

Opțiunea 3. A= 180, m = 10; Opțiunea 4. a = 82, m = 9;

Opțiunea 5. A= 85, m = 11; Opțiunea 6. a = 84, m = 8;

Opțiunea 7. A= 103, m = 87; Opțiunea 8. a = 84, m = 16;

Opțiunea 9. A= 15, m = 10; Opțiunea 10. a = 81, m = 9;

Opțiunea 11. A= 85, m = 15; Opțiunea 12. a = 74, m = 13;

Opțiunea 13. A= 185, m = 16; Opțiunea 14. a = 14, m = 9;

Opțiunea 15. A= 100, m = 11; Opțiunea 16. a = 484, m = 15;

Opțiunea 17. A= 153, m = 61; Opțiunea 18. a = 217, m = 19;

Opțiunea 19. A= 625, m = 25; Opțiunea 20. a = 624, m = 25;

Sarcina 3. Notați sistemul complet și redus al celui mai mic

Clauza 17. Sisteme complete și reduse de deduceri.

În paragraful anterior s-a reținut că relația є m comparabilitate modulo arbitrară m este o relație de echivalență pe mulțimea numerelor întregi. Această relație de echivalență induce o partiție a mulțimii de numere întregi în clase de elemente echivalente între ele, i.e. numere care atunci când sunt împărțite la m solduri identice. Numărul de clase de echivalență є m(Experții vor spune - „indice de echivalență є m") este exact egală m .

Definiție. Orice număr din clasa de echivalență є mîl vom numi reziduu modulo m. Un set de deduceri luate câte una din fiecare clasă de echivalență є m, se numește un sistem complet de resturi modulo m(în sistemul complet de deduceri, prin urmare, numai m bucăți de numere). Resturile în sine atunci când sunt împărțite cu m sunt numite cele mai mici reziduuri nenegative și, desigur, formează un sistem complet de resturi modulo m. Un reziduu r se numește absolut cel mai mic dacă este cel mai mic dintre modulele de reziduuri ale unei clase date.

Exemplu: Lăsa m= 5 . Apoi:

0, 1, 2, 3, 4 - cele mai mici reziduuri nenegative;

2, -1, 0, 1, 2 sunt cele mai mici deduceri absolute.

Ambele seturi date de numere formează sisteme complete de resturi modulo 5 .

Lema 1. 1) Oricare m piese care nu sunt comparabile ca modul m numerele formează un sistem complet de resturi modulo m .

2) Dacă AȘi m sunt relativ simple și Xm, apoi valorile formei liniare topor+b, Unde b- orice număr întreg, de asemenea, rulat prin sistemul complet de reziduuri modulo m .

Dovada. Afirmația 1) este evidentă. Să demonstrăm afirmația 2). Numerele topor+b neted m lucruri. Să arătăm că nu sunt comparabile ca modul m. Ei bine, să fie pentru unii diferit x 1Și x 2 din sistemul complet de deduceri a rezultat că ax 1 +b є ax 2 +b(mod m). Apoi, conform proprietăților comparațiilor din paragraful anterior, obținem:

ax 1 є ax 2 (mod m)

x 1 є x 2 (mod m)

- o contradicţie cu faptul că x 1Și x 2 sunt diferite și luate din sistemul complet de deduceri.

Deoarece toate numerele dintr-o clasă de echivalență dată є sunt obținute dintr-un număr dintr-o clasă dată prin adăugarea unui număr care este multiplu m, atunci toate numerele din această clasă au modul m același cel mai mare divizor comun. Din anumite motive, de interes sporit sunt acele deduceri care au cu modulul m cel mai mare divizor comun egal cu unu, adică reziduuri care sunt coprime la modul.

Definiție. Sistemul redus de deducții modulo m este mulțimea tuturor reziduurilor din sistemul complet care sunt coprime la modul m .

Sistemul redus este de obicei ales dintre cele mai mici reziduuri nenegative. Este clar că sistemul dat de resturi modulo m conține j( m) bucăți de deduceri, unde j ( m) – Funcția Euler – numărul de numere mai mic decât mși amorsați reciproc cu m. Dacă până acum ați uitat deja funcția Euler, uitați-vă la paragraful 14 și asigurați-vă că acolo s-a spus ceva despre ea.

Exemplu. Lăsa m= 42. Atunci sistemul dat de reziduuri este:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Lema 2. 1) Orice j ( m) numere care sunt perechi incomparabile ca modul mși coprim cu modulul, formează un sistem redus de resturi modulo m .

2) Dacă (a,m) = 1Și X trece prin sistemul redus de resturi modulo m, Acea topor trece de asemenea prin sistemul redus de resturi modulo m .

Dovada. Afirmația 1) este evidentă. Să demonstrăm afirmația 2). Numerele topor sunt incomparabile perechi (acest lucru este dovedit în același mod ca în Lema 1 a acestui paragraf), există exact j dintre ele ( m) lucruri. De asemenea, este clar că toate sunt relativ prime pentru modul, deoarece (a,m)=1, (x,m)=1 Yu (ax.m)=1. Deci numerele topor formează un sistem redus de reziduuri.

Acestea sunt definițiile și proprietățile de bază ale sistemelor complete și reduse de reziduuri, totuși, în bagajul cunoștințelor matematice există o serie întreagă de fapte foarte interesante și utile referitoare la sistemele de reziduuri. Dacă păstrați tăcerea despre ele în acest paragraf, atunci aceasta, mă tem, va fi o încălcare directă a Legii Federației Ruse privind informațiile, a cărei ascundere rău intenționată este, conform acestei legi, o infracțiune administrativă și chiar penală. . În plus, fără familiarizarea cu alte proprietăți importante ale sistemelor de deducție, punctul 17 se va dovedi a fi foarte puțin. Hai sa continuăm.

Lema 3. Lăsa m 1, m 2, ..., m k– sunt perechi relativ prime și m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k, Unde

1) Dacă x 1 , x 2 , ..., x k rulează prin sisteme complete de reziduuri modulo m 1, m 2, ..., m k parcurge sistemul complet de deducții modulo m=m 1 m 2 ...m k .

2) Dacă x 1 , x 2 , ..., x k rulați prin sistemele cu reziduuri reduse modulo m 1, m 2, ..., m kîn consecință, apoi valorile formei liniare parcurge sistemul redus de reziduuri modulo m=m 1 m 2 ...m k .

Dovada.

1) Forma M1x1 +M2x2 + ...+Mkxk acceptă evident m 1 m 2 ...m k =m valorile. Să arătăm că aceste valori sunt incomparabile în perechi. Ei bine, lasă să fie

M 1 x 1 +M 2 x 2 + ...+M k x k є M 1 x 1 С +M 2 x 2 С + ...+M k x k С (mod m)

Tot felul de lucruri Mj, diferit de Domnișoară, multiple Domnișoară. Eliminarea termenilor din stânga și din dreapta din ultima comparație care sunt multipli Domnișoară, primim:

M s x s є M s x s С (mod m s) У x s є x s С (mod m s)

- o contradicţie cu faptul că xs parcurge sistemul complet de resturi modulo Domnișoară .

2). Formă M1x1 +M2x2 + ...+Mkxk evident ia j ( m 1) j ( m 2) Ch ... Ch j ( m k) = j ( m 1 m 2 H ... H m k)= j ( m) (Funcția lui Euler este multiplicativă!) de valori diferite, care se modulo reciproc m=m 1 m 2 ...m k perechi incomparabil. Acesta din urmă se dovedește cu ușurință prin raționament similar cu raționamentul efectuat în proba afirmației 1) a acestei leme. Deoarece ( M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=(M s x s ,m s)=1 pentru fiecare 1 Ј s Ј k, Acea ( M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=1, de unde și setul de valori ale formei M1x1 +M2x2 + ...+Mkxk formează un sistem redus de resturi modulo m .

Lema 4. Lăsa x 1 , x 2 , ..., x k ,x alerga plin și x 1 , x 2 ,..., x k , x– rulați prin sistemele date de reziduuri modulo m 1, m 2, ..., m kȘi m=m 1 m 2 ...m k respectiv, unde (m i m j)=1 la i Nu. j. Apoi fracții coincid cu fracțiile (x/m), și fracții coincid cu fracțiile (x/m) .

Dovada. Dovada ambelor afirmații ale Lemei 4 se obține ușor prin aplicarea Lemei 3 anterioare după ce ați dat fiecare sumă (x 1 /m 1 +x 2 /m 2 +...+x k /m k)Și ( x 1 /m 1 + x 2 /m 2 +...+ x k /m k ) la un numitor comun:

(x 1 /m 1 +x 2 /m 2 +...+x k /m k )=((M 1 x 1 +M 2 x 2 +...+M k x k)/m) ;

( x 1 /m 1 + x 2 /m 2 +...+ x k /m k )=((M 1 x 1 +M 2 x 2 +...+M k x k)/m) ,

Unde M j =m 1 ...m j-1 m j+1 ...m k .

Dacă acum luăm în considerare că părțile fracționale ale numerelor obținute la împărțirea la modul m oricare două numere comparabile ca modul m, sunt la fel (sunt egale r/m, Unde r este cel mai mic reziduu nenegativ dintr-o clasă dată), atunci afirmațiile acestei leme devin evidente.

În restul acestei secțiuni, se va întâmpla cel mai interesant lucru - vom însuma rădăcinile complexe m-a putere a unității și vom descoperi conexiuni uimitoare între sumele rădăcinilor, sistemele de reziduuri și deja familiară funcție multiplicativă Möbius m ( m) .

Să notăm cu e k k a rădăcină m- o, puterea unității:

Ne amintim bine aceste forme de scriere a numerelor complexe din primul an. Aici k=0,1,...,m-1– parcurge sistemul complet de deducții modulo m .

Permiteți-mi să vă reamintesc că suma e 0 + e 1 +...+ e m-1 toate rădăcinile m a-a putere a unuia este egală cu zero pentru oricare m. Într-adevăr, să e 0 + e 1 +...+ e m-1 =a. Să înmulțim această sumă cu un număr diferit de zero e 1. O astfel de multiplicare geometrică în plan complex înseamnă rotirea corectă m-un triunghi cu rădăcini la vârfuri e 0 , e 1 ,..., e m-1, la un unghi diferit de zero 2p/m. Este clar că în acest caz rădăcina e 0 va merge la rădăcină e 1, rădăcină e 1 va merge la rădăcină e 2, etc., și rădăcina e m-1 va merge la rădăcină e 0, adică sumă e 0 + e 1 +...+ e m-1 Nu se va schimba. Avem e 1 a=a, Unde a=0 .

Teorema 1. Lăsa m>0- întreg, un O Z , X parcurge sistemul complet de resturi modulo m. Atunci dacă A multiplu m, Acea

altfel, când A nu un multiplu m ,

.

Dovada. La A multiplu m avem: a=mdȘi

La A nedivizibil cu m, împărțiți numărătorul și numitorul fracției a.m pe d- cel mai mare divizor comun AȘi m, obținem o fracție ireductibilă a 1 /m 1. Apoi, după Lema 1, a 1 x va rula prin sistemul complet de deducții modulo m. Avem:

deoarece suma tuturor rădăcinilor gradului m 1 de la unu este egal cu zero.

Permiteți-mi să vă reamintesc că rădăcina e k m a-a putere a unității se numește antiderivată dacă indicele ei k coprime cu m. În acest caz, după cum sa dovedit în primul an, diplome succesive e k 1 , e k 2 ,..., e k m-1 rădăcină e k formează întregul set de rădăcini m-a putere a unuia sau, cu alte cuvinte, e k este elementul generator al grupului ciclic al tuturor rădăcinilor m-a putere a unității.

Evident, numărul de rădăcini primitive diferite m a-a putere a unității este egală cu j ( m), unde j este funcția Euler, deoarece indicii rădăcinilor antiderivate formează un sistem redus de resturi modulo m .

Teorema 2. Lăsa m>0– un număr întreg, x trece prin sistemul redus de reziduuri modulo m. Apoi (suma rădăcinilor antiderivate ale gradului m):

unde m ( m) – Funcția Möbius.

Dovada. Lăsa m=p 1 a 1 p 2 a 2 ...p k a k– extinderea canonică a unui număr m ; m 1 =p 1 a 1 , m 2 = p 2 a 2 , m 3 =p 3 a 3; x i trece prin sistemul redus de resturi modulo m i. Avem:

La a s = 1 rezultă că numai rădăcina e 0 =1 nu este antiderivată, prin urmare suma tuturor rădăcinilor antiderivate este suma tuturor rădăcinilor minus unu:

prin urmare, dacă m fără pătrate (adică nu este divizibil cu r 2, la r >1), Acea

Dacă vreun indicator la fel de mai mare decât unu (adică m impartit de r 2, la r>1), apoi suma tuturor rădăcinilor antiderivate ale gradului Domnișoară este suma tuturor rădăcinilor gradului Domnișoară minus suma tuturor rădăcinilor neprime, adică toate rădăcinile într-o oarecare măsură mai puțin Domnișoară. Exact dacă m s =p s m s *, Acea:

Acum, dragi cititori, când v-am prezentat în atenție o cantitate destul de semnificativă de informații despre sistemele complete și date de deducere, nimeni nu mă poate acuza că am încălcat cu răutate Legea Informației a Federației Ruse prin ascunderea acesteia, așa că termin. acest paragraf cu satisfacție.

Probleme

1 . Notează pe o foaie de hârtie toate cele mai mici reziduuri nenegative și toate cele mai mici reziduuri absolut a) modulo 6, b) modulo 8. Chiar mai jos scrieți sistemele date de deduceri pentru aceste module. Desenați separat a șasea și a opta rădăcină a unității pe planul complex, încercuiți rădăcinile primitive din ambele desene și găsiți suma lor în fiecare caz. 2 . Lăsa e– rădăcina primitivă a gradului 2n de la unul. Aflați suma: 1+ e + e 2 +...+ e n-1 . 3 . Aflați suma tuturor rădăcinilor primitive: a) a 15-a; b) 24; c) puterea a 30-a a unu. 4 . Aflați suma tuturor produselor posibile ale rădăcinilor primitive n-a putere de la unu, luată în doi. 5 . Găsiți suma k-x puterile tuturor rădăcinilor n-a putere a unității. 6 . Lăsa m>1 , (a, m)=1 , b– număr întreg, X trece prin sistemul complet și x – redus de reziduuri modulo m. Demonstrați că: A) b) 7 . Demonstrați că: , Unde R trece prin toți factorii primi ai unui număr A .

Sistem complet de deduceri. Sistemul dat de deduceri. Cele mai comune sisteme de deducții sunt: ​​cel mai puțin pozitiv, cel mai puțin nenegativ, absolut cel puțin etc.

Teorema 1. Proprietăți ale sistemului complet și redus de reziduuri.

1°.Criteriul pentru un sistem complet de deduceri. Orice colecție de m numere întregi care sunt perechi incomparabile ca modul m, formează un sistem complet de resturi modulo m.

2°. Dacă numerele X 1 , X 2 , ..., x m– un sistem complet de deducții modulo m, (A, m) = 1, b este un întreg arbitrar, apoi numerele topor 1 +b, topor 2 +b, ..., topor m+b alcătuiesc de asemenea un sistem complet de deducții modulo m.

3°. Criteriul sistemului redus de deduceri. Orice colecție constând din j( m) numere întregi care sunt perechi incomparabile ca modul mși coprim cu modulul, formează un sistem redus de resturi modulo m.

4°. Dacă numerele X 1 , X 2 , ..., X j ( m) – sistem redus de resturi modulo m, (A, m) = 1, apoi numerele topor 1 , topor 2 , ..., un x j ( m) formează, de asemenea, un sistem redus de resturi modulo m.

Teorema 2. teorema lui Euler.

Dacă numerele AȘi m relativ prim, atunci A j ( m) º 1(mod m).

Consecinţă.

1°. teorema lui Fermat. Dacă p– un număr prim și A nedivizibil cu p, Acea a p–1 º 1 (mod p).

2°. Teorema lui Fermat generalizată. Dacă p este un număr prim, atunci a p º A(mod p) pentru orice AÎ Z .

§ 4. Rezolvarea comparațiilor cu o variabilă

Rezolvarea comparațiilor. Echivalenţă. Gradul de comparație.

Teorema. Proprietăți ale soluțiilor la comparații.

1°. Soluțiile pentru comparații sunt clase întregi de reziduuri.

2°. (" k)(un k º b k(mod m))Ù k= Þ comparație º 0 (mod m) și º 0 (mod m) sunt echivalente.

3°. Dacă ambele părți ale comparației sunt înmulțite cu un număr coprim la modul, atunci se va obține o comparație care este echivalentă cu cea inițială.

4°. Orice comparație modulo prime p echivalează cu o comparaţie al cărei grad nu depăşeşte p–1.

5°. Comparație º 0 (mod p), Unde p– număr prim, nu are mai mult de n diverse solutii.

6°. teorema lui Wilson. ( n-1)! º –1 (mod n) Û n Număr prim.

§ 5. Rezolvarea comparațiilor de gradul I

topor º b(mod m).

Teorema. 1°. Dacă ( A, m) = 1, atunci comparația are o soluție, și una unică.

2°. Dacă ( A, m) = dȘi b nedivizibil cu d, atunci comparația nu are soluții.

3°. Dacă ( A, m) = dȘi b impartit de d, atunci comparația are d diferite soluții care constituie o clasă de reziduuri modulo .

Modalități de rezolvare a comparațiilor topor º b(mod m) în cazul în care ( A, m) = 1:

1) selecția (selectarea elementelor sistemului complet de deduceri);

2) utilizarea teoremei lui Euler;

3) utilizarea algoritmului euclidian;

4) variația coeficienților (utilizarea proprietății 2° a sistemului complet de reziduuri din Teorema 2.2);

§ 6. Ecuații nedeterminate de gradul I

topor+de = c.

Teorema. Ecuația topor+de = c rezolvabil dacă și numai dacă c (A, b).

Când ( A, b) = 1 toate soluțiile ecuației sunt date prin formule

tÎ Z , Unde X 0 este o soluție de comparație

topor º c(mod b), y 0 = .

Ecuații diofantine.

CAPITOLUL 10. Numere complexe

Definirea sistemului de numere complexe. Existența unui sistem de numere complexe

Definirea sistemului de numere complexe.

Teorema. Există un sistem de numere complexe.

Model: R 2 cu operatii

(A, b)+(c, d) = (A+c, b+d), (A, b)×( c, d) = (ac–bd, bc+anunț),

i= (0, 1) și identificare A = (A, 0).

Forma algebrică a numărului complex

Reprezentarea unui număr complex ca z = A+bi, Unde A, bÎ R , i 2 = –1. Unicitatea unei astfel de reprezentări. Re z, Sunt z.

Reguli pentru efectuarea operaţiilor aritmetice asupra numerelor complexe în formă algebrică.

Aritmetic n-spațiu vectorial dimensional C n. Sisteme de ecuații liniare, matrice și determinanți peste C .

Extragerea rădăcinilor pătrate ale numerelor complexe în formă algebrică.