MCD tra polinomi
ragazzi, ho i seguenti polinomi:
$f=x^4-3x^2+2$ e $g=x^3-5x^2+7x-3$
Adesso dovrei calcolare il M.C.D, specifico che siamo in $Z_2$.
Adesso dovrei scomporre i polinomi.
In primis, ho espresso $f$ come $x^4+x^2$ in quanto $-3 in Z_2 = 1$ mentre $+2 in Z_2=0$ va bene?
g lo espresso così: $x^3+x^2+x+1$, vorrei sapere se è corretto, come continuo?
$f=x^4-3x^2+2$ e $g=x^3-5x^2+7x-3$
Adesso dovrei calcolare il M.C.D, specifico che siamo in $Z_2$.
Adesso dovrei scomporre i polinomi.
In primis, ho espresso $f$ come $x^4+x^2$ in quanto $-3 in Z_2 = 1$ mentre $+2 in Z_2=0$ va bene?
g lo espresso così: $x^3+x^2+x+1$, vorrei sapere se è corretto, come continuo?
Risposte
fai la divisione tra polinomi...dovresti applicare se non sbaglio l'algoritmo delle divisioni successive di Euclide
Io ho svolto un primo procedimento, comunque penso che anche usando ruffini andrebbe bene però non sono sicuro
Prova con l'algoritmo delle divisioni successive ricordando che i coefficienti dei monomi li vedi esprimere in $ZZ_2$, quindi forse avrai dei casi in cui ottieni delle frazioni da cui ti dovrai poi calcolare l'inverso moltiplicativo per avere il giusto risultato.
Scusami, potresti farmi capire, come applicare l'algoritmo delle divisioni successive in questo caso?
L'algoritmo delle divisioni successive immagino lo saprai... quello che devi tenere a mente invece è che ti trovi in $ZZ_2$, quindi i coefficienti dei monomi devono risultare sempre in $ZZ_2$. Ti faccio un esempio:
sia $f=\bar(2)x^5$ e $g=\bar(5)x^2$ in , ad esempio, $ZZ_7$; se dividi $f$ per $g$ ottieni $(2/5)x^2$ ma $(2/5)$ altro non è che $2*5^-1x^2$, per cui ti calcoli l'inverso moltiplicativo modulo 7 di 5: cioè $5x-=1_(mod_7)$, cioè $5x-7k=1$ da cui $x=3$ e $k=2$.
Ora sostituisci $5^-1$ con per $3$ e avrai: $2*3x^2$ che è $\bar(6)x^2$, sempre in $ZZ_7$.
Nel tuo caso invece sei in $ZZ_2$, ma il concetto è lo stesso.
Sono un pò contorto
ma spero di essere stato chiaro.
sia $f=\bar(2)x^5$ e $g=\bar(5)x^2$ in , ad esempio, $ZZ_7$; se dividi $f$ per $g$ ottieni $(2/5)x^2$ ma $(2/5)$ altro non è che $2*5^-1x^2$, per cui ti calcoli l'inverso moltiplicativo modulo 7 di 5: cioè $5x-=1_(mod_7)$, cioè $5x-7k=1$ da cui $x=3$ e $k=2$.
Ora sostituisci $5^-1$ con per $3$ e avrai: $2*3x^2$ che è $\bar(6)x^2$, sempre in $ZZ_7$.
Nel tuo caso invece sei in $ZZ_2$, ma il concetto è lo stesso.
Sono un pò contorto
ma spero di essere stato chiaro.
Perdonami, ma se scompongo i due polinomi in prodotto di fattori di altri polinomi e poi prendo i fattori in comune con grado massimo, non ottengo il M.C.D???
Riguardo all'algoritmo euclideo , sò che serve per calcolare il M.C.D tra due numeri.
es. 14 e 11,
Siano a, b due numeri interi, $EE q,r in Z$ tale che $a=bq+r$ con $(0 <= r <|b|)$ q=quoziente ed r=resto.
nel mio caso quindi:
$14=11*1+3$
$11=3*3+2$
$3=1*2+1$
$2=1*2+0$
In questo caso $r_(n-1)$ è il mio M.C.D cioè 1 (M.C.D(14,11)=1)
Adesso, sappiamo che in $Z_n$ l'inverso esiste se e solo se, $AA [a] in Z_n, EE in Z_n : [a]=1$ e se non ho capito male, per calcolarci quel , dobbiamo svolgere un equazione congruenziale del tipo: $ax ≡ 1 (mod. n)$ nel nostro caso:
$(5x ≡ 1 (mod. 7))$. La x è la nostra incognita e va calcolata mediante l'identità di bezout, cioè $EE h,k : ak+bh=1$ in questo caso, dobbiamo calcolare $k$
Adesso non riesco a capire come calcolare $h$ e $k$ dovrei praticamente iterare a ritroso questo:
$14=11*1+3$
$11=3*3+2$
$3=1*2+1$
$2=1*2+0$
cioè:
$1=3-(1*2)$, poi non riesco a capire come continuare le sostituzioni.
P.S
Comunque se divido $f$ per $g$, nel tuo caso, non ttoengo $(2/5)x^3$???
Riguardo all'algoritmo euclideo , sò che serve per calcolare il M.C.D tra due numeri.
es. 14 e 11,
Siano a, b due numeri interi, $EE q,r in Z$ tale che $a=bq+r$ con $(0 <= r <|b|)$ q=quoziente ed r=resto.
nel mio caso quindi:
$14=11*1+3$
$11=3*3+2$
$3=1*2+1$
$2=1*2+0$
In questo caso $r_(n-1)$ è il mio M.C.D cioè 1 (M.C.D(14,11)=1)
Adesso, sappiamo che in $Z_n$ l'inverso esiste se e solo se, $AA [a] in Z_n, EE in Z_n : [a]=1$ e se non ho capito male, per calcolarci quel , dobbiamo svolgere un equazione congruenziale del tipo: $ax ≡ 1 (mod. n)$ nel nostro caso:
$(5x ≡ 1 (mod. 7))$. La x è la nostra incognita e va calcolata mediante l'identità di bezout, cioè $EE h,k : ak+bh=1$ in questo caso, dobbiamo calcolare $k$
Adesso non riesco a capire come calcolare $h$ e $k$ dovrei praticamente iterare a ritroso questo:
$14=11*1+3$
$11=3*3+2$
$3=1*2+1$
$2=1*2+0$
cioè:
$1=3-(1*2)$, poi non riesco a capire come continuare le sostituzioni.
P.S
Comunque se divido $f$ per $g$, nel tuo caso, non ttoengo $(2/5)x^3$???
Aspetta, nell'esempio che ti ho proposto hai $5x-=1_(mod_7)$, cioè $5x-7k=1$, quindi, come hai scritto, devi risolvere l'equazione al fine di calcolare $x$ e $k$ derivante dall'identità di Bèzout.
Il calcolo lo fai proprio come l'hai impostato, però non con i numeri $14$ e $11$
Divisione euclidea tra $7$ e $5$:
$7:5=1$ con il resto di $2$, cioè $7=5*1+2$, e $2=7-5*1$
$5:2=2$ con il resto di $1$, cioè $5=2*2+1$, e $1=5-2*2$
$2:1=2$ con il resto di $0$
quindi parti dall'ultimo resto diverso da zero e inizi le sostituzioni a ritroso:
$1=5-2*2=5*1-2*2$ ma $2=7*1-5*1$ (dalla prima divisione...) quindi avrai $1=5*1-2(7*1-5*1)=5*1-7*2+5*2=5*3-7*2$
che è quanto ricercato, cioè $x=3$ e $k=2$
Relativamente l'ultima domanda, si, ottieni $(2/5)x^3$ ma che puoi scrivere come $2*5^-1x^3$ ricordandoti però che sei in $ZZ_7$, ok, da cui poi tutta la pappardella dell'inverso moltiplicativo, Bèzout, ecc. ecc.
Il calcolo lo fai proprio come l'hai impostato, però non con i numeri $14$ e $11$
Divisione euclidea tra $7$ e $5$:
$7:5=1$ con il resto di $2$, cioè $7=5*1+2$, e $2=7-5*1$
$5:2=2$ con il resto di $1$, cioè $5=2*2+1$, e $1=5-2*2$
$2:1=2$ con il resto di $0$
quindi parti dall'ultimo resto diverso da zero e inizi le sostituzioni a ritroso:
$1=5-2*2=5*1-2*2$ ma $2=7*1-5*1$ (dalla prima divisione...) quindi avrai $1=5*1-2(7*1-5*1)=5*1-7*2+5*2=5*3-7*2$
che è quanto ricercato, cioè $x=3$ e $k=2$
Relativamente l'ultima domanda, si, ottieni $(2/5)x^3$ ma che puoi scrivere come $2*5^-1x^3$ ricordandoti però che sei in $ZZ_7$, ok, da cui poi tutta la pappardella dell'inverso moltiplicativo, Bèzout, ecc. ecc.
$14=11⋅1+3$
$11=3⋅3+2$
$3=1⋅2+1$
$2=1⋅2+0$
In questo esempio che ho usato prima mi trovo : $h=4$ e $k=1$ ho fatto così:
$1=3-1*2=3*1-1*2=3*1-1(11-3*3)=3*1-11*1+3*(3*1)=3*4-11*1$ è giusto?
una volta calcolati h e k cosa faccio per calcolare il M.C.D???
$11=3⋅3+2$
$3=1⋅2+1$
$2=1⋅2+0$
In questo esempio che ho usato prima mi trovo : $h=4$ e $k=1$ ho fatto così:
$1=3-1*2=3*1-1*2=3*1-1(11-3*3)=3*1-11*1+3*(3*1)=3*4-11*1$ è giusto?
una volta calcolati h e k cosa faccio per calcolare il M.C.D???
Il procedimento è giusto, ma ti serve per determinare la relativa identità di Bèzout (per l'inverso moltiplicativo in $ZZ_n$....), non il $MCD$ che hai già trovato e che è $1$.
Si ma vorrei verificare il MCD tra i polinomi che ho scritto nel post iniziale.
L'hai impostato bene, ora basta solo fare la divisione tra polinomi da cui otterrai un resto, che userai per la divisione successiva....
Quindi applicando l'algoritmo delle divisioni successive ho fatto:
$x^4-3x^2+2 : x^3-5x^2+7x-3$ poichè siamo in $Z_2$ esprimo i polinomi così:
$x^4+x^2 : x^3-x^2+x+1$ , applico ruffini per calcolare quoziente e resto, dopodichè itero fino ad ottenere un resto uguale a 0. Dopodichè prendo il resto $r_(n-1)$ cioè prima del resto nullo e cosa faccio?
$x^4-3x^2+2 : x^3-5x^2+7x-3$ poichè siamo in $Z_2$ esprimo i polinomi così:
$x^4+x^2 : x^3-x^2+x+1$ , applico ruffini per calcolare quoziente e resto, dopodichè itero fino ad ottenere un resto uguale a 0. Dopodichè prendo il resto $r_(n-1)$ cioè prima del resto nullo e cosa faccio?
Nulla, quello dovrebbe essere il tuo $MCD$.
Perdonami, allora perchè abbiamo fatto tutto il discorso sull'inverso moltiplicativo, non riesco a capire. Perchè è uscita fuori l'identità di bezout?
Tutto è partito dalla ricerca del $MCD$ tra due polinomi a coefficienti in $ZZ_2$, e ti è stato detto di usare l'algoritmo di divisione euclidea, stando giusto attento però al fatto che sei in $ZZ_n$, quindi potresti avere dei casi di quozienti con coefficienti frazionari, quindi per riportarli modulo $n$ ti dovrai calcolare il relativo inverso moltiplicativo, da cui Bèzout...
Insomma ci siamo lasciati un pò trasportare
Insomma ci siamo lasciati un pò trasportare
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo