Congruenze polinomiali non lineari

Frank Lioty
Buonasera a tutti. Sto incontrando un po' di difficoltà con il tipo di congruenza in oggetto. Nelle dispense del mio professore non se ne fa esplicitamente riferimento, quindi ho cercato in Rete ma non trovo niente di univocamente funzionante. Ammettiamo di avere una congruenza nella forma

$ f(x) -= 0 (m) $

dove $ f(x) $ è un polinomio in x a coefficienti interi. Esiste un modo univoco, possibilmente attuabile senza l'uso della calcolatrice (stupide regole d'esame), per risolvere tale congruenza a prescindere dalla grandezza di m e il grado di $ f(x) $ ?

Il metodo più intuitivo trovato finora è il seguente:

- fattorizzo m, ottenendo i fattori primi, quindi $ m=p^{a_1}_1p^{a_2}_2p^{a_3}_3...p^{k}_k $ e metto a sistema le congruenze della forma $ f(x) -= 0 (p^{i}_i) $ per $ i=0, 1, 2, 3, ...k $

- a questo punto so che ciascuna congruenza avendo come modulo un numero primo ha alpiù n soluzioni, dove n è il grado del polinomio

- calcolo tutti i valori del polinomio prendendo $ x=0, 1, 2, 3, ... p-1 $ e considerando soluzioni quelle che danno resto 0. Per semplificare il calcolo posso considerare le $ -p/2 \leq x \leq p/2 $

- chiamiamo $ s_1, s_2, s_i $ le soluzioni di ciascuna congruenza a sistema, con $ i \leq n $ e costruiamo un sistema per ciascuna combinazione fra tutte le soluzioni, mettendo a sistema le congruenze nella forma $ x -= s_i (p) $ con p modulo della congruenza di cui è soluzione

- risolviamo i singoli sistemi trovando così tutte le soluzioni della congruenza iniziale

------------------------------------------------------------------------------------------------------------------

Passo ad un esempio:

$ x^3 + 2x^2 -1 -= 0 (10) $

scompongo 10 nei suoi fattori primi $ 5 $ e $ 2 $ e costruisco il sistema corrispondente:

$ { ( x^3 + 2x^2 - 1 -= 0 (2) ),( x^3 + 2x^2 - 1 -= 0 (5) ):} $

che posso riscrivere nella forma:

$ { ( x^3 - 1 -= 0 (2) ),( x^3 + 2x^2 - 1 -= 0 (5) ):} $

per ciascuna congruenza controllo i possibili valori di x ($ 0, 1 $) per la prima e ($ -2, -1, 0, 1, 2 $ corrispondenti a $ 0, 1, 2, 3, 4 $). La prima congruenza ha soluzione (è congrua a 0) per $ x = 1 $, mentre la seconda ha due soluzioni: $ x = -1 $ e $ x = 2 $. Costruisco quindi i sistemi per ciascuna combinazione, ovvero i 2 sistemi:

$ { ( x -= 1 (2) ),( x -= -1 (5) ):} $ e $ { ( x -= 1 (2) ),( x -= 2 (5) ):} $

ciascun sistema avrà una ed una sola soluzione modulo m, poiché le congruenze hanno per modulo numeri primi ed $ MCD(p_1, p_2) = 1 $ sempre. Facendo i calcoli del caso otterremo le soluzioni $ x = 7 $ e $ x = 9 $ modulo $ m $.

--------------------------------------------------------------------------------------------

Tutto questo però inizia maledettamente a complicarsi nel caso in cui m si scomponga in parecchi fattori primi, specie piuttosto grossi. Penso ad esempio ad una congruenza con $ mod 34 $ (fattori $ 2 $ e $ 17 $). Toccherebbe controllare tutte le $ -8 \leq x \leq 8 $, non proprio agevole (e ho considerato un fattore primo ancora "ragionevole"). Allo stesso tempo potrebbero venir fuori parecchie soluzioni, quindi un numero potenzialmente spropositato di sistemi di combinazioni. Insomma assolutamente infattibile.
Qualcuno sa darmi qualche dritta per migliorare tale procedimento o indicarmene uno semplice e fattibile, ripeto, senza calcolatrice, "universalmente" applicabile?

Grazie mille

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.