Clasa de reziduuri - l

defini

Ei spun că două numere întregi și un bsravnimy modulo un număr natural n. dacă acestea dau același rest când împărțit la n.

Formulări echivalente: a și bsravnimy pe modulyun. în cazul în care diferența lor a - b este împărțit de n. sau dacă poate fi reprezentat ca a = b + kuna. unde k - un întreg.

EXEMPLU: 32 și -10 sunt modulo congruente 7, deoarece 32 = 7 ∙ 4 + 4 -10 = 7 ∙ (-2) + 4.

Adoptarea «a și b sunt congruente modulo n» poate fi scris ca:

Comparând raportul este o relație de echivalență și are multe din proprietățile ecuațiilor convenționale. De exemplu, acestea pot fi adăugate și multiplicate: dacă

Prin comparație, cu toate acestea, nu poate, în general vorbind, să împartă între ele sau la alt număr. De exemplu, cu toate acestea, a scăzut cu 2, obținem o comparație greșită :. Reguli pentru reducerea următoarele comparații.

Puteți diviza ambele părți ale compararea numărului de prim cu modul: dacă GCD, atunci.
Este posibil să se separe simultan cele două părți ale modulului de comparație, și factorul lor comun: în cazul în care, atunci.

Nu puteți efectua operațiuni cu comparații, în cazul în care modulele nu sunt aceleași.

Dacă, atunci, în cazul în care m = [m1, m2].
Dacă există o, b sunt comparabile în orice modul - împărțitor m.

clase de reziduuri

Setul tuturor numerelor congruentă cu un modulo n este numit un rest de clasa modulo n. și de obicei desemnate [a] n sau. Astfel, comparația este claselor echivalente ale reziduurilor [a] n = [b] n.

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

operații de adunare și înmulțire pentru a induce operațiile corespunzătoare pe platoul de filmare:

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

Relativ multe dintre aceste operații este un inel finit. iar dacă n este prim - un câmp finit.

comparație soluție

Comparațiile de gradul I

În teoria numerelor. criptografie și în alte domenii ale științei apare adesea problema de a găsi soluții de congruența primul grad de forma:

Soluția comparației începe prin calcularea cmmdc (a, m) = d. În acest caz, există 2 cazuri:

În cazul în care b nu este un multiplu de d. apoi comparații nu sunt soluții.
În cazul în care b este un multiplu de d. apoi compararea unei soluții unice pentru modulul m / d. sau ceea ce este același lucru, soluții d modulo m. În acest caz, prin reducerea comparațiilor inițiale în comparație d se transformă:

unde a1 = a / d. b1 = b / d și m1 = m / d fiind numere întregi, unde a1 și m1 sunt prime între ele. Prin urmare, numărul a1 poate plăti m1 modulo. care este, pentru a găsi un număr de c. că (cu alte cuvinte). Acum, soluția se obține prin înmulțirea comparație c:

Cum de a calcula valoarea C se poate face în diferite moduri: folosind teorema lui Euler. Algoritmul lui Euclid. . Teoria fracțiilor continue (. Cm algoritm) etc. In particular, teorema lui Euler ne permite să scrie valoarea c în forma:

Exemplu rezolva ecuația. Aici d = 2. Prin urmare, modulo 22 comparație are două soluții. Înlocuiți 26 4 comparabil cu ei modulo 22, iar apoi se reduce numărul de toate cele 3 pentru 2:

Deoarece 2 este prim la modul 11, este posibil să se reducă din stânga și din dreapta de 2. Ca rezultat, vom obține o soluție modulo 11: echivalentul a două soluții modulo 22 :.

Comparațiile gradul al doilea

al doilea grad de soluții se reduce la a determina dacă numărul unui reziduu pătratice (folosind legea de reciprocitate pătratic) și calcularea ulterioară a rădăcinii pătrate a acestui modul.

În mare parte teoria divizibilitate și deduceri a fost creat de Euler. Comparațiile Modulo folosit pentru prima dată de Gauss în cartea sa „cercetare aritmetică“, în 1801. De asemenea, el a propus să aprobe simbolurile matematice pentru comparații.

Veil O .. Fundamentele teoria numerelor, Moscova: Mir, 1972.
Vilenkin N. I .. Comparații și clase de reziduuri. Quant. Numărul 10 1978.
Vinogradov M .. Principiile fundamentale ale teoriei numerelor. M. GITTL 1952.

Vezi ce „clasa de reziduuri“ în alte dicționare:

descărcare de gestiune clasa de impozitare - punctul de pe scara venitului impozabil la care venitul impozabil (venitul impozabil). De asemenea, numit. categorie de impozitare marginală (categorie de impozitare marginală). Acesta și-a exprimat în procente, care trebuie să se aplice pentru fiecare ... ... Finanțe și Investiții dicționar

Teoria Numerelor - secțiunea matematică pură, a studiat numerele întregi 0, ± 1, ± 2. și relațiile dintre ele. Uneori teoria numerelor se numește aritmetică mai mare. Calcule separate efectuate pe numărul specific, de exemplu, 9 + 16 = 25, nu ... ... Enciclopedia Collier

Quotient - câtul în algebra abstractă este inelul de clasa rest al unui inel modulo idealul său. Indicat. clase de reziduuri modulo definite ca clasele de reziduuri ale inelului asupra grupului de aditivi ... Wikipedia

INDEX -. Numărul unui indicator SW modulo m compararea a = gg (mod m), unde ai tvzaimno ușor, și g este un primitiv modulo rădăcină m fix de apo AI toboznachaetsya module prin g = indg bine sau, mai succint, în = ind o. Rădăcinile primitivi ... ... Enciclopedia de matematică

Nilpotency ELEMENT - Element nilpotence akoltsa semigrup cu zero sau A, care satisface ecuația pentru un anumit număr întreg n valoare minimă cerned de n pentru cerned la această ecuație se numește .. indicele nilpotency unui. Ex. în inelul de reziduuri modulo ... Enciclopedia de Matematică

Nilpotente - sau nilpotence - inel membru satisface egalitatea pentru un număr natural. Valoarea minimă. care satisface această ecuație se numește indicele nilpotency al elementului. nilpotents considerare de multe ori ... ... Wikipedia