´ Matematica ´ Ampliacion Discreta ´ Justo Peralta Lopez U  A´ı ´ D  A  A´ M´

Polinomios

1

´ Introduccion

2

Anillos de polinomios

3

´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun Algoritmo de Euclides Algoritmo de Euclides Extendido

4

Anillo cociente

5

Algoritmo Chino del Resto

6

Polinomios Irreducibles

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Introduccion

Definiciones 1

´ de la forma Sea R un anillo cualquiera. Un polinomio sobre R es una expresion f (x ) =

n X

ai x i = a0 + a1 x + · · · + an x n

i =0

donde n es un entero no negativo, los coeficientes ai ,0 ≤ i ≤ n, son elementos de R, y x es la indeterminada sobre R. 2

3

Dos polinomios f (x ) = 0 ≤ i ≤ n.

Pn

i =o

ai x i y g (x ) =

Pn

i =0

bi x i sobre R son iguales si ai = bi para

Definimos la suma de f (x ) y g (x ) como f (x ) + g (x ) =

n X

(ai + bi )x i

i =0 4

Si f (x ) =

Pn

i =o

ai x i y g (x ) = f (x )g (x ) =

Pm

nX +m

i =0

bi x i definimos el producto como

X

ck x k , donde ck =

k =0

´ Matematica ´ Ampliacion Discreta

i+j =k 0 ≤ i ≤ n, 0 ≤ j ≤ m

Polinomios

ai bj

Polinomios Anillos de polinomios

1

Con estas operaciones, los polinomios sobre R es un anillo al cual llamaremos el anillo de polinomios sobre R y lo notaremos por R [x ].

2

El cero en R [x ] es el polinomio con todos sus coeficientes nulos y lo representaremos por 0.

3

Si f (x ) = f0 + f1 x + . . . fm x m es un polinomio sobre R y fm , 0, entonces m es llamado el grado de f (x ), y a fm se le llama el l´ıder del polinomio. Si fm = 1, entonces decimos ´ que el polinomio es monico.

Teorema Sea f , g ∈ R [x ]. Entonces gr (f + g ) ≤ max (gr (f ), gr (g )) gr (fg ) ≤ gr (f ) + gr (g ) Si R es un dominio de integridad, entonces gr (fg ) = gr (f ) + gr (g )

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Anillos de polinomios

Teorema 1

´ si lo es R. R [x ] es un anillo conmutativo si y solo

2

´ si R posee identidad. R [x ] es un anillo con identidad si y solo

3

´ si R es un dominio de integridad. R [x ] es un dominio de integridad si y solo

Definiciones 1

Sea F un cuerpo. Un polinomio b (x ) es divisible por d (x ) y d (x ) es un factor de b (x ) si existe un q(x ) tal que b (x ) = q(x )d (x ). Si d (x ) es un factor de b (x ), entonces cd (x ) ´ es un factor para c , 0 ∈ F. tambien

2

Las unidades de F[x ] son los divisores del polinomio 1 que son todos los elementos no nulos de F.

Teorema Sea g , 0 un polinomio en F[x ]. Entonces para todo f ∈ F[x ] existen dos polinomios q, r ∈ F[x ] tal que f = qg + r , donde gr (r ) < gr (g ) ´ implica que todo ideal de F[x ] es El hecho de que F[x ] permita un algoritmo de division principal. ´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun

Teorema

F[x ] es un dominio de ideales principales y cualquier ideal J ∈ F[x ] es generado por un ´ ´ unico polinomio monico de menor grado de J. Teorema ´ Sean f1 , f2 , . . . , fn ∈ F[x ] con alguno de ellos no nulos. Entonces existe un unico polinomio ´ monico d ∈ F[x ] con las siguientes propiedades: 1 2

d divide a cada fj , 1 ≤ j ≤ n. ´ d se puede Cualquier polinomio c ∈ F[x ] que divida a fj , 1 ≤ j ≤ n, divide a d. Es mas, expresar como d = b1 f1 + · · · + bn fn con b1 , . . . , bn ∈ F[x ].

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun Algoritmo de Euclides

Algoritmo de Euclides ´ divisor se puede obtener gracias al algoritmo de Sean f , g ∈ F[x ], el m´ınimo comun Euclides de la siguiente forma: f = q1 g + r1 g = q2 r1 + r2 r1 = q3 r2 + r3

0 ≤ gr (r1 ) < gr (g ) 0 ≤ gr (r2 ) < gr (r1 ) 0 ≤ gr (r3 ) < gr (r2 )

rs −2 = q2 rs −1 + r2 rs −1 = qs +1 rs

0 ≤ gr (rs ) < gr (rs −1 )

. . .

´ divisor viene dado por donde q1 , . . . , qs +1 , r1 , . . . , rs ∈ F[x ]. El m´ınimo comun mcd (f , g ) = b −1 rs donde b es el coeficiente l´ıder de rs

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun Algoritmo de Euclides

Teorema ´ Sean f1 , f2 , . . . , fn ∈ F[x ] con alguno de ellos no nulos. Entonces existe un unico polinomio ´ monico m ∈ F[x ] con las siguientes propiedades: 1

´ m es multiplo de cada fj , 1 ≤ j ≤ n.

2

´ ´ Cualquier polinomio b ∈ F[x ] multiplo fj , 1 ≤ j ≤ n, es un multiplo de m.

´ Ademas, a −1 fg = mcm(f , g )mcd (f , g ) donde a es el coeficiente l´ıder de fg.

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun Algoritmo de Euclides Extendido

Algoritmo de Euclides Extendido

Entrada: p1 (x ), p2 (x ) ∈ J [x ], p2 (x ) , 0, m = gr (p1 (x )) ≥ gr (p2 (x )) = n; J un cuerpo. Salida: ph (x ), f (x ), g (x ) ∈ J [x ] tal que gr (f (x )) < gr (p1 (x ) − gr (ph (x )),gr (g (x )) < gr (p2 (x ) − gr (ph (x )) y ph (x ) = p1 (x )g (x ) + p2 (x )f (x ) 1. [Inicio ] [p0 (x ), p1 (x )] := [p1 (x ), p2 (x )];[g0 (x ), g1 (x )] := [1, 0]; 2. [Ciclo ] While p1 (x ) , 0 do q(x ) := Cociente(p0 (x ), p1 (x )); [p0 (x ), p1 (x )] := [p1 (x ), p0 (x ) − p1 (x )q(x )] [g0 (x ), g1 (x )] := [g1 (x ), g0 (x ) − g1 (x )q(x )] [f0 (x ), f1 (x )] := [f1 (x ), f0 (x ) − f1 (x )q(x )] 3.[Salida ] Return [ph (x ), g (x ), f (x )] := [p0 (x ), g0 (x ), f0 (x )]

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios ´ Divisor y M´ınimo Comun ´ Multiplo ´ M´ınimo Comun Algoritmo de Euclides Extendido

Ejemplo Sea p1 (x ) = 7x 5 + 4x 3 + 2x + 1 y p2 (x ) = 5x 3 + 2 sobre el cuerpo Z11 ´ Iteracion 0 1 2 3 4

q (x )

− 8x 2 + 3 10x + 4 8x + 7 7x

p0 (x ) 7x 5 + 4x 3 + 2x + 1 5x 3 + 2 6x + 2x + 6 9x 6

p1 (x ) 5x 3 + 2 2 6x + 2x + 6 9x 6 0

´ Matematica ´ Ampliacion Discreta

g0 (x ) 1 0 1 x +7 3x 2 + 8

g1 (x ) 0 1 x +7 3x 2 + 8

−

Polinomios

f 0 (x ) 0 1 3x 2 + 8 3x 3 + 10x 2 + 8x + 2 9x 4 + 4x 2 + 3x + 10

f1 (x ) 1 3x 2 + 8 3x 3 + 10x 2 + 8x + 2 9x 4 + 4x 2 + 3x + 10

−

Polinomios Anillo cociente

´ Definicion Un polinomio p ∈ F[x ] es irreducible sobre F si p tiene grado positivo y si p = bc con b , c ∈ F[x ] implica que b o c es una constante. Lema Si un polinomio irreducible p ∈ F[x ] divide al producto f1 . . . fm de polinomios en F[x ], entonces como m´ınimo un factor fj es divisible por p. ´ ´ Unica) Teorema (Factorizacion Cualquier polinomio f ∈ F[x ] de grado positivo se puede expresar como e

e

f = ap1 1 . . . pk k ´ con a ∈ F y p1 , . . . , pk ∈ F[x ] son polinomios monicos irreducibles distintos y e1 , . . . , ek ´ dicha factorizacion ´ es unica. ´ enteros positivos. Ademas,

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Anillo cociente

Teorema ´ si f es irreducible sobre Para todo f ∈ F[x ], el anillo cociente F[x ]/(f ) es un cuerpo si y solo F. ´ Definicion ´ Dos polinomios g (x ), h (x ) en Fq [x ], se dicen que son congruentes modulo f (x ), y se denota por g (x ) ≡f (x ) h (x ) ´ si g (x ) − h (x ) es divisible por f (x ). si y solo

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Anillo cociente

Ejemplo 1 2

Sea f (x ) = x ∈ F2 [x ]. Entonces F2 [x ]/(x ) = {[0], [1]}. Sea f (x ) = x 2 + x + 1 ∈ F2 [x ]/(f ). Entonces F2 [x ]/(f ) = {[0], [1], [x ], [x + 1]} y la tabla de operaciones viene dado por

+ [0] [1] [x ] [x + 1] × [0] [1] [x ] [x + 1]

[0] [0] [1] [x ] [x + 1] [0] [0] [0] [0] [0]

´ Matematica ´ Ampliacion Discreta

[1] [1] [0] [x + 1] [x ] [1] [0] [1] [x ] [x + 1]

[x ] [x ] [x + 1] [0] [1] [x ] [0] [x ] [x + 1] [1]

Polinomios

[x + 1] [x + 1] [x ] [1] [0] [x + 1] [0] [x + 1] [1] [x ]

Polinomios Anillo cociente

´ Definicion Un elemento b ∈ F es una ra´ız de f ∈ F[x ] si f (b ) = 0. Teorema ´ si x − b divide a f (x ). Un elemento b ∈ F[x ] es una ra´ız de f ∈ F[x ] si y solo ´ Definicion Sea b ∈ F una ra´ız de f ∈ F[x ]. Si k es un entero positivo tal que f (x ) es divisible por (x − b )k pero no por(x − b )k +1 , entonces llamamos a k la multiplicidad de b. Si k = 1 entonces decimos que b es de multiplicidad simple. Teorema ´ ´ si es ra´ız de f y f 0 . Un elemento b ∈ F es una ra´ız multiple de f ∈ F si y solo Teorema ´ si no posee raices en El polinomio f ∈ F[x ] de grado 2 o 3 es irreducible en F[x ] si y solo F[x ] ´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Algoritmo Chino del Resto

´ Congruencias modulo un polinomio p (x ) ∈ F[x ] verifican las mismas propiedades que para enteros. Por ejemplo: 1

Si f ≡m g, entonces fk ≡m kg.

2

Si f1 ≡m g1 y f2 ≡m g2 , entonces f1 + g1 ≡m g1 + g2 y f1 g1 ≡m g1 g2

3

Si f ≡m g y g ≡m h entonces f ≡m h.

Teorema (Resto Chino) Sea F un cuerpo y a1 (x ), a2 (x ), . . . , an (x ), m1 (x ), m2 (x ), . . . , mn (x ) ∈ F[x ], tal que mi (x ) y mj (x ) sean coprimos . Entonces existe un f (x ) ∈ F[x ] tal que f (x ) ≡m1 (x ) a1 (x ) f (x ) ≡m2 (x ) a2 (x )

. . .

f (x ) ≡mn (x ) an (x ) Si f( x ), f2 (x ) son dos soluciones, entonces f1 (x ) ≡M (x ) f2 (x ) con M (x ) =

´ Matematica ´ Ampliacion Discreta

Polinomios

Q

mi (x )

Polinomios Algoritmo Chino del Resto

Algoritmo del Resto Chino ´ Las formulas para el algoritmo del resto chino para i = 1, . . . , n M1 (x ) = 1 Q Mi (x ) = ij =1 mj (x ) Ui (x )Mi (x ) ≡mi (x ) 1 b1 (x ) = a1 (x ) wi (x ) = (ai (x ) − bi −1 (x ))Ui (x ) m¨ı¿ 12 ulo mi (x ) bi (x ) = bi −1 (x ) + wi (x )Mi (x ) Ejemplo f (x ) ≡x 2 +x x y f (x ) ≡x 2 +x +1 1 en Z2 [x ] poseen la tabla ai x 1

mi x2 + x x2 + x + 1

Mi 1 x2 + x

´ Matematica ´ Ampliacion Discreta

Ui 1 1

Polinomios

wi

− 1+x

bi x x3

Polinomios Polinomios Irreducibles

´ Definicion ´ de Mobiuis se define por Sea m ∈ Z+ . La funcion

  1, si m = 1    0, si m es divisible por el cuadrado de un primo µ(m) =     (−1)k , si m es el producto de k primos diferentes Ejemplo m

1

1 1

2 −1

3 −1

4 0

5 −1

6 1

7 −1

8 0

9 0

10 1

´ ´ El numero de polinomios monicos irreducibles de grado m en Zp [x ] para p primo viene dado por 1 X Np ( m ) = µ(d )p m/d m d |m

2

´ La probabilidad de que un polinomio aleatorio monico sea irreducible es aproximadamente 1/m.

´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Polinomios Irreducibles

Teorema Sea p un primo y k ∈ Z+ 1

´ El producto de todos los polinomios monicos irreducibles en Zp [x ] de grado un divisor de k es igual a k

xp − x 2

Sea f (x ) un polinomio de grado m en Zp [x ]. Entonces f (x ) es irreducible sobre Zp [x ] ´ si si y solo i m mcd (f (x ), x p − x ) = 1 ∀i , 1 ≤ i ≤ b c 2

Test polinomio irreducible

´ Entrada: Un primo p y un polinomio monico de grado m ∈ Zp [x ] Salida: Respuesta a , es f (x ) irreducible en Zp [x ] ?. 1. u(x ) := x 2. For i = 1 to b m 2 c do 2.1 u(x ) := u(x )p mod f (x ) 2.2 d (x ) := mcd (f (x ), u(x ) − x ) 2.3 if d (x ) , 1 then Return(Reducible”)

3. Return(”Irreducible”) ´ Matematica ´ Ampliacion Discreta

Polinomios

Polinomios Polinomios Irreducibles

´ de polinomios irreducibles Generacion

Entrada: Un primo p y un m ∈ Z+ ´ Salida: f (x ) monico irreducible de grado m en Zp [x ] 1. Generar a0 , a1 , . . . , am−1 de forma aleatoria con 0 ≤ ai ≤ p − 1 y a0 , 0 2. f (x ) := a0 + a1 x + a2 x 2 + · · · + am−1 x m−1 + x m 3. Testear si f (x ) es irreducible 3.1 Si f (x ) es irreducible Return(f (x )) 3.2 Si f (x ) no es irreducible ir a 1.

´ Matematica ´ Ampliacion Discreta

Polinomios