Congruenze polinomiali

Da Wikipedia, l'enciclopedia libera.

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

$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\equiv 0\mod n$

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

Le proprietà di questi polinomi differisce 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.

Indice

1 Teoremi fondamentali
2 Congruenze lineari
- 2.1 Sistemi di congruenze lineari
3 Congruenze quadratiche
4 Bibliografia

[modifica] Teoremi fondamentali

[modifica] 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, questo principio non si applica: ad esempio si possono considerare, modulo 5, i due polinomi

P (x) = x 7 + 4 x 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, mentra altri no.

[modifica] Numero di soluzioni

Anche qui si distinguono due casi: se n è primo oppure se è composto. In quest'ultimo caso ci si può ricondurre a casi in cui il modulo è primo; ad esempio, se cerchiamo le soluzioni di $P(x)\equiv 0\mod n$ , se $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ (i p<subi sono primi distinti), e se indichiamo con $S (n)$ il numero di soluzioni di P(x) modulo n, si avrà $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; anzi, questo in genere non succede: per esempio la congruenza

$x^2-1\equiv 0$

ha due soluzioni modulo 4, quattro soluzioni modulo 8 e ben otto soluzioni modulo 12.

Se invece n=p è un numero primo, si può essere sicuri che il numero delle soluzioni non è minore o uguale del grado: 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).

[modifica] Congruenze in più incognite

Per approfondire, vedi la voce Teorema di Chevalley.

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.

[modifica] 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

a x - n y = 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.

[modifica] Sistemi di congruenze lineari

Per approfondire, vedi la voce Teorema cinese del resto.

[modifica] Congruenze quadratiche

Una congruenza quadratica è una congruenza polinomiale di secondo grado, ovvero nella forma

$ax^2+bx+c\equiv 0\mod n$

Se n è un numero primo, può essere applicato il medesimo procedimento che si usa per trovare la formula risolutiva (vedi Equazione di secondo grado): quindi si avrà

$x_{1,2}\equiv\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\mod n$

Per risolvere la radice quadrata, bisognerà risolvere la congruenza

$x^2\equiv b^2-4ac\mod n$

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

[modifica] Bibliografia

H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo II

Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica

Categorie: Aritmetica modulare | Polinomi