Congruenza polinomiale

Una congruenza polinomiale, o congruenza algebrica, è una congruenza del tipo

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

dove n è un qualsiasi intero maggiore o uguale a 2.

Le proprietà di questi polinomi differiscono in molti casi radicalmente rispetto alle proprietà possedute, ad esempio, negli interi o nei razionali; in altri casi valgono invece teoremi simili se non identici.

Proprietà generali

Principio di identità dei polinomi

In $\mathbb {Z}$, $\mathbb {Q}$, $\mathbb {R}$ e $\mathbb {C}$, due polinomi assumono valori identici in ogni punto se e solo se i loro coefficienti sono rispettivamente uguali: ovvero se in uno dei due compare un termine $a_{i}x^{i}$di grado i, allora anche nell'altro sarà presente un termine di grado i, con lo stesso coefficiente a_i.

In $\mathbb {Z} _{n}$, qualunque sia $n\neq 0$, questo principio non si applica: ad esempio si possono considerare, modulo 5, i due polinomi

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

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

e considerare i valori che assumono:

$P(0)=0\qquad \qquad Q(0)=0$

$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$

$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$

Le ragioni di questo comportamento sono due: primo, la rappresentazione di un numero non è unica, ma può essere sia negativa che positiva: ad esempio $-2\equiv 6\mod 8$. In secondo luogo, il piccolo teorema di Fermat (e il teorema di Eulero che è la sua generalizzazione) afferma che $a^{p}\equiv a\mod p$ per ogni a, quando p è un numero primo: di conseguenza ogni esponente maggiore di p si comporta nello stesso modo di un esponente più piccolo, compreso tra 0 e p-1. Possiamo però ridurre questi esponenti, in modo da portarli in questo intervallo: la riduzione sarà compiuta come se si fosse in modulo p-1, con l'eccezione di non ridurre ogni multiplo di p-1 a 0, ma di lasciarlo a p-1. Questo perché, mentre $x^{0}\equiv 1\mod p$ per ogni primo p, $x^{p-1}\equiv 0$ se x=0, mentre è congruo a 1 se $x\neq 0$.

Se rispettiamo queste limitazioni (n è primo, sia gli esponenti che i coefficienti appartengono all'intervallo $[0;~p-1]$) allora il principio di identità è valido.

Se poi il modulo non è primo, non vale neppure un principio di questo tipo, in quanto alcuni numeri saranno divisori dello 0, mentre altri no.

Riduzione a una potenza prima

La tecnica generale per risolvere (sia numericamente che in ragionamenti teorici) una congruenza polinomiale modulo n prevede di spezzare la congruenza in un sistema di congruenze in cui i moduli siano le potenze dei numeri primi che dividono n: una volta risolte le singole congruenze polinomiali, è possibile poi "ricomporle" ed individuare le soluzioni modulo n attraverso il teorema cinese dei resti.

Con questo metodo è possibile esprimere il numero di soluzioni modulo n attraverso il numero di soluzioni modulo $p_{i}^{a_{i}}$ (dove $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$ è la fattorizzazione di n in primi distinti): se S(k) è il numero di soluzioni di $f(x)\equiv 0\mod k$, si ha $S(n)=S(p_{1}^{a_{1}})S(p_{2}^{a_{2}})\cdots S(p_{k}^{a_{k}})$

Questo non garantisce che il numero di soluzioni sia minore del grado del polinomio, e in genere non succede: per esempio la congruenza $x^{2}-1\equiv 0$ ha due soluzioni modulo 4 ma quattro soluzioni modulo 8.

In generale $x^{2}-1\equiv 0{\pmod {n}}$ possiede un numero di soluzioni che dipende dalla fattorizzazione di n, esplicitamente il numero di soluzioni sarà:

• $2^{\omega (n)}$ se $\nu _{2}(n)=0,2$
• $2^{\omega (n)-1}$ se $\nu _{2}(n)=1$
• $2^{\omega (n)+1}$ se $\nu _{2}(n)>2$

Dove $\nu _{2}(n)$ è una valutazione. Formule simili si possono trovare anche nel caso più generale $x^{p}-1\equiv 0{\pmod {n}}$ con p un numero primo, caso nel quale il numero di soluzioni sarà una potenza di p che dipenderà dalla fattorizzazione in primi di n.

Ritornando al caso di una congruenza polinomiale modulo n: $p(x)\equiv 0{\pmod {n}}$ Lagrange per primo dimostrò che se n = p è un numero primo, si può essere sicuri che il numero delle soluzioni sia minore o uguale al grado del polinomio; la dimostrazione ricalca la corrispondente dimostrazione nel caso di trovarsi in $\mathbb {Z}$ o in $\mathbb {Q}$: se a è una soluzione di $P(x)\equiv 0$, allora si può scrivere $(x-a)Q(x)\equiv 0$, dove Q(x) ha grado n-1. Procedendo in questo modo si arriva o a fattorizzare completamente P(x) oppure a non avere più fattori per cui dividerlo; in entrambi i casi il numero di soluzioni è al più n. La differenza con il caso precedente è che, se n è composto, $\mathbb {Z} _{n}$ non è un dominio d'integrità, e quindi un numero b può essere soluzione di P(x) senza esserlo né di (x-a) né di Q(x).

Sollevamento delle soluzioni

Sebbene non si conosca un metodo generale per risolvere le congruenze modulo un primo p, esiste un semplice procedimento algoritmico ricorsivo che permette di ricavare, una volta note queste, le soluzioni modulo p^k per ogni k.

Esso si basa su uno sviluppo "alla Taylor" del polinomio f(x), usando il concetto di derivata formale. Data una soluzione y modulo p^k si hanno tre casi:

• se $f'(y)\not \equiv 0\mod p$ allora esiste un'unica soluzione del tipo $y+tp^{k}$, che è tale che t verifica

  $f'(y)t+{\frac {f(y)}{p^{k}}}\equiv 0\mod p$

• se $f'(y)\equiv 0\mod p$ e y è una soluzione modulo p^k+1, allora $y+tp^{k}$ è una soluzione per tutti i t compresi tra 0 e p -1;
• se $f'(y)\equiv 0\mod p$ e y non è una soluzione modulo p^k+1, allora neppure gli elementi nella forma $y+tp^{k}$ sono soluzioni di f.

Congruenze lineari

Una congruenza lineare è una congruenza polinomiale di primo grado, ovvero nella forma

$ax+b\equiv 0\mod n$, o il che è lo stesso, $ax\equiv b\mod n$

La teoria di queste congruenze è molto semplice: la congruenza ammette soluzioni soltanto quando il massimo comun divisore tra a ed n divide b. In questo caso il numero delle soluzioni è precisamente $MCD(a,n)$.

Infatti risolvere la congruenza equivale a risolvere l'equazione

$ax-ny=b$

in numeri interi. Dalla teoria delle equazioni diofantee sappiamo che questa equazione, lineare e in due variabili, ha soluzione se e soltanto se $MCD(a,n)|b$.

Sistemi di congruenze lineari

Si distinguono due tipi di sistemi di congruenze lineari: il primo e più importante in cui si ha un'unica incognita e i moduli sono diversi tra loro; e un secondo in cui si hanno più incognite modulo lo stesso n: nel caso che n = p sia un numero primo, quest'ultima può essere risolta con i metodi dei sistemi di equazioni lineari (sfruttando il fatto che $\mathbb {Z} _{p}$ è un campo); per n qualsiasi una condizione sufficiente è che il determinante della matrice associata sia coprimo con n.

Il primo caso è di grande importanza sia teorica che pratica, perché permette sia di unificare diverse congruenze in un'unica congruenza sia di spezzarne una modulo n in un sistema modulo p^k, per p primi distinti, risolvere queste e quindi risalire al modulo originario. Se

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

e gli n_i sono primi tra loro, allora esiste un'unica soluzione modulo $n=n_{1}n_{2}\cdots n_{k}$; più in generale, una condizione necessaria e sufficiente perché esista un'unica soluzione modulo $n=\mathrm {mcm} (n_{1},n_{2},\ldots ,n_{k})$ è che, per ogni coppia di i e j diversi tra loro l'MCD(n_i,n_j) divida la differenza a_i - a_j.

Estrazione di radici

La possibilità di risolvere le congruenze del tipo

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

(ovvero di voler trovare una "radice m-esima" di a) può essere affrontata in parte grazie all'esistenza delle radici primitive modulo p^k (per p primo dispari), ovvero grazie al fatto che il gruppo delle unità di $\mathbb {Z} _{p^{k}}$ è ciclico. Se a è coprimo con p, questo permette infatti di trasformare la congruenza in

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

(dove r è una radice primitiva e $r^{s}\equiv a\mod p^{k}$) che a sua volta è equivalente a

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

dove φ indica la funzione phi di Eulero. Quest'ultima congruenza è risolubile se e solo se il massimo comun divisore d tra m e s divide $\phi (p^{k})=p^{k-1}(p-1)$, e in tal caso ha d soluzioni; in particolare se m è coprimo con p -1 la congruenza è sempre risolubile e ha una sola soluzione. Se invece a non è coprimo con p, anche le eventuali soluzioni sono divisibili per p, e quindi ci si può ridurre ad una congruenza modulo p^j, con j < k, in cui il termine noto è coprimo con il modulo.

Questo metodo è tuttavia inefficace per il calcolo effettivo delle soluzioni e perfino per sapere se esistono soluzioni per un determinato a, perché si basa sul calcolo di una radice primitiva modulo p, per cui non è noto alcun algoritmo efficace. Per determinare l'eventuale esistenza delle soluzioni ci si può però basare sulla legge di reciprocità quadratica (nel caso m = 2) o nelle leggi di reciprocità per esponenti maggiori.

Congruenze quadratiche

Le congruenze quadratiche (ovvero le congruenze polinomiali di secondo grado) possono essere in gran parte ridotte all'estrazione di una radice quadrata modulo p^k: applicando il medesimo procedimento che si usa per trovare la formula risolutiva (vedi Equazione di secondo grado), infatti, si può ottenere passare da

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

a

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

ovvero

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

Se $b^{2}-4c$ è un residuo quadratico, la congruenza originaria avrà due soluzioni (eventualmente coincidenti); se non lo è, neppure la congruenza originaria sarà risolubile.

Congruenze in più incognite

Una proprietà interessante, non posseduta dai campi infiniti, si ha quando si esaminano congruenze in più incognite. Il teorema di Chevalley asserisce infatti che se il numero di incognite supera il grado del polinomio, e non è presente un termine costante, allora esiste un'altra soluzione diversa da quella banale $(0,0,\ldots ,0)$. In $\mathbb {R}$ questo non è vero: basta prendere ad esempio il polinomio $x^{2}+y^{2}+z^{2}$, che assume sempre valori positivi eccetto quando le tre variabili sono uguali a 0.

Bibliografia

• Harold Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546, capitolo 2
• Andrew Adler e John E. Coury, The Theory of Numbers, Jones and Bartlett Publishers, Sudbury, 1995, ISBN 0-86720-472-9, capitolo 4

Collegamenti esterni

• (EN) Eric W. Weisstein, Congruenza polinomiale, su MathWorld, Wolfram Research.
• (EN) Congruenza polinomiale, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.