OliForum Matematico

Sia $ P(x) $ un polinomio di grado $ b $ a coefficienti unitari.
Come si dimostra che $ P(x) \equiv 0 (p) $ ha al massimo $ b $ soluzioni (intese modulo $ p $)?

consiglio: prendi la dimostrazione dello stesso teorema, per i razionali/reali/complessi, e prova a vedere dove ti blocchi/dove non ti blocchi/che ipotesi usi in ogni passaggio/cosa non funziona mod n/cosa funziona mod p ma non mod n, ecc...

Eh ci avevo provato ma non ci sono riuscito..:
Per i complessi va tutto bene perchè se $ P(x) $ ha $ n+1 $ soluzioni e $ \deg P(x)=n $ allora $ P(x)=(x- \lambda_1)(x- \lambda_2)...(x- \lambda_{n+1}) $ per il teorema fondamentale dell'algebra, ma allora $ P(x)=Q(x) \forall x $ con $ \deg Q(x)= n+1 $ e questo è assurdo perchè $ Q(x)-P(x)=0 $ è un polinomio di grado $ n+1 $ e perciò (ancora teorema fondamentale dell'algebra) ha solo $ n+1 $ soluzioni e perciò non vale $ \forall x $

Provo a fare lo stesso con le congruenze: se $ P(x) \equiv 0 \pmod{p} $ avesse $ n+1 $ soluzioni allora $ P(x) \equiv Q(x) \pmod{p} \forall x $ con $ Q(x) $ di grado $ n+1 $ ma il fatto che 2 polinomi siano congruenti $ \forall x $ non è affatto assurdo (per esempio $ x \equiv x^3 \pmod{3} $ per FLT) e mi blocco.

ti ho modificato un po' il TeX qua e là...
comunque. ti serve davvero usare il teorema fondamentale dell'algebra per i reali/razionali/complessi?
prova a far finta di non sapere il teorema fondamentale dell'algebra, e vedi se riesci a trovare una dimostrazione (i pezzi sono già lì).

Ok ci provo per induzione sul numero massimo di valori che soddisfano la congruenza:

Premessa: Per tutta la dimostrazione dirò che un polinomio $ P(x) $ ha grado $ g \pmod{k} $ se e solo se $ g $ è il più grande esponente dei monomi in $ x $ che non hanno per coefficiente un multiplo di $ k $

Passo base: $ x \equiv u \pmod{n} $ ha chiaramente 1 soluzione $ \pmod{n} $
Ipotesi induttiva: Suppongo che un polinomio di grado $ n $ sia congruo $ 0 \pmod{n} $ in massimo $ n $ valori (intesi sempre $ \pmod{n} $).
Passo induttivo: mostro che ogni polinomio di grado $ n+1 $ è congruo $ 0 \pmod{n} $ in massimo $ n+1 $ valori.
Infatti sia $ Q(x) $ un polinomio di grado $ n+1 $ e sia $ \lambda_1 $ una sua radice. Allora posso scrivere $ Q(x)=(x-\lambda_1)a(x) $ e so che $ \deg a(x)=n $. Allora $ Q(x) \equiv 0 \pmod{n} $ è equivalente a $ (x-\lambda_1)a(x) \equiv 0 \pmod{n} $ ma il primo termine ha una soluzione mentre $ a(x) $ ne ha al massimo $ n $, quindi il massimo di soluzioni che può avere $ Q(x) $ è $ n+1 $.

Corretto?

posto che quando scrivi (mod n) in realtà intendi (mod k) funziona tutto.
un altro metodo un po' più diretto è:
supponiamo esista un polinomio di grado n con n+k soluzioni.
lo scomponiamo con ruffini e lo rimoltiplichiamo insieme, otteniamo qualcosa che ha grado multiplo di n+k (detto velocemente)

no, Spammowarrior, così non funziona.

prima che arrivasse Spammowarrior, ma_go ha scritto:hai fatto un po' di casino con i moduli/gradi..
comunque, no, non è corretto.
nello specifico, chiediti cosa c'è che non va col polinomio $x(x-1)(x-2)$ modulo 6.

vediamo se riesco ad essere più chiaro:

Testo nascosto:

nei polinomi che vuoi considerare (mod p) c'è la fattorizzazione unica, mentre nei polinomi mod n (se n non è primo) non c'è la fattorizzazione unica, e questo crea qualche inghippo quando provi ad applicare ruffini come fai tu.

hai ragione, ero convinto di essere su un campo...

edit: aspetta: non siamo su un campo?

il fatto che sia passato dalla lettera p alla lettera n mi fa sorgere molti sospetti

Sospetti fondati direi.. Immaginavo che non fossero a caso le tue precisazioni su $ n $ e $ p $ ma non riuscivo a vedere l'errore.. ma allora posso dire qualcosa $ \pmod n $ oppure nulla?

Uhm, scusate, sono solo io a non aver capito cosa intende dire @Citrullo con "a coefficienti unitari"?

Nono infatti hai ragione, avevo chiesto di dimostrarlo quando tutti i coefficienti erano 1, ma mi han aiutato a mostrare un caso più generale.. Ora ho chiesto se è possibile dire qualcosa sul numero di soluzioni di una congruenza tipo$ P(x) \equiv 0 (n) $ con $ n $ generico, ma esula dal problema di partenza.

qualcosa si può dire, ma non moltissimo. c'è un thread di qualche tempo fa, al riguardo (il minimo grado di un polinomio che si annulli sulle classi di resto mod n, mi pare fosse di piever).

Va bene, grazie dell'aiuto!