Aritmetica modulară

Aritmetica modulară (uneori numită aritmetică de ceas, deoarece calculul orelor în cicluri de 12 sau 24 se bazează pe acest principiu) reprezintă o ramură importantă a matematicii . Acesta găsește aplicații în criptografie , în teoria numerelor (în special în căutarea numerelor prime ) și stă la baza multora dintre cele mai frecvente operații aritmetice și algebrice .

Este un sistem de aritmetică întreagă , în care numerele se „înfășoară în jurul lor” de fiecare dată când ajung la multiplii unui anumit număr n , numit modulo . Aritmetica modulară și notația obișnuită a congruențelor au fost introduse formal de Carl Friedrich Gauss în tratatul său Disquisitiones Arithmeticae , publicat în 1801 .

Relația de congruență

Aritmetica modulară se bazează pe conceptul de congruență modulo n . Având în vedere trei numere întregi a , b , n , cu n ≠ 0, spunem că a și b sunt congruente modulo n, sau că a este congruent cu b modulo n , dacă diferența ( a - b ) este un multiplu al lui n . În acest caz scriem

a\equiv b{\pmod {n}}\,

{\ displaystyle a \ equiv b {\ pmod {n}} \,}

{\ displaystyle a \ equiv b {\ pmod {n}} \,}

De exemplu, putem scrie

38\equiv 14{\pmod {12}}\,

{\ displaystyle 38 \ equiv 14 {\ pmod {12}} \,}

{\ displaystyle 38 \ equiv 14 {\ pmod {12}} \,}

deoarece 38 - 14 = 24, care este multiplu de 12.

Dacă ambele numere sunt pozitive, putem spune, de asemenea, că a și b sunt modulo congruente n dacă au același rest în diviziune cu n . Deci, putem spune, de asemenea, că 38 este congruent cu 14 modulo 12, deoarece atât 38, cât și 14 au restul 2, împărțind la 12.

Proprietățile congruențelor

Relația de echivalență

Congruența este o relație de echivalență între numere întregi, după cum se poate observa din următoarele proprietăți:

Proprietate reflexivă : fiecare număr este congruent cu modulul n , pentru fiecare n diferit de 0.

a\equiv a{\pmod {n}}\qquad \forall a\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equals {\ pmod {n}} \ qquad \ forall a \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

{\ displaystyle a \ equals {\ pmod {n}} \ qquad \ forall a \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

Dovadă : avem a - a = 0 și, după cum se știe, fiecare număr întreg diferit de zero este divizor de 0. Prin urmare, n se împarte (a - a)

Proprietate simetrică : dacă a este congruent cu b modulul n atunci b este congruent cu un modul n

a\equiv b{\pmod {n}}\Rightarrow b\equiv a{\pmod {n}}\qquad \forall a,b\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow b \ equiv a {\ pmod {n}} \ qquad \ forall a, b \ in \ mathbb {N}, \ forall n \ in \ mathbb { N} _ {0}}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow b \ equiv a {\ pmod {n}} \ qquad \ forall a, b \ in \ mathbb {N}, \ forall n \ in \ mathbb { N} _ {0}}

Dovadă : dacă n divide (a - b) , atunci n împarte și opusul (b - a) = - (a - b)

Proprietate tranzitivă : dacă a este congruent cu b modulul n și b este congruent cu c modulul n atunci și a este congruent cu c modulul n .

a\equiv b{\pmod {n}}\quad \land \quad b\equiv c{\pmod {n}}\Rightarrow a\equiv c{\pmod {n}}\qquad \forall a,b,c\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equiv b {\ pmod {n}} \ quad \ land \ quad b \ equiv c {\ pmod {n}} \ Rightarrow a \ equiv c {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

{\ displaystyle a \ equiv b {\ pmod {n}} \ quad \ land \ quad b \ equiv c {\ pmod {n}} \ Rightarrow a \ equiv c {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

Dovadă : dacă n împarte (a - b) și n împarte (b - c) atunci, la proprietatea distributivă a divizării în raport cu suma, n împarte și [(a - b) + (b - c)] = [ a - b + b - c] = (a - c) .

Invarianță în ceea ce privește operațiile aritmetice

O altă caracteristică importantă a relației de congruență este faptul că este păstrată din operațiile aritmetice obișnuite dintre numere întregi:

Invarianță prin adăugare : prin creșterea sau descreșterea a două numere congruente modulul n cu aceeași cantitate, noile numere obținute sunt încă congruente între ele modulul n . Mai pe scurt

a\equiv b{\pmod {n}}\Leftrightarrow (a+c)\equiv (b+c){\pmod {n}}\qquad \forall a,b,c\in \mathbb {Z} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Leftrightarrow (a + c) \ equiv (b + c) {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {Z }, \ forall n \ in \ mathbb {N} _ {0}}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Leftrightarrow (a + c) \ equiv (b + c) {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {Z }, \ forall n \ in \ mathbb {N} _ {0}}

Dovadă : (a - b) = (a - b + c - c) = (a + c) - (b + c)

Invarianța prin înmulțire : înmulțind două numere congruente modulul n cu aceeași cantitate, noile numere obținute sunt încă congruente între ele modulul n .

a\equiv b{\pmod {n}}\Rightarrow a\cdot c\equiv b\cdot c{\pmod {n}}\qquad \forall a,b,c\in \mathbb {Z} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow a \ cdot c \ equiv b \ cdot c {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {Z}, \ forall n \ in \ mathbb {N} _ {0}}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow a \ cdot c \ equiv b \ cdot c {\ pmod {n}} \ qquad \ forall a, b, c \ in \ mathbb {Z}, \ forall n \ in \ mathbb {N} _ {0}}

Dovadă : dacă n divide (a - b) atunci n divide (a - b) × c

Notă : puteți inversa această proprietate numai dacă GCD ( n , c ) = 1.

Invarianță în ceea ce privește exponențierea : creșterea a două numere congruente modulul n la aceeași putere k , numerele obținute sunt încă congruente între ele modulul n .

a\equiv b{\pmod {n}}\Rightarrow a^{k}\equiv b^{k}{\pmod {n}}\qquad \forall a,b\in \mathbb {Z} ,\forall k\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow a ^ {k} \ equiv b ^ {k} {\ pmod {n}} \ qquad \ forall a, b \ in \ mathbb {Z}, \ forall k \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

{\ displaystyle a \ equiv b {\ pmod {n}} \ Rightarrow a ^ {k} \ equiv b ^ {k} {\ pmod {n}} \ qquad \ forall a, b \ in \ mathbb {Z}, \ forall k \ in \ mathbb {N}, \ forall n \ in \ mathbb {N} _ {0}}

Dovadă : dacă a ≡ b ≡ 0 (mod n) propoziția este banală. Dacă a ≡ b (mod n) nu este nul, presupuneți că

a^{k-1}\equiv b^{k-1}{\pmod {n}}

{\ displaystyle a ^ {k-1} \ equiv b ^ {k-1} {\ pmod {n}}}

{\ displaystyle a ^ {k-1} \ equiv b ^ {k-1} {\ pmod {n}}}

. Înmulțind ambii termeni cu o mulțumire invarianței prin înmulțire, obținem

a^{k}\equiv b^{k-1}\cdot a{\pmod {n}}

{\ displaystyle a ^ {k} \ equiv b ^ {k-1} \ cdot a {\ pmod {n}}}

{\ displaystyle a ^ {k} \ equiv b ^ {k-1} \ cdot a {\ pmod {n}}}

. Începând de la congruența a ≡ b (mod n) și înmulțind ambele părți cu

b^{k-1}{\pmod {n}}

{\ displaystyle b ^ {k-1} {\ pmod {n}}}

{\ displaystyle b ^ {k-1} {\ pmod {n}}}

, din nou datorită invarianței prin multiplicare, obținem:

a\cdot b^{k-1}\equiv b^{k}{\pmod {n}}

{\ displaystyle a \ cdot b ^ {k-1} \ equiv b ^ {k} {\ pmod {n}}}

{\ displaystyle a \ cdot b ^ {k-1} \ equiv b ^ {k} {\ pmod {n}}}

. Comparând cele două expresii și folosind proprietățile simetrice și tranzitive, deducem că

a^{k}\equiv b^{k}{\pmod {n}}

{\ displaystyle a ^ {k} \ equiv b ^ {k} {\ pmod {n}}}

{\ displaystyle a ^ {k} \ equiv b ^ {k} {\ pmod {n}}}

. Deoarece propoziția este adevărată pentru k = 1 și a fi adevărată pentru k-1 implică faptul că este adevărată pentru k , prin principiul inducției propoziția este adevărată pentru toți k .

Celelalte clase modulo n

Proprietățile reflexive, simetrice și tranzitive descrise mai sus indică faptul că relația de congruență modulul n este o relație de echivalență și, prin urmare, definește un set de coeficienți .

Împărțirea euclidiană a unui întreg a cu n , deci

a=k\times n+r

{\ displaystyle a = k \ times n + r}

{\ displaystyle a = k \ times n + r}

adică

a-r=k\times n

{\ displaystyle ar = k \ times n}

{\ displaystyle a-r = k \ times n}

vă permite să împărțiți întregul $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb Z$ a numerelor întregi din $n$ ${\ displaystyle n}$ $n$ clase (subseturi) conform următoarei relații de echivalență: se spune că este un număr întreg $la$ ${\ displaystyle a}$ $la$ este echivalent cu $r{\pmod {n}}$ ${\ displaystyle r {\ pmod {n}}}$ ${\ displaystyle r {\ pmod {n}}}$ dacă și numai dacă diferența $a-r$ ${\ displaystyle ar}$ ${\ displaystyle a-r}$ este un relativ multiplu al $n$ ${\ displaystyle n}$ $n$ . Astfel definim setul de coeficient de $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb Z$ în ceea ce privește această relație de echivalență și formată din n clase

[0],[1],...,[n-2],[n-1]

{\ displaystyle [0], [1], ..., [n-2], [n-1]}

{\ displaystyle [0], [1], ..., [n-2], [n-1]}

numite clase de odihnă modulo $n$ ${\ displaystyle n}$ $n$ .

Fiecare clasă de rest [ r ] reprezintă, pe lângă r în sine, toate numerele întregi de forma a = k × n + r pentru un număr întreg k .

De exemplu, în modulul de congruență 7, clasa restului [5] reprezintă, pe lângă numărul 5, și numărul 12 (= 1 × 7 + 5), numărul 19 (= 2 × 7 + 5), număr 2308 (= 329 × 7 + 5) etc. Mai mult, [5] reprezintă, de asemenea, numărul -2 (= -1 × 7 + 5), numărul -9 (= -2 × 7 + 5) și așa mai departe.

Aritmetica congruențelor modulul n

Invarianțele descrise mai sus cu privire la sumă și multiplicare indică faptul că aceste operații sunt, de asemenea, bine definite la coeficient. Aceste operațiuni continuă să satisfacă proprietățile comutative , asociative și distributive . Elementele neutre pentru adunare și multiplicare sunt clasele [0] și [1].

Clasele modulo n cu suma formează un grup abelian : mai exact, formează un grup ciclic finit . Cu suma și produsul formează un inel . Spre deosebire de ceea ce se întâmplă pentru numere întregi , produsul a două elemente diferite de zero poate fi zero. De exemplu:

[2]*[3]=[6]=[0]

{\ displaystyle [2] * [3] = [6] = [0]}

{\ displaystyle [2] * [3] = [6] = [0]}

de sine

n=6

{\ displaystyle n = 6}

{\ displaystyle n = 6}

.

Acest lucru nu se întâmplă, totuși, când n este un număr prim : de fapt, în acest caz, clasele formează un domeniu de integritate și, de asemenea, un câmp .

Printre proprietățile operațiilor găsim următoarele:

$[a]+[b]=[a+b]$ ${\ displaystyle [a] + [b] = [a + b]}$ ${\ displaystyle [a] + [b] = [a + b]}$
$[ab]=[a][b]$ ${\ displaystyle [ab] = [a] [b]}$ ${\ displaystyle [ab] = [a] [b]}$

Rădăcini primitive

Același subiect în detaliu: Generator (teoria numerelor) .

Datorită prezenței posibile a divizorilor lui 0, în general $\mathbb {Z} _{n}-\{0\}$ ${\ displaystyle \ mathbb {Z} _ {n} - \ {0 \}}$ ${\ displaystyle \ mathbb {Z} _ {n} - \ {0 \}}$ nu este un grup cu produsul. De fapt, divizorii lui 0 nu au inversuri. Pe de altă parte, atunci când nu există divizori diferiți de 0, adică în cazurile cu n prime, înmulțirea formează un grup multiplicativ și inelul $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ este un câmp. Cu toate acestea, dacă ne restrângem la clasele ale căror reprezentări sunt coprimă cu n , această proprietate reapare. Este ușor să demonstrați acest lucru recurgând la identitatea Bézout : dacă a este coprimă cu n , există două numere întregi x și y astfel încât

ax+ny=1

{\ displaystyle ax + ny = 1}

{\ displaystyle ax + ny = 1}

adică reducerea modulului n ,

ax\equiv 1\mod n

{\ displaystyle ax \ equiv 1 \ mod n}

{\ displaystyle ax \ equiv 1 \ mod n}

și, prin urmare, fiecare a are un invers. Mai mult, multiplicarea continuă să fie internă inelului și să posede proprietăți asociative și comutative , iar clasa [1] este elementul neutru.

Un rezultat important, găsit deja de Gauss, este că acest grup este ciclic dacă și numai dacă n este 2, 4, puterea unui număr prim impar sau dublul puterii unui număr prim impar. Generatorii acestui grup ciclic sunt uneori numiți rădăcini primitive modulo n .

Polinoame în aritmetică modulară

Același subiect în detaliu: Congruențe polinomiale .

De asemenea, în $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ este posibil, prin operațiile definite mai sus, să vorbim despre polinoame . Proprietățile acestora diferă în multe cazuri de proprietățile „uzuale” observate atunci când se iau în considerare polinoame pe câmpuri precum $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ $\ mathbb {Q}$ sau $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ , sau pe inele precum $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ . De exemplu, principiul identității polinoamelor (două polinoame asumă valori egale dacă și numai dacă coeficienții lor sunt unul câte unul egali) nu este valid, deși o versiune modificată a acestuia este validă.

De asemenea, în studiul acestui subiect, la fel ca în majoritatea aritmeticii modulare, se disting două tipuri foarte diferite de comportament. $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ : când n este prim și când n este compus. În ultimul caz, nefiind $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ nici un câmp, nici un domeniu de integritate , comportamentul polinoamelor poate fi foarte „ciudat”: de exemplu, congruența polinomului de gradul 2 $x^{2}-1\equiv 0\mod 8$ ${\ displaystyle x ^ {2} -1 \ equiv 0 \ mod 8}$ ${\ displaystyle x ^ {2} -1 \ equiv 0 \ mod 8}$ are patru soluții (1, 3, 5 și 7) atunci când în câmpuri infinite, cum ar fi raționalele, realele sau complexele, numărul de soluții nu poate depăși gradul polinomului.

Ireductibilitate

Inelele $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ $\ mathbb {Z} _p$ ele oferă, de asemenea, o modalitate de a studia ireductibilitatea polinoamelor cu coeficienți întregi și, prin urmare, prin lema lui Gauss , și a celor cu coeficienți raționali . De fapt, dacă un polinom este reductibil în inel $\mathbb {Z} [X]$ ${\ displaystyle \ mathbb {Z} [X]}$ ${\ mathbb {Z}} [X]$ polinoame cu coeficienți întregi, cum ar fi f (x) = g (x) h (x), atunci același modulo este valabil pentru orice prim p :

$[f(x)]_{p}\equiv [g(x)]_{p}[h(x)]_{p}\mod p$ ${\ displaystyle [f (x)] _ {p} \ equiv [g (x)] _ {p} [h (x)] _ {p} \ mod p}$ ${\ displaystyle [f (x)] _ {p} \ equiv [g (x)] _ {p} [h (x)] _ {p} \ mod p}$

Această proprietate poate fi exploatată pentru a construi un criteriu de ireductibilitate : dacă un polinom nu este luat în considerare $\mathbb {Z} _{p}[X]$ ${\ displaystyle \ mathbb {Z} _ {p} [X]}$ ${\ displaystyle \ mathbb {Z} _ {p} [X]}$ , cu p prim care nu împarte coeficientul termenului de grad maxim, atunci nu este luat în considerare, adică este ireductibil, în inel $\mathbb {Z} [X]$ ${\ displaystyle \ mathbb {Z} [X]}$ ${\ mathbb {Z}} [X]$ .

Conversa nu este adevărată: $f(x)=x^{2}+1$ ${\ displaystyle f (x) = x ^ {2} +1}$ ${\ displaystyle f (x) = x ^ {2} +1}$ este ireductibil în $\mathbb {Z} [X]$ ${\ displaystyle \ mathbb {Z} [X]}$ ${\ mathbb {Z}} [X]$ , dar în $\mathbb {Z} _{5}[X]$ ${\ displaystyle \ mathbb {Z} _ {5} [X]}$ ${\ displaystyle \ mathbb {Z} _ {5} [X]}$ este luat în considerare ca

x^{2}+1\equiv (x+2)(x+3)\mod 5

{\ displaystyle x ^ {2} +1 \ equiv (x + 2) (x + 3) \ mod 5}

{\ displaystyle x ^ {2} +1 \ equiv (x + 2) (x + 3) \ mod 5}

Ecuații diofantine

În același mod ca și studiul ireductibilității polinoamelor, în studiul ecuațiilor diofantine se studiază uneori același mod de ecuație și un număr întreg n pentru a furniza condițiile necesare rezolvabilității ecuației în sine. De exemplu ecuația

x^{3}+7y^{3}=2

{\ displaystyle x ^ {3} + 7y ^ {3} = 2}

{\ displaystyle x ^ {3} + 7y ^ {3} = 2}

nu poate avea soluții întregi, pentru că dacă ar exista o soluție $(x_{0},y_{0})$ ${\ displaystyle (x_ {0}, y_ {0})}$ $(x_0, y_0)$ acest lucru ar fi, de asemenea, același în inelul de congruențe modulo 7; adică congruența ar trebui să fie rezolvabilă

x^{3}+7y^{3}\equiv 2\mod 7

{\ displaystyle x ^ {3} + 7y ^ {3} \ equiv 2 \ mod 7}

{\ displaystyle x ^ {3} + 7y ^ {3} \ equiv 2 \ mod 7}

x^{3}\equiv 2\mod 7

{\ displaystyle x ^ {3} \ equiv 2 \ mod 7}

{\ displaystyle x ^ {3} \ equiv 2 \ mod 7}

care nu are soluții, deoarece valorile posibile pe care și le asumă $x^{3}\mod 7$ ${\ displaystyle x ^ {3} \ mod 7}$ ${\ displaystyle x ^ {3} \ mod 7}$ sunt 0, 1 și 6.

Bibliografie

Tom M. Apostol, Introducere în teoria numerelor analitice , Springer-Verlag , New York , 1976. ISBN 0-387-90163-9 , capitolul 5.
H. Davenport, Aritmetica superioară , Zanichelli , Bologna , 1994, ISBN 88-08-09154-6 , capitolul II.
T. Sengadir, Matematică discretă și combinatorică . Chennai, India: Pearson Education India, 2009. ISBN 978-81-317-1405-8

Elemente conexe

Alte proiecte

Wikibooks conține texte sau manuale aritmetice modulare
Wikimedia Commons conține imagini sau alte fișiere pe aritmetică modulară

linkuri externe

( EN ) Aritmetica modulară , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Teoria numerelor
Cele mai utilizate numere	Natural · Întreg · Par și impar
Principii generale	Principiul inducției · Principiul unei bune ordonări · Relația de echivalență
Secvențe de numere întregi	Factorial · Fibonacci · Număr de catalană · Număr Perrin · Număr de Euler · Secvență Mian-Chowla · Succesiunea lui Thue-Morse
Caracteristicile numerelor prime	Primul număr · lema lui Euclid · Teorema infinitate de numere prime · ciurul Eratostene · teste primality · Teorema fundamentală a aritmeticii · Total acoperire mine · Bézout Identitate · MCD · mcm · algoritmul lui Euclid · Teorema de Prime Numbers
Funcții aritmetice	Funcție multiplicativă · funcție aditivă · Convoluție Dirichlet · Funcția Euler Euler · Funcția Möbius · funcția tau pe pozitiv · funcția sigmoidă · Funcția Liouville · Funcția Mertens
Aritmetica modulară	Teorema a restului chinez · teorema lui Fermat mici · teorema lui Euler · Criterii de divizibilitate · teorema lui Fermat pe sume de două pătrate · Wilson Teorema · reciprocitatea pătratică
Conjecturi	Conjectura lui Goldbach · Conjectura Polignac · Guess abc · conjectura primelor gemene · Conjectura lui Legendre · Noua conjectură Mersenne · Conjectura Collatz · Ipoteza Riemann
Alte	Problema lui Waring
Principalii teoreticieni	Fibonacci · Fermat · Gauss · Euler · Legendre · Riemann · Dirichlet
Disciplinele conexe	Teoria algebrică a numerelor · Teoria analitică a numerelor · Criptografie · Teoria computațională a numerelor