# Aritmetica modulare/Polinomi in aritmetica modulare

Aritmetica modulare
Copertina Bibliografia Tutti i moduli · Sviluppo
    CopertinaAritmetica modulare/Copertina
* La relazione di congruenzaAritmetica modulare/La relazione di congruenza
* Prime proprietà e applicazioniAritmetica modulare/Prime proprietà e applicazioni
* Congruenze lineariAritmetica modulare/Congruenze lineari
* Polinomi in aritmetica modulareAritmetica modulare/Polinomi in aritmetica modulare
* Radici primitiveAritmetica modulare/Radici primitive
* Congruenze quadraticheAritmetica modulare/Congruenze quadratiche
* Alcune applicazioniAritmetica modulare/Alcune applicazioni
* BibliografiaAritmetica modulare/Bibliografia
* EserciziAritmetica modulare/Esercizi
Modifica il sommario
Questo modulo tratta delle proprietà dei polinomi in aritmetica modulare. In particolare, verrà dimostrato il teorema di Waring sul numero di soluzioni di una congruenza polinomiale in più incognite.

## Modulo primo contro modulo composto

Quando considerati in aritmetica modulare, i polinomi possono presentare proprietà inusuali e controintuitive. Lo stesso piccolo teorema di Fermat ne è un esempio: può essere infatti interpretato dicendo che, dato un primo p, i polinomi $x^{p}$ e x (che sono, formalmente, distinti) assumono sempre lo stesso valore quando considerati modulo p. Questo non può avvenire quando sono considerati polinomi a coefficienti reali o razionali, ma permette invece di ridurre il grado di un polinomio, se questo è maggiore di p, senza cambiare i valori che questo assume e, di conseguenza, i valori per cui il polinomio si annulla.
Altri fenomeni riguardo al rapporto tra il numero di zeri di un polinomio e il suo grado: se infatti in ambienti "usuali" come i polinomi reali o razionali il numero di soluzioni non può superare il grado del polinomio, questo non sempre avviene in aritmetica modulare: un esempio semplice è $P(x)=x^{2}-1$ che, se considerato modulo 8, ha quattro soluzioni distinte, e cioè 1, 3, 5 e 7. Questo deriva dal fatto che $\mathbb {Z} _{8}$ non è un dominio d'integrità: infatti normalmente, fattorizzando P(x) come $(x-1)(x+1)$, gli unici zeri del polinomio sarebbero in 1 e -1, cioè (in questo caso) in 1 e 7. Tuttavia, non è necessario che uno dei due fattori sia zero perché sia zero il prodotto: in questo caso, $P(3)=2\cdot 4\equiv 0\mod 8$.
Da quanto detto appare chiaro che, trasferendosi in $\mathbb {Z} _{p}$, dove p è un numero primo, si ottiene la stessa situazione dei razionali o dei reali. La dimostrazione è la stessa che in questi ultimi casi: dato P(x) di grado n, se P(a)=0, allora (x - a) divide P(x); se ora ci fossero n +1 (o più) radici, il polinomio formato dal prodotto dei vari (x - a) sarebbe di grado n +1 e dovrebbe dividere P(x), il che è impossibile. Quindi possono esistere al massimo n zeri.
Questo permette di dimostrare che, dati due polinomi P(x) e Q(x) di grado minore di p, se sono distinti, non possono avere lo stesso valore ovunque (modulo p): infatti il polinomio differenza R(x)=P(x)- Q(x) avrebbe un grado compreso tra 0 e p -1, ma p soluzioni, il che è impossibile.
Questa proprietà, unita alla "scomposizione" di una congruenza in altri moduli tra loro comprimi rende particolarmente importante la soluzione di congruenze polinomiali quando il modulo è primo. Congruenze generiche in più incognite verranno trattare successivamente in questo capitolo, mentre uno studio approfondito delle congruenze quadratiche in un'unica incognita è l'argomento dell'ultimo capitolo.

## Il teorema di Chevalley

Supponiamo di avere un polinomio in n incognite $P(x_{1},x_{2},\ldots ,x_{n})$ di grado g (cioè tale che g è il massimo grado tra quelli dei monomi, dopo che il grado di ogni incognita è già stato ridotto ad essere minore di p), tale che n > g, e supponiamo che $P(0,0,\ldots ,0)\equiv 0\mod p$, ovvero che non ci sia un termine noto. Il teorema di Chevalley afferma che esiste almeno un'altra soluzione della congruenza.
Per dimostrarlo, ragioniamo per assurdo, e supponiamo che esista un'unica soluzione. Costruiamo i due nuovi polinomi (dove X denota la n-upla $(x_{1},x_{2},\ldots ,x_{n})$)
    $f(X)=1-[P(X)]^{p-1}$
    $g(X)=(1-x_{1}^{p-1})(1-x_{2}^{p-1})\ldots (1-x_{n}^{p-1})$
Se X è la n-upla nulla, allora f(X)=1, e così g(X), perché tutti i fattori sono uguali a 1. Se invece almeno uno tra gli $x_{i}$ è diverso da 0, allora g(X)=0 perché il fattore $(1-x_{i}^{p-1})$ è uguale a 0; d'altra parte, si ha anche $P(X)\equiv 1$, perché P(X) è diverso da 0 (l'unica soluzione è quella nulla) e si può applicare il piccolo teorema di Fermat. Quindi i due polinomi assumono sempre lo stesso valore modulo p.
Consideriamo ora i loro gradi. g(X) ha grado n(p -1), perché esiste un monomio in cui tutte le incognite hanno grado p -1, e non possono quindi essere ridotte. Il grado di f(X), d'altra parte, non può essere più di g(p -1) (potrebbe essere strettamente minore, in quanto ci si può trovare a dover ridurre il grado di un'incognita per farlo diventare minore di p); quindi f(X) ha grado strettamente minore di g(X): poiché il grado in ogni incognita è minore di p, f(X) e g(X) non possono però assumere sempre lo stesso valore, perché i loro gradi sono diversi.
Abbiamo quindi una contraddizione, che è dovuta all'aver supposto che esiste un'unica soluzione. Di conseguenza, esiste almeno un'altra n -upla che risolve la congruenza.

## Generalizzazioni

Il teorema di Chevalley può essere generalizzato.
Infatti, supponiamo che l'unica soluzione conosciuta non sia quella nulla (0,0,...,0), ma una generica $(a_{1},a_{2},\ldots ,a_{n})$, e che P(X) abbia comunque grado minore del numero di incognite. In questo caso, per dimostrare che esiste un'altra soluzione, è sufficiente variare la definizione di g(X): $g(X)=[1-(x_{1}-a_{1})^{p-1}][1-(x_{2}-a_{2})^{p-1}]\ldots [1-(x_{n}-a_{n})^{p-1}]$
La situazione è esattamente quella precedente: g(X)=1 se e solo se $X=(a_{1},a_{2},\ldots ,a_{n})$, mentre altrimenti è uguale a 0, così come f(X). Inoltre il loro grado è rispettivamente n(p -1) e un numero minore o uguale di g(p -1): quindi non possono essere uguali, e i due polinomi non possono coincidere, il che è assurdo perché hanno sempre lo stesso valore. Quindi esiste almeno un'altra soluzione.
Un teorema molto più forte è invece il teorema di Waring. Esso afferma che, nelle stesse condizioni di questa prima generalizzazione (grado minore del numero di incognite, esistenza di almeno una soluzione) il numero di soluzioni è divisibile per p. Supponiamo infatti che ci siano m soluzioni $X_{1},X_{2},\ldots ,X_{m}$, e costruiamo i polinomi
    $g(X_{i})=[1-(x_{1}-a_{1}^{i})^{p-1}][1-(x_{2}-a_{2}^{i})^{p-1}]\ldots [1-(x_{n}-a_{n}^{i})^{p-1}]$
dove $a_{j}^{i}$ indica la j-esima componente di $X_{i}$, e li sommiamo insieme, costruendo
    $g(X)=g(X_{1})+g(X_{2})+\ldots +g(X_{m})$
Quando X è una delle soluzioni, g(X) è uguale a 1, perché il corrispondente $g(X_{i})$ è uguale a 1, mentre gli altri sono uguali a 0; se invece X non è una delle soluzioni, tutti gli addendi sono uguali a 0, e quindi anche g(X).
Come prima, costruiamo anche
    $f(X)=1-[P(X)]^{p-1}$
che ha grado minore o uguale di g(p -1), e assume sempre lo stesso valore di g(X). Ora in g(X) vi sono m fattori del tipo $x_{1}^{p-1}x_{2}^{p-1}\ldots x_{n}^{p-1}$ che sono di grado n(p -1). Ma i due gradi devono essere uguali, quindi il monomio di grado n(p -1) di g(X) deve annullarsi, cioè si deve avere
    $mx_{1}^{p-1}x_{2}^{p-1}\ldots x_{n}^{p-1}\equiv 0\mod p$
per ogni scelta degli $x_{i}$. perché sia possibile, si deve avere $m\equiv 0\mod p$, cioè m deve essere divisibile per p. Ma siccome m era stato definito come il numero di soluzioni di P(X), si ha che queste ultima sono in numero divisibile per p, come volevasi dimostrare.