al massimo b soluzioni
al massimo b soluzioni
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 $)?
Come si dimostra che $ P(x) \equiv 0 (p) $ ha al massimo $ b $ soluzioni (intese modulo $ p $)?
Re: al massimo b soluzioni
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...
Re: al massimo b soluzioni
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.
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.
Re: al massimo b soluzioni
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ì).
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ì).
Re: al massimo b soluzioni
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?
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?
-
- Messaggi: 282
- Iscritto il: 23 dic 2009, 17:14
Re: al massimo b soluzioni
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)
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)
Re: al massimo b soluzioni
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:
-
- Messaggi: 282
- Iscritto il: 23 dic 2009, 17:14
Re: al massimo b soluzioni
hai ragione, ero convinto di essere su un campo...
edit: aspetta: non siamo su un campo?
edit: aspetta: non siamo su un campo?
Re: al massimo b soluzioni
il fatto che sia passato dalla lettera p alla lettera n mi fa sorgere molti sospetti
Re: al massimo b soluzioni
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?
Re: al massimo b soluzioni
Uhm, scusate, sono solo io a non aver capito cosa intende dire @Citrullo con "a coefficienti unitari"?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: al massimo b soluzioni
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.
Re: al massimo b soluzioni
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).
Re: al massimo b soluzioni
Va bene, grazie dell'aiuto!