Quoziente e resto di polinomi in Zn

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Quoziente e resto di polinomi in Zn #64197

avt
Monimela
Punto
Ciao a tutti! Non riesco a comprendere questo esercizio sul quoziente e sul resto di polinomi in Zn, mi potete aiutare?

Siano

p(x)= 3x^4 - 5x^2 + 3

q(x)= 2x^2 - 1

con p(x), q(x) appartenenti all'insieme \mathbb{Z}_{19} [x]. E' possibile calcolare il quoziente e resto del rapporto p(x)/q(x)? Perché? in caso affermativo, svolgere il calcolo.


Dalla divisione tra i due polinomi ottengo il risultato \frac{3}{2} x^2 - \frac{7}{4}. Il resto è \frac{5}{4}.

A questo punto come mi comporto?

Come fa il quoziente finale ad essere [11]x^2 + [3] ? (Soluzione dell'esercizio)

Quello che non capisco è:
- in che modo utilizzo i risultati ottenuti dalla divisione dei due polinomi?
- come faccio a trovare gli inversi nell'insieme? Il procedimento non mi è chiaro.

Grazie ancora in anticipo!
 
 

Re: Quoziente e resto di polinomi in Zn #64228

avt
Galois
Amministratore
Ciao Monimela emt

Procediamo con ordine.

Proprio come accade in \mathbb{Z} dove il Teorema della divisione euclidea ci assicura l'esistenza e l'unicità di quoziente e resto tra due numeri interi, esiste un Teorema che ci garantisce l'esistenza di quoziente e resto della divisione tra due polinomi ed è il seguente:

Sia (A,+,\cdot) un campo.

Per ogni a(x), b(x) \in A[x], \ b \neq 0 esistono due polinomi:

q(x),r(x) \in A[x] tali che

a(x) = q(x) \cdot b(x)+r(x)

con grado[r(x)] < grado[b(x)]. Inoltre q(x) e r(x) sono unici.

Ora, noi abbiamo due polinomi a coefficienti in \mathbb{Z}_{n}, \ \mbox{con} \ n=19 che sappiamo essere un campo in quanto 19 è un numero primo. Siamo quindi sicuri dell'esistenza di quoziente e resto della divisione tra i due polinomi:

p(x)= 3x^4 - 5x^2 + 3

q(x)= 2x^2 - 1

Eseguiamola! Prima di procedere, dobbiamo ricordare che stiamo lavorando, appunto in \mathbb{Z}_{19} ovvero con le classi di resto modulo 19. Per intenderci con le classi di equivalenza i cui rappresentanti sono:

\mathbb{Z}_{19} = \left\{[0]_{19}, \ [1]_{19}, \ [2]_{19}, \ ....., \ [18]_{19} \right\}

cioè, per dirla in "maniera sporca" ogni numero maggiore o uguale a 19 dovrà essere ricondotto ad una di tali classi.

Ad esempio

23 \equiv 4 \ (mod 19)

In quanto:

23:19=1 \ resto \ {\color{red}4}

Chiarito questo vediamo come eseguire la divisione:

Iniziamo con disporre i termini in colonna, proprio come si procede nella divisione tra polinomi in \mathbb{R}:

\begin{array}{ccccccccc|ccc}3x^4 & + & 0x^3 & - & 5x^2 & + & 0x & + & 3 & 2x^2 & - & 1\\\cline{10-12}\end{array}

Ora, che dobbiamo fare?

Dobbiamo trovare quel termine che moltiplicato per 2x^2 ci da come risultato 3x^4

Ovviamente la x sarà elevata al quadrato. Non ci rimane altro da fare se non trovare il suo coefficiente (lo chiamo \spadesuit).

Ricordando che stiamo lavorando in \mathbb{Z}_{19} non possiamo utilizzare frazioni! Dobbiamo quindi procedere con le congruenze. Cioè dobbiamo, ripeto, trovare quel numero \spadesuit che moltiplicato per 2 ci da 3, cioè:

2 \cdot \spadesuit = 3 \ (mod 19)

Per trovarlo, moltiplichiamo ambo i membri per l'inverso moltiplicativo di 2 (modulo 19) che è 10, in quanto:

2 \cdot 10 = 20 \equiv 1 \ (mod 19)

cioè, (così rispondo anche all'altra tua domanda) l'inverso moltiplicativo a^{-1} di un numero a modulo n è quel numero tale che:

aa^{-1} \equiv 1 \ (mod \ n)

Come si fa a trovarlo? Basta solo un po' di pratica e soprattutto occhio. Male che vada si procede per tentativi! Tanto, ricorda, stiamo lavorando in insiemi che hanno un numero finito di elementi.. nel nostro specifico caso 19.

Tornando a noi, avendo trovato che 10 è l'inverso di 2 modulo 19, moltiplicando in

2 \cdot \spadesuit = 3 \ (mod 19)

ambo i membri per 10 si ha:

\underbrace{2 \cdot 10}_{=1 \ (mod 19)} \cdot \spadesuit = 3 \cdot 10 = 30 \ (mod 19)

Ovvero:

\spadesuit = 30 = 11 \ (mod 19)

Pertanto il primo termine del quoziente sarà 11x^2 o meglio [11]_{19} x^2 (visto che stiamo lavorando con classi)

In definitiva, facendo i conti:

\begin{array}{ccccccccc|ccc}3x^4 & + & 0x^3 & - & 5x^2 & + & 0x & + & 3 & 2x^2 & - & 1\\\cline{10-12}3x^4 & - & /\ & - &  11x^2 & & & & & 11x^2 & \\ \cline{1-9} & & & & 6x^2 & & & + & 3\end{array}

Ora, stesso ragionamento di prima: dobbiamo trovare quel termine tale che moltiplicato per 2x^2 ci dia 6x^2

Qua, senza fare mille giri, tale termine è direttamente 3. Abbiamo quindi:

\begin{array}{ccccccccc|ccc}3x^4 & + & 0x^3 & - & 5x^2 & + & 0x & + & 3 & 2x^2 & - & 1\\\cline{10-12}3x^4 & - & /\ & - &  11x^2 & & & & & 11x^2 & + & 3\\ \cline{1-9} & & & & 6x^2 & & & + & 3 & \\ & & & & 6x^2 & & & - & 3 & \\ \cline{1-9} & & & & & & & + & 6 &\end{array}


Ovvero p(x):q(x) = 11 x^2 + 3 \ \mbox{resto} \ 6

Sempre in \mathbb{Z}_{19}!

Facciamo la verifica:

(11x^2+3)(2x^2-1)+6=22x^4-11x^2+6x^2-3+6=22x^4-5x^2+3=3x^4-5x^2+3

in quanto

22 = 5 \ (mod \ 19)

emt
Ringraziano: Omega, Pi Greco, CarFaby
  • Pagina:
  • 1
Os