Congruența polinomială

O congruență polinomială sau congruență algebrică este o congruență de acest tip

a_{k}x^{n}+a_{k-1}x^{n-1}+\cdots +a_{1}x+a_{0}\equiv 0\mod n

{\ displaystyle a_ {k} x ^ {n} + a_ {k-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0} \ equiv 0 \ mod n}

{\ displaystyle a_ {k} x ^ {n} + a_ {k-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0} \ equiv 0 \ mod n}

unde n este orice număr întreg mai mare sau egal cu 2.

Proprietățile acestor polinoame diferă în multe cazuri radical în raport cu proprietățile posedate, de exemplu, în numere întregi sau raționale; în alte cazuri, sunt valabile teoreme similare, dacă nu identice.

Proprietăți generale

Principiul identității polinoamelor

În $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ , $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ $\ mathbb {Q}$ , $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ Și $\mathbb {C}$ ${\ displaystyle \ mathbb {C}}$ ${\ mathbb {C}}$ , două polinoame își asumă valori identice în fiecare punct dacă și numai dacă coeficienții lor sunt egali, respectiv: dacă un termen apare în unul dintre cei doi $a_{i}x^{i}$ ${\ displaystyle a_ {i} x ^ {i}}$ ${\ displaystyle a_ {i} x ^ {i}}$ de gradul i , apoi și în celălalt va exista un termen de gradul i , cu același coeficient a _i .

În $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ , orice ar fi $n\neq 0$ ${\ displaystyle n \ neq 0}$ ${\ displaystyle n \ neq 0}$ , acest principiu nu se aplică: de exemplu putem considera, modulul 5, cele două polinoame

P(x)=x^{7}+4x^{6}

{\ displaystyle P (x) = x ^ {7} + 4x ^ {6}}

{\ displaystyle P (x) = x ^ {7} + 4x ^ {6}}

Q(x)=x^{3}-x^{2}

{\ displaystyle Q (x) = x ^ {3} -x ^ {2}}

{\ displaystyle Q (x) = x ^ {3} -x ^ {2}}

și ia în considerare valorile pe care și le asumă:

$P(0)=0\qquad \qquad Q(0)=0$ ${\ displaystyle P (0) = 0 \ qquad \ qquad Q (0) = 0}$ ${\ displaystyle P (0) = 0 \ qquad \ qquad Q (0) = 0}$

$P(1)=1+4\equiv 0\qquad Q(1)=1-1\equiv 0$ ${\ displaystyle P (1) = 1 + 4 \ equiv 0 \ qquad Q (1) = 1-1 \ equiv 0}$ ${\ displaystyle P (1) = 1 + 4 \ equiv 0 \ qquad Q (1) = 1-1 \ equiv 0}$

$P(2)=2^{7}+4\cdot 2^{6}=384\equiv 4\qquad Q(2)=8-4\equiv 4$ ${\ displaystyle P (2) = 2 ^ {7} +4 \ cdot 2 ^ {6} = 384 \ equiv 4 \ qquad Q (2) = 8-4 \ equiv 4}$ ${\ displaystyle P (2) = 2 ^ {7} +4 \ cdot 2 ^ {6} = 384 \ equiv 4 \ qquad Q (2) = 8-4 \ equiv 4}$

$P(3)=2187+2916=5103\equiv 3\qquad Q(3)=27-9=18\equiv 3$ ${\ displaystyle P (3) = 2187 + 2916 = 5103 \ equiv 3 \ qquad Q (3) = 27-9 = 18 \ equiv 3}$ ${\ displaystyle P (3) = 2187 + 2916 = 5103 \ equiv 3 \ qquad Q (3) = 27-9 = 18 \ equiv 3}$

$P(4)=16384+16384=32768\equiv 3\qquad Q(4)=64-16=48\equiv 3$ ${\ displaystyle P (4) = 16384 + 16384 = 32768 \ equiv 3 \ qquad Q (4) = 64-16 = 48 \ equiv 3}$ ${\ displaystyle P (4) = 16384 + 16384 = 32768 \ equiv 3 \ qquad Q (4) = 64-16 = 48 \ equiv 3}$

Există două motive pentru acest comportament: în primul rând, reprezentarea unui număr nu este unică, dar poate fi atât negativă, cât și pozitivă: de exemplu $-2\equiv 6\mod 8$ ${\ displaystyle -2 \ equiv 6 \ mod 8}$ ${\ displaystyle -2 \ equiv 6 \ mod 8}$ . În al doilea rând, mica teoremă a lui Fermat (și teorema lui Euler care este generalizarea sa) afirmă că $a^{p}\equiv a\mod p$ ${\ displaystyle a ^ {p} \ egal \ mod p}$ ${\ displaystyle a ^ {p} \ egal \ mod p}$ pentru fiecare a , când p este un număr prim: în consecință, fiecare exponent mai mare decât p se comportă în același mod ca un exponent mai mic, între 0 și p-1 . Cu toate acestea, putem reduce acești exponenți, astfel încât să îi aducem în acest interval: reducerea va fi efectuată ca și cum ar fi în modul p-1 , cu excepția de a nu reduce fiecare multiplu de p-1 la 0, dar lăsându-l la p- 1 . Acest lucru se datorează faptului că, în timp ce $x^{0}\equiv 1\mod p$ ${\ displaystyle x ^ {0} \ equiv 1 \ mod p}$ ${\ displaystyle x ^ {0} \ equiv 1 \ mod p}$ pentru fiecare prim p , $x^{p-1}\equiv 0$ ${\ displaystyle x ^ {p-1} \ equiv 0}$ ${\ displaystyle x ^ {p-1} \ equiv 0}$ dacă x = 0 , în timp ce este congruent cu 1 dacă $x\neq 0$ ${\ displaystyle x \ neq 0}$ $x \ neq 0$ .

Dacă respectăm aceste limitări ( n este prim, atât exponenții, cât și coeficienții aparțin intervalului $[0;~p-1]$ ${\ displaystyle [0; ~ p-1]}$ ${\ displaystyle [0; ~ p-1]}$ ) atunci principiul identității este valabil.

Și dacă modulul nu este prim, nici un principiu de acest tip nu este valabil, deoarece unele numere vor fi divizoare de 0, în timp ce altele nu.

Reducerea la o putere mai întâi

Tehnica generală de a rezolva (atât numeric cât și în raționament teoretic) un modul de congruență polinomială n implică ruperea congruenței într-un sistem de congruențe în care modulele sunt puterile numerelor prime care împart n : odată ce congruențele polinomiale unice au fost rezolvate , este apoi posibil să le „recompunem” și să identificăm soluțiile modulo n prin teorema restului chinezesc .

Cu această metodă este posibil să se exprime numărul de soluții modulo n prin numărul de soluții modulo $p_{i}^{a_{i}}$ ${\ displaystyle p_ {i} ^ {a_ {i}}}$ ${\ displaystyle p_ {i} ^ {a_ {i}}}$ (unde este $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$ ${\ displaystyle n = p_ {1} ^ {a_ {1}} p_ {2} ^ {a_ {2}} \ cdots p_ {k} ^ {a_ {k}}}$ ${\ displaystyle n = p_ {1} ^ {a_ {1}} p_ {2} ^ {a_ {2}} \ cdots p_ {k} ^ {a_ {k}}}$ este factorizarea lui n în prime distincte): dacă S ( k ) este numărul de soluții ale $f(x)\equiv 0\mod k$ ${\ displaystyle f (x) \ equiv 0 \ mod k}$ ${\ displaystyle f (x) \ equiv 0 \ mod k}$ , da $S(n)=S(p_{1}^{a_{1}})S(p_{2}^{a_{2}})\cdots S(p_{k}^{a_{k}})$ ${\ displaystyle S (n) = S (p_ {1} ^ {a_ {1}}) S (p_ {2} ^ {a_ {2}}) \ cdots S (p_ {k} ^ {a_ {k} })}$ ${\ displaystyle S (n) = S (p_ {1} ^ {a_ {1}}) S (p_ {2} ^ {a_ {2}}) \ cdots S (p_ {k} ^ {a_ {k} })}$

Acest lucru nu garantează că numărul de soluții este mai mic decât gradul polinomului și, în general, nu: de exemplu, congruența $x^{2}-1\equiv 0$ ${\ displaystyle x ^ {2} -1 \ equiv 0}$ ${\ displaystyle x ^ {2} -1 \ equiv 0}$ are două soluții modulo 4, dar patru soluții modulo 8.

În general $x^{2}-1\equiv 0{\pmod {n}}$ ${\ displaystyle x ^ {2} -1 \ equiv 0 {\ pmod {n}}}$ ${\ displaystyle x ^ {2} -1 \ equiv 0 {\ pmod {n}}}$ are un număr de soluții care depinde de factorizarea lui n, în mod explicit numărul de soluții va fi:

$2^{\omega (n)}$ ${\ displaystyle 2 ^ {\ omega (n)}}$ ${\ displaystyle 2 ^ {\ omega (n)}}$ de sine $\nu _{2}(n)=0,2$ ${\ displaystyle \ nu _ {2} (n) = 0.2}$ ${\ displaystyle \ nu _ {2} (n) = 0.2}$
$2^{\omega (n)-1}$ ${\ displaystyle 2 ^ {\ omega (n) -1}}$ ${\ displaystyle 2 ^ {\ omega (n) -1}}$ de sine $\nu _{2}(n)=1$ ${\ displaystyle \ nu _ {2} (n) = 1}$ ${\ displaystyle \ nu _ {2} (n) = 1}$
$2^{\omega (n)+1}$ ${\ displaystyle 2 ^ {\ omega (n) +1}}$ ${\ displaystyle 2 ^ {\ omega (n) +1}}$ de sine $\nu _{2}(n)>2$ ${\ displaystyle \ nu _ {2} (n)> 2}$ ${\ displaystyle \ nu _ {2} (n)> 2}$

Unde este $\nu _{2}(n)$ ${\ displaystyle \ nu _ {2} (n)}$ ${\ displaystyle \ nu _ {2} (n)}$ este o evaluare . Formule similare pot fi găsite și în cazul mai general $x^{p}-1\equiv 0{\pmod {n}}$ ${\ displaystyle x ^ {p} -1 \ equiv 0 {\ pmod {n}}}$ ${\ displaystyle x ^ {p} -1 \ equiv 0 {\ pmod {n}}}$ cu p un număr prim, caz în care numărul soluțiilor va fi o putere a lui p care va depinde de factorizarea primă a lui n.

Revenind la cazul unui modul de congruență polinomial n: $p(x)\equiv 0{\pmod {n}}$ ${\ displaystyle p (x) \ equiv 0 {\ pmod {n}}}$ ${\ displaystyle p (x) \ equiv 0 {\ pmod {n}}}$ Lagrange a fost primul care a demonstrat că, dacă n = p este un număr prim, se poate fi sigur că numărul de soluții este mai mic sau egal cu gradul polinomului; dovada urmează dovada corespunzătoare în cazul în care se află în $\mathbb {Z}$ ${\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ sau în $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ $\ mathbb {Q}$ : dacă a este o soluție a $P(x)\equiv 0$ ${\ displaystyle P (x) \ equiv 0}$ ${\ displaystyle P (x) \ equiv 0}$ , atunci poți scrie $(x-a)Q(x)\equiv 0$ ${\ displaystyle (xa) Q (x) \ equiv 0}$ ${\ displaystyle (x-a) Q (x) \ equiv 0}$ , unde Q (x) are gradul n-1 . Procedând în acest fel, ajungem fie să luăm în calcul complet P (x), fie să nu avem mai mulți factori prin care să îl împărțim; în ambele cazuri numărul soluțiilor este cel mult n . Diferența cu cazul anterior este că, dacă n este compus, $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ nu este un domeniu de integritate și, prin urmare, un număr b poate fi o soluție a lui P (x) fără a fi o soluție a (xa) sau Q (x).

Ridicarea soluțiilor

Deși nu cunoaștem o metodă generală de rezolvare a congruențelor modulo a p prim, există o procedură algoritmică recursivă simplă care ne permite să obținem, odată ce acestea sunt cunoscute, soluțiile modulo p ^k pentru fiecare k .

Se bazează pe o dezvoltare „ Taylor ” a polinomului f ( x ), utilizând conceptul de derivată formală . Având o soluție y modulo p ^k există trei cazuri:

de sine $f'(y)\not \equiv 0\mod p$ ${\ displaystyle f '(y) \ not \ equiv 0 \ mod p}$ ${\ displaystyle f '(y) \ not \ equiv 0 \ mod p}$ atunci există doar o astfel de soluție $y+tp^{k}$ ${\ displaystyle y + tp ^ {k}}$ ${\ displaystyle y + tp ^ {k}}$ , care este astfel încât apare t
$f'(y)t+{\frac {f(y)}{p^{k}}}\equiv 0\mod p$ ${\ displaystyle f '(y) t + {\ frac {f (y)} {p ^ {k}}} \ equiv 0 \ mod p}$ ${\ displaystyle f '(y) t + {\ frac {f (y)} {p ^ {k}}} \ equiv 0 \ mod p}$
de sine $f'(y)\equiv 0\mod p$ ${\ displaystyle f '(y) \ equiv 0 \ mod p}$ ${\ displaystyle f '(y) \ equiv 0 \ mod p}$ și y este o soluție modulo p ^{k + 1} , atunci $y+tp^{k}$ ${\ displaystyle y + tp ^ {k}}$ ${\ displaystyle y + tp ^ {k}}$ este o soluție pentru toate t între 0 și p -1;
de sine $f'(y)\equiv 0\mod p$ ${\ displaystyle f '(y) \ equiv 0 \ mod p}$ ${\ displaystyle f '(y) \ equiv 0 \ mod p}$ și y nu este o soluție modulo p ^{k + 1} , deci nici elementele din formă nu sunt $y+tp^{k}$ ${\ displaystyle y + tp ^ {k}}$ ${\ displaystyle y + tp ^ {k}}$ sunt soluții de f .

Congruențe liniare

O congruență liniară este o congruență polinomială de gradul I, adică sub formă

ax+b\equiv 0\mod n

{\ displaystyle ax + b \ equiv 0 \ mod n}

{\ displaystyle ax + b \ equiv 0 \ mod n}

, sau care este același,

ax\equiv b\mod n

{\ displaystyle ax \ equiv b \ mod n}

{\ displaystyle ax \ equiv b \ mod n}

Teoria acestor congruențe este foarte simplă: congruența admite soluții numai atunci când cel mai mare divizor comun dintre a și n îl divide pe b . În acest caz, numărul soluțiilor este exact $MCD(a,n)$ ${\ displaystyle MCD (a, n)}$ ${\ displaystyle MCD (a, n)}$ .

De fapt, rezolvarea congruenței este aceeași cu rezolvarea ecuației

ax-ny=b

{\ displaystyle ax-ny = b}

{\ displaystyle ax-ny = b}

în număr întreg. Din teoria ecuațiilor diofantine știm că această ecuație, liniară și în două variabile, are o soluție dacă și numai dacă $MCD(a,n)|b$ ${\ displaystyle MCD (a, n) | b}$ ${\ displaystyle MCD (a, n) | b}$ .

Sisteme de congruență liniare

Același subiect în detaliu: teorema restului chinezesc .

Se disting două tipuri de sisteme de congruență liniare: primul și cel mai important în care există o singură necunoscută și modulele sunt diferite între ele; și un al doilea în care există mai multe necunoscute modul același n : în cazul în care n = p este un număr prim, acesta din urmă poate fi rezolvat cu metodele sistemelor de ecuații liniare (exploatând faptul că $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ $\ mathbb {Z} _p$ este un câmp ); pentru orice n o condiție suficientă este ca determinantul matricei asociate să fie coprimă cu n .

Primul caz are o mare importanță teoretică și practică, deoarece permite atât unificarea congruențelor diferite într-o singură congruență, cât și divizarea unui modul n într-un sistem modulo p ^k , pentru p distinct mai întâi, rezolvați-le și apoi reveniți la original modul. De sine

\{x\equiv a_{i}\mod n_{i}\quad \mathrm {per} \;i=1,\ldots ,k.

{\ displaystyle \ {x \ equals_ {i} \ mod n_ {i} \ quad \ mathrm {per} \; i = 1, \ ldots, k.}

{\ displaystyle \ {x \ equals_ {i} \ mod n_ {i} \ quad \ mathrm {per} \; i = 1, \ ldots, k.}

iar n _i sunt primele dintre ele, atunci există o soluție modulo unică $n=n_{1}n_{2}\cdots n_{k}$ ${\ displaystyle n = n_ {1} n_ {2} \ cdots n_ {k}}$ ${\ displaystyle n = n_ {1} n_ {2} \ cdots n_ {k}}$ ; mai general, o condiție necesară și suficientă pentru a exista o soluție de un singur modul $n=\mathrm {mcm} (n_{1},n_{2},\ldots ,n_{k})$ ${\ displaystyle n = \ mathrm {mcm} (n_ {1}, n_ {2}, \ ldots, n_ {k})}$ ${\ displaystyle n = \ mathrm {mcm} (n_ {1}, n_ {2}, \ ldots, n_ {k})}$ este că, pentru fiecare pereche de i și j diferită una de cealaltă, GCD ( n _i , n _j ) împarte diferența a _i - a _j .

Extracția rădăcinilor

Capacitatea de a rezolva congruențe de tip

X^{m}\equiv a\mod p^{k}

{\ displaystyle X ^ {m} \ egal \ mod p ^ {k}}

{\ displaystyle X ^ {m} \ egal \ mod p ^ {k}}

(adică să vrea să găsească o „rădăcină m- lea“ de a) pot fi abordate , în parte datorită existenței rădăcinilor primitive modulo p ^k (pentru p primul nui adevărat), adică, datorită faptului că grupul de unități de $\mathbb {Z} _{p^{k}}$ ${\ displaystyle \ mathbb {Z} _ {p ^ {k}}}$ ${\ displaystyle \ mathbb {Z} _ {p ^ {k}}}$ este ciclic . Dacă a este coprimă cu p , acest lucru ne permite să transformăm congruența în

r^{mT}\equiv r^{k}\mod p^{k}

{\ displaystyle r ^ {mT} \ equiv r ^ {k} \ mod p ^ {k}}

{\ displaystyle r ^ {mT} \ equiv r ^ {k} \ mod p ^ {k}}

(unde r este o rădăcină primitivă e $r^{s}\equiv a\mod p^{k}$ ${\ displaystyle r ^ {s} \ egal \ mod p ^ {k}}$ ${\ displaystyle r ^ {s} \ egal \ mod p ^ {k}}$ ) care la rândul său este echivalent cu

mT\equiv s\mod \phi (p^{k})

{\ displaystyle mT \ equiv s \ mod \ phi (p ^ {k})}

{\ displaystyle mT \ equiv s \ mod \ phi (p ^ {k})}

unde φ indică funcția lui Euler phi . Această din urmă congruență este rezolvabilă dacă și numai dacă cel mai mare divizor comun d între m și s se împarte $\phi (p^{k})=p^{k-1}(p-1)$ ${\ displaystyle \ phi (p ^ {k}) = p ^ {k-1} (p-1)}$ ${\ displaystyle \ phi (p ^ {k}) = p ^ {k-1} (p-1)}$ , și în acest caz are soluții d ; în special dacă m este coprimă cu p -1, congruența este întotdeauna rezolvabilă și are o singură soluție. Dacă, pe de altă parte, a nu este coprimă cu p , soluțiile posibile sunt, de asemenea, divizibile cu p și, prin urmare, ne putem reduce la un modul de congruență p ^j , cu j < k , în care termenul cunoscut este coprimă cu modulo.

Cu toate acestea, această metodă este ineficientă pentru calcularea efectivă a soluțiilor și chiar pentru a ști dacă există soluții pentru un anumit a , deoarece se bazează pe calculul unui modulo rădăcină primitiv p , pentru care nu se cunoaște niciun algoritm eficient. Pentru a determina posibila existență a soluțiilor, totuși, ne putem baza pe legea reciprocității pătratice (în cazul m = 2) sau pe legile reciprocității pentru exponenții majori.

Congruențe quadratice

Congruențele pătratice (adică congruențele polinomiale de gradul al doilea) pot fi reduse în mare măsură la extragerea unei rădăcini pătrate modulo p ^k : aplicând aceeași procedură care este utilizată pentru a găsi formula soluției (a se vedea ecuația de gradul II ), de fapt, puteți treci pe lângă

x^{2}+bx+c\equiv 0\mod p

{\ displaystyle x ^ {2} + bx + c \ equiv 0 \ mod p}

{\ displaystyle x ^ {2} + bx + c \ equiv 0 \ mod p}

la

(x+b2^{-1})^{2}+c-b^{2}2^{-2}\equiv 0\mod p

{\ displaystyle (x + b2 ^ {- 1}) ^ {2} + cb ^ {2} 2 ^ {- 2} \ equiv 0 \ mod p}

{\ displaystyle (x + b2 ^ {- 1}) ^ {2} + c-b ^ {2} 2 ^ {- 2} \ equiv 0 \ mod p}

adică

4(x+b2^{-1})^{2}\equiv b^{2}-4c\mod p

{\ displaystyle 4 (x + b2 ^ {- 1}) ^ {2} \ equiv b ^ {2} -4c \ mod p}

{\ displaystyle 4 (x + b2 ^ {- 1}) ^ {2} \ equiv b ^ {2} -4c \ mod p}

De sine $b^{2}-4c$ ${\ displaystyle b ^ {2} -4c}$ ${\ displaystyle b ^ {2} -4c}$ este un reziduu pătratic , congruența originală va avea două soluții (posibil coincidente); dacă nu este, nici congruența originală nu va putea fi rezolvată.

Congruențe în mai multe necunoscute

Același subiect în detaliu: teorema lui Chevalley .

O proprietate interesantă, ne posedată de câmpuri infinite, este atunci când se examinează congruențe în mai multe necunoscute. De fapt, teorema lui Chevalley afirmă că dacă numărul necunoscutelor depășește gradul polinomului și nu există un termen constant, atunci există o altă soluție decât cea banală $(0,0,\ldots ,0)$ ${\ displaystyle (0,0, \ ldots, 0)}$ ${\ displaystyle (0,0, \ ldots, 0)}$ . În $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ acest lucru nu este adevărat: luați ca exemplu polinomul $x^{2}+y^{2}+z^{2}$ ${\ displaystyle x ^ {2} + y ^ {2} + z ^ {2}}$ ${\ displaystyle x ^ {2} + y ^ {2} + z ^ {2}}$ , care ia întotdeauna valori pozitive, cu excepția cazului în care cele trei variabile sunt egale cu 0.

Bibliografie

Harold Davenport , Arithmetic Superior , Zanichelli, Bologna, 1994, ISBN 8808091546 , capitolul 2
Andrew Adler și John E. Coury, The Theory of Numbers , Jones and Bartlett Publishers, Sudbury, 1995, ISBN 0-86720-472-9 , capitolul 4

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