Ruffini e radici in $Z_n[x]$
Avevo postato una domanda prima, ma siccome mi sono accorta di aver scritto una megavaccata ho cancellato.
Riprovo a porla in maniera (spero) corretta.
Per scomporre il polinomio $x^2+1$ in $Z_5[x]$ lo scrivo come $x^2-4 = (x+2)(x-2)$.
Mi chiedevo se, in generale, per trovare le radici di un polinomio in $Z_n[x]$ che ha termine noto $p_0$, devo cercarle tra i fattori di $p_0$ e tra quelli di $p_0-n$ (che poi nelle classi di resto sono lo stesso numero).
Se invece mi chiedessi, per esempio: "trovare in quali classi di resto $Z_n$ il polinomio $p(x) = x^2+x+1$ ha radici"?
Una curiosità: questi $n$ per cui p(x) ha soluzioni in $Z_n$ hanno qualche "regolarità"? (se la domanda ha senso)
Riprovo a porla in maniera (spero) corretta.
Per scomporre il polinomio $x^2+1$ in $Z_5[x]$ lo scrivo come $x^2-4 = (x+2)(x-2)$.
Mi chiedevo se, in generale, per trovare le radici di un polinomio in $Z_n[x]$ che ha termine noto $p_0$, devo cercarle tra i fattori di $p_0$ e tra quelli di $p_0-n$ (che poi nelle classi di resto sono lo stesso numero).
Se invece mi chiedessi, per esempio: "trovare in quali classi di resto $Z_n$ il polinomio $p(x) = x^2+x+1$ ha radici"?
Una curiosità: questi $n$ per cui p(x) ha soluzioni in $Z_n$ hanno qualche "regolarità"? (se la domanda ha senso)
Risposte
CIa0 Paola jitter;
ti posso gettare una risposta parziale: se \(\displaystyle n\) è dispari puoi usare (nel caso delle equazioni di secondo grado) la usuale formula risolutiva.
ti posso gettare una risposta parziale: se \(\displaystyle n\) è dispari puoi usare (nel caso delle equazioni di secondo grado) la usuale formula risolutiva.
Ciao Armando! 
sono a corto di idee, mannaggia
...
comincio a scrivere la formula risolutiva per l'esempio $ p(x) = x^2+x+1 $:
$x= (-1+-sqrt(-3))/2$
Il polinomio ha radici per le classi in cui $-3$ è un quadrato perfetto e la soluzione è intera. Quindi devo avere $[k^2+3] = [0] mod n$... ma qui non mi viene in mente niente che sia legato a $n$ dispari...
"j18eos":
ti posso gettare una risposta parziale: se n è dispari puoi usare (nel caso delle equazioni di secondo grado) la usuale formula risolutiva.
sono a corto di idee, mannaggia
...comincio a scrivere la formula risolutiva per l'esempio $ p(x) = x^2+x+1 $:
$x= (-1+-sqrt(-3))/2$
Il polinomio ha radici per le classi in cui $-3$ è un quadrato perfetto e la soluzione è intera. Quindi devo avere $[k^2+3] = [0] mod n$... ma qui non mi viene in mente niente che sia legato a $n$ dispari...
(Ri)Eccomi qua! 
Ho iniziato dall'ipotesi che \(\displaystyle n\) sia dispari, sicché si possa considerare l'inverso di \(\displaystyle2\) in \(\displaystyle\mathbb{Z}_n\) (perché?) e usare la formula risolutiva delle equazioni (intere) di secondo grado.
Correttamente arrivi all'equazione congruenziale
\[
k^2\equiv-3(mod\,n)
\]
che ti permette di determinare per quali \(\displaystyle n\) dispari \(\displaystyle-3\) è un quadrato in \(\displaystyle\mathbb{Z}_n\); cioè gli \(\displaystyle n\) dispari tali che:
\[
\exists h,k\in\mathbb{Z}\mid k^2+3=hn.
\]
Se, invece, \(\displaystyle n\) è pari: il polinomio \(\displaystyle x^2+x+1\) sui numeri interi fornisce sempre numeri dispari; e quindi...
Ho iniziato dall'ipotesi che \(\displaystyle n\) sia dispari, sicché si possa considerare l'inverso di \(\displaystyle2\) in \(\displaystyle\mathbb{Z}_n\) (perché?) e usare la formula risolutiva delle equazioni (intere) di secondo grado.
Correttamente arrivi all'equazione congruenziale
\[
k^2\equiv-3(mod\,n)
\]
che ti permette di determinare per quali \(\displaystyle n\) dispari \(\displaystyle-3\) è un quadrato in \(\displaystyle\mathbb{Z}_n\); cioè gli \(\displaystyle n\) dispari tali che:
\[
\exists h,k\in\mathbb{Z}\mid k^2+3=hn.
\]
Se, invece, \(\displaystyle n\) è pari: il polinomio \(\displaystyle x^2+x+1\) sui numeri interi fornisce sempre numeri dispari; e quindi...
Grazie!!! 
Forse aggio capito...
Perché la formula risolutiva contiene "fratto 2", cioè l'inverso di 2, che esiste solo in $Zn$ con n dispari (se n è pari, 2 è un divisore dello zero e quindi non è invertibile).
Mi resterebbe un po' il dubbio "boh, magari la radice di $-3$ è dispari nella classe $Zn$ (potrebbe?), e quindi il "fratto 2" non disturberebbe... ma comunque anche da qui si esclude il caso pari:
perché se $x^2+x+1$ è dispari non può essere congruo a zero.
Forse aggio capito...
"j18eos":
Ho iniziato dall'ipotesi che n sia dispari, sicché si possa considerare l'inverso di 2 in Zn (perché?) e usare la formula risolutiva delle equazioni (intere) di secondo grado.
Perché la formula risolutiva contiene "fratto 2", cioè l'inverso di 2, che esiste solo in $Zn$ con n dispari (se n è pari, 2 è un divisore dello zero e quindi non è invertibile).
Mi resterebbe un po' il dubbio "boh, magari la radice di $-3$ è dispari nella classe $Zn$ (potrebbe?), e quindi il "fratto 2" non disturberebbe... ma comunque anche da qui si esclude il caso pari:
"j18eos":
Se, invece, n è pari: il polinomio $x^2+x+1$ sui numeri interi fornisce sempre numeri dispari; e quindi...
perché se $x^2+x+1$ è dispari non può essere congruo a zero.
Esatto Paola!
Per avere idee sul problema di risolvere $X^2+3=0$ modulo $n$ considera il caso in cui $n$ è un numero primo e usa il simbolo di Legendre e nella fattispecie la legge di reciprocità quadratica.
"Martino":
er avere idee sul problema di risolvere X2+3=0 modulo n considera il caso in cui n è un numero primo e usa il simbolo di Legendre e nella fattispecie la legge di reciprocità quadratica.
Non l'avevo mai visto, mi sembra interessante.
Provo ad applicarlo per vedere che succede, seguendo la voce di wiki.
Devo tradurre nel simbolo di Legendre $ k^3-=_p 3 $ con p numero primo:
$ L=( ( -3 ),( p ) ) $
Si hanno tre casi:
1) $L = 0$ se $p | -3$, cioè se $p=+-1$ oppure $p=+-3$ (in questo caso la verifica per l'equazione può essere diretta)
2) $L = 1$ se esiste un intero k tale che $k^2-=_p-3$, che mi sa è proprio il caso che ci interessa
3) $L = -1$ se non esiste il k come nel caso 2
Provo ad applicare alla 2) le proprietà elencate nella voce wiki:
Se $k^2 ≡_p -3 $, allora $ ( ( -3 ),( p ) ) = ( ( k^2),( p ) ) = ( ( k),( p ) )( ( k),( p ) ) $
Ora potrei porre $( ( k),( p ) )( ( k),( p ) ) = 1$ perché voglio soddisfatta la condizione 2.
Ma $( ( k),( p ) ) = +-1$ quando $k -=_p h^2$ e.... porca miseria sul più bello (pensavo di essere arrivata a qualche conclusione) non so più andare avanti...
Poi mi sa che ho sbagliato anche perché potrebbe essere $( ( k),( p ) ) = -1$, mentre non potrebbe essere zero....
(a proposito: il fatto che non possa essere zero mi dice che la congruenza non è soddisfatta per p = 1 e 3?)
Prova a usare la reciprocità quadratica: se $p$ e $q$ sono due primi dispari allora
$((p),(q)) ((q),(p)) = (-1)^{((p-1)(q-1))/4}$
Questo insieme alla completa moltiplicatività (vedi il link wiki sopra sul simbolo di Legendre) implica che
$((-3),(p)) = ((-1),(p)) ((3),(p)) = (-1)^{(p-1)/2} ((p),(3)) (-1)^{((3-1)(p-1))/4} = ((p),(3))$.
Quindi se $p$ è un primo dispari allora $-3$ è un quadrato modulo $p$ se e solo se $p$ è un quadrato modulo $3$. Concorderai che il problema si è semplificato enormemente. Riesci a concludere?
$((p),(q)) ((q),(p)) = (-1)^{((p-1)(q-1))/4}$
Questo insieme alla completa moltiplicatività (vedi il link wiki sopra sul simbolo di Legendre) implica che
$((-3),(p)) = ((-1),(p)) ((3),(p)) = (-1)^{(p-1)/2} ((p),(3)) (-1)^{((3-1)(p-1))/4} = ((p),(3))$.
Quindi se $p$ è un primo dispari allora $-3$ è un quadrato modulo $p$ se e solo se $p$ è un quadrato modulo $3$. Concorderai che il problema si è semplificato enormemente. Riesci a concludere?
"Martino":
Questo insieme alla completa moltiplicatività (vedi il link wiki sopra sul simbolo di Legendre) implica che
(−3p)=(−1p)(3p)=(−1)p−12(p3)(−1)(3−1)(p−1)4=(p3).
Quindi se p è un primo dispari allora −3 è un quadrato modulo p se e solo se p è un quadrato modulo 3.
Come manipolazione dei simboli, fino a qui ci sono.
"Martino":
Concorderai che il problema si è semplificato enormemente. Riesci a concludere?
Per capire che si è semplificato dovrei capire perché dire che p è un quadrato modulo 3 è più semplice che dire che −3 è un quadrato modulo p.
Che $p$ è un quadrato modulo 3 significa che esiste $h$ t.c. $h^2-=_3p$. Questa congruenza di secondo grado non l'ho mai vista e non saprei come affrontarla, ma forse è qui che si semplifica il problema perché, sapendola risolvere, probabilmente è un attimo...
E' una stupidata, per risolverla, mettere a sistema $h^2=3s+p$ con $k^2=pt+3$?
Il valore di $p$ modulo $3$ può essere solo $0$, $1$ o $2$. Quale di questi è un quadrato modulo $3$?
"Martino":
Il valore di p modulo 3 può essere solo 0, 1 o 2. Quale di questi è un quadrato modulo 3?
Direi 1... quindi la conclusione è che l'equazione iniziale (per p primo) ha soluzione per tutti e soli i numeri primi congrui a 1 modulo 3?
Sì quasi, devi includere il primo 3 (a un certo punto ho diviso per il simbolo di Legendre). Il caso generale in cui $n$ è dispari e non primo si può fare credo ma con un po' più di fatica usando la moltiplicatività.
Ok! Grazie mille per lo stimolo, è stato un esercizio che mi ha divertita
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo