Definirea și proprietățile resturilor

Un rezumat al teoriei

Aplicând teorema privind diviziunea cu rest poate fi un set de numere întregi divizate într-un număr de clase. Să considerăm un exemplu. Să m = 6. Apoi, avem șase clase de partiție a mulțimii de numere întregi modulo 6:

în care R reprezintă restul după împărțirea întreg 6.

Să ne amintim teorema pe diviziune cu rest:

Teorema. Împărțiți numărul de numărul. . cu restul, astfel încât să găsească o pereche de întregi q și r. astfel încât sunt îndeplinite următoarele condiții :.

Este ușor să se demonstreze că pentru orice numere întregi a și o diviziune cu rest este posibil și numărul de q și r sunt în mod unic determinată. În acest exemplu, un sistem complet de non-negativ, cel puțin, există multe deduceri; sistem complet al reziduului cel pozitiv - set; un sistem complet de mici deduceri de valoare absolută - set; Sistemul de deducere de mai sus - mai multe; set factor

O metodă pentru efectuarea operațiunilor aritmetice pe date întregi pe baza prevederilor simple ale teoriei numerelor. Ideea acestei metode este faptul că numerele întregi sunt reprezentate într-unul din sistemele nepozitsionnyh - în sistemul de clase reziduale. Și anume, în loc de operațiunile de pe numere întregi operează cu reziduuri de la divizarea acestor numere prime pentru un număr de pre-selectate - module.

În cele mai multe cazuri, numărul este selectat dintr-o multitudine de numere prime.

Deoarece în inelul de întregi este o teoremă pe diviziune cu rest, r. E. În cazul în care. Z. inel, prin definiție, este un euclidiană.

Astfel, cifrele pot fi alese prin împărțirea numărului de resturi din A pi respectiv.

sistem de deducere permite operații aritmetice într-un set finit de numere nu va merge dincolo de limitele sale. Un sistem complet de resturi modulo n # 8213; orice set de n modulo incongruente n perechi numere întregi. De obicei, ca un sistem complet de reziduuri modulo n provin de la cele mai mici resturi de nenegative

Numerele sunt, de asemenea, numite deducere pentru modulyum. NeotritsatelnyeVYChETy a = r (când q = 0), care ia valori în intervalul [0, 1 m - 1]. formează un sistem complet de resturi puțin modulyum.

De exemplu, când forma m = 5 clase mai mici resturi

r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Cele două seturi de numere date sub formă de sistem complet de reziduuri modulo 5 s.

clase de reziduuri. elemente care sunt prime între ele la modulul m

numita redus. Funcția Euler determină cât de mult deducerea din sistem complet de reziduuri modulyum puțin relativ prim la m. Într-un mod simplu, avem m = p = p-1.

Definiția. Set maxim de m numere modulo incongruente relativ perechi prime la m. Acesta a numit sistemul redus de reziduuri modulo m. Fiecare sistem de mai sus a reziduurilor modulo m conține elemente care - funcția Euler.

Definiția. Orice număr de clasă Je m echivalență se numesc o deducere mii modulo m. Setul de deducere e luat una din fiecare clasă de echivalență Je m. Se numește întregul sistem de deducere modulo m (sistem de deducere integrală s, astfel încât toate piesele numerele m). Direct ei înșiși reziduuri atunci când împărțită m este reziduul cel nenegativ de s și, desigur, formează un sistem complet de deducere s modulo m. Deducerea r este numit absolută cea mai mică, în cazul în care ïrï cea mai mică dintre modulele s deducerea din această clasă.

Exemplu. Verificați dacă forma de 13 8 - 3, 10, 35, 60 plin de resturi modulo m = 6 sistem.

Decizie. Prin definirea formei unui sistem complet de resturi modulo m. dacă exact m și ele sunt Pairwise incomparabil modulyum.

Pairwise incomparabil poate fi verificată prin înlocuirea fiecărui număr este cel mai mic non-negativ, net; Dacă repetarea nu este, atunci este un sistem complet de reziduuri.

Aplicam teorema diviziunii cu rest: a = mq + r.

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

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

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

Numerele primite secventa 1, 2, 3, 4, 5, 0, 6 sunt exact, repetiție și au reciproc incomparabil. Aceasta înseamnă că ele formează un sistem complet de resturi modulo m = 6.

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

Decizie. Aplicăm teorema privind diviziunea cu rest:

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

Exemplu. Verificați dacă numărul formularului (13, -13, 29, -9) redus sistem de reziduuri modulo m = 10.

Soluție: Orice Sistemul de mai sus a reziduurilor modulo m conține elemente care - functia Euler. În acest caz, k = 4, deoarece între numerele naturale numai 1, 3, 7, 9 cu 10 prime între ele, și nu-l depășească. Asta este, este posibil ca aceste patru numere alcătuiesc sistemul dorit. Noi verificam aceste numere pe incomparabila lor pairwise:

13 = 10 1 + 3; 13 martie (mod 10); - 13 10 = (- 2) + 7; -13 7 (mod 10);

29 = 10 2 + 9; 29 septembrie (mod 10); - 9 10 = (- 1) + 1; - 1 septembrie (mod 10).

Toate numărul de Pairwise incomparabilă, nici unul dintre ele sunt repeta, sunt exact 4 și nu depășesc modulul. Prin urmare, ele formează sistemul redus de reziduuri.

Exemplu. Verificați dacă numărul de formă (-349, -193, 231, 401) redus sistem de reziduuri modulo m = 12.

Soluție: În acest caz, k = 4, deoarece între numerele naturale numai 1, 3, 7, 9 cu 10 prime între ele, și nu-l depășească. Asta este, este posibil ca aceste patru numere alcătuiesc sistemul dorit. Noi verificam aceste numere pe incomparabila lor pairwise:

-12 = 349 (-30) + 11; -349 11 (mod 12);

- = 12 193 (-17) + 11; -193 11 (mod 12);

231 = 12 19 + 3; 231 3 (mod 12);

401 = 12 33 + 5; 401 5 (mod 12).

Printre numerele au o repetare, avem două numere comparabile -349 și -193. Prin urmare, cifrele nu formează sistemul redus de reziduuri.

Setarea 1. Modificați numărul și cea mai mică în valoare absolută, precum și cel mai mic reziduu pozitiv modulo m.

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

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

5. întruchipare a = 85, m = 11; 6. întruchipare a = 84, m = 8;

7. întruchipare a = 103, m = 87; 8. întruchipare a = 84, m = 16;

9. întruchipare a = 15, m = 10; 10. întruchipare a = 81, m = 9;

11. întruchipare a = 85, m = 15; 12. întruchipare a = 74, m = 13;

Întruchipare 13. a = 185, m = 16; 14. întruchipare a = 14, m = 9;

Întruchipare 15. a = 100, m = 11; 16. întruchipare a = 484, m = 15;

Întruchipare 17. a = 153, m = 61; 18. întruchipare a = 217, m = 19;

19. întruchipare a = 625, m = 25; 20. întruchipare a = 624, m = 25;

Sarcina 3. Scrieți un sistem complet și cel mai puțin redus