CMG N3 - Polinômios, RdU e Ciclotômicos

Prévia do material em texto

CÍRCULOS MATEMÁTICOS DE GOIÂNIA - NÍVEL 3
Profª Ana Paula Chaves
apchaves@ufg.br
https://apchaves.ime.ufg.br/
• Polinômios, Raízes da Unidade e Polinômios Ciclotômicos •
1. INTRODUÇÃO
Um polinômio de grau n, em x, sobre um anel R, usualmenteZ,Q,R ouC, é uma expressão da forma
P (x) = an xn +an°1xn°1 +·· ·+a1x +a0 ,
onde ai 2 R para 0 ∑ i ∑ n e an 6= 0. Os ai ’s são ditos os coeficientes de P (x), e seu grau é denotado
aqui por deg P (x) (alguns livros podem usar @P ou outras notações). Um elemento não-nulo1 a 2 R, é
um polinômio de grau nulo. Se P (a) = 0, dizemos que a é uma raíz de P (x). O conjunto de todos os
polinômios em x sobre R, é denotado por R[x], e dito o Anel de Polinômios sobre R.
Algumas propriedades de R[x] são:
(1) R[x] é fechado para as operações de + e ·;
(2) deg( f (x)+ g (x)) ∑ max{deg( f (x)),deg(g (x))};
(3) deg( f (x)g (x)) = deg( f (x))+deg(g (x));
(4) (Divisão de polinômios) R[x] é um Domínio Euclidiano, isto é, dados f (x) e g (x) em R[x], com
g (x) não-nulo, existem q(x),r (x) 2 R[x] tais que
f (x) = q(x)g (x)+ r (x),
onde deg(r (x)) < deg(g (x)).
(5) Para f (x), g (x) 2 R[x], com g (x) não-nulo, dizemos que “g (x) divide f (x)", e denotamos por
g (x)| f (x), se existe um polinômio q(x) 2 R[x], não-nulo, tal que f (x) = q(x)g (x).
(6) Um polinômio p(x) é dito irredutível sobre R, se não pode ser escrito como o produto de dois
polinômios de R[x], de grau positivo. Caso um polinômio não seja irredutível, o chamamos de
redutível.
(7) (MDC) Dados f (x), g (x) 2 R[x], as seguintes afirmações para d(x) 2 R[x] são equivalentes:
(a) Para todo polinômio não-nulo p(x) 2 R[x], p(x)| f (x) e p(x)|g (x), implica p(x)|d(x);
(b) d(x) possui grau máximo dentre os divisores comuns de f (x) e g (x);
1Aqui, entendemos o ‘0"como o elemento neutro da operação aditiva de R, podendo não ser o nosso 0, dependendo
do anel
1
https://apchaves.ime.ufg.br/
(c) d(x) é um polinômio não-nulo, de grau mínimo, tal que existem a(x),b(x) 2 R[x] satisfa-
zendo d(x) = a(x) f (x)+b(x)g (x).
Se d(x) satisfaz uma das propriedades acima, e portanto todas, dizemos que d(x) é o má-
ximo divisor comum (MDC) de f (x) e g (x), e escrevemos d(x) = mdc( f (x), g (x)) ou apenas
( f (x), g (x)). O MDC sempre existe e é único, a menos de uma constante não nula de R, para
todo par de polinômios f (x) e g (x).
(8) R[x] é um domínio de fatoração única (DFU), isto é, todo polinômio não-nulo p(x) 2 R[x] pode
ser fatorado de maneira única (a menos de uma constante e permutação) no produto de po-
linômios irredutíveis.2
2. ÁLGEBRA
Alguns dos resultados mais úteis vindos da estrutura algébrica de um anel de polinômios, são:
Teorema Fundamental da Álgebra: Um polinômio P (x) de grau n em C[x], possui n raízes complexas.
Ele pode ser fatorado de forma única como
P (x) = a(x ° r1)(x ° r2) · · · (x ° rn) .
Relações de Girard: Seja P (x) = an xn +an°1xn°1+·· ·+a1x °a0, com ai 2C e raízes r1,r2, . . . ,rn. Então:
nX
i=1
ri = (°1)1
an°1
an
;
X
1∑i< j∑n
ri r j = (°1)2
an°2
an
; . . . ;
X
1∑i1<...<in°1∑n
ri1 · · ·rin°1 = (°1)n°1
a1
an
;
r1r2 · · ·rn = (°1)n
a0
an
.
Teorema de Bezout: Um polinômio P (x) é divisível por x °a se, e somente se, P (a) = 0.
Interpolação de Lagrange: Dados n pontos (x1, y1), (x2, y2), . . . , (xn , yn), existe um único polinômio P (x)
que passa por esses n pontos, ou seja, P (xi ) = yi , para i = 1,2, . . . ,n. Sua forma explícita é:
P (x) =
nX
i=1
yi
Y
1∑ j∑n
j 6=i
x °x j
xi °x j
.
2Mais precisamente, R[x] é DFU se R é DFU, o que é válido para Z,Q,R e C.
2
Regra dos sinais de Descartes: Seja P (x) 2R[x]. Então a quantidade de raizes positivas de P (x) é igual a
N °2k, onde N é a quantidade de trocas de sinais na lista dos coeficientes (ignorando coeficientes nulos),
e k é um inteiro positivo.
Algumas estratégias de ataque são:
• Atenção nas raízes: Utilizar o Teorema Fundametal da Álgebra sempre que for interessante.
Por exemplo, se queremos mostrar que um polinômio P (x) é identicamente nulo, produzir uma
sequência de infinitas raízes, dá conta do recado.
• Atenção nos coeficientes: Útil principalmente quando temos coeficientes inteiros. O coefici-
ente líder e o independente são os mais interessantes de se observar.
• Um fato simples, porém muito útil, é P (x)|Q(x) ) deg(P (x)) ∑ deg(Q(x)).
• Tentar algumas manipulações algébricas como fatorar, expadir, introduzir polinômios auxilia-
res, ver o que ocorre com o polinômio ao trocarmos a variável x por outras expressões, como
x +1, 1/x e etc.
2.1. Warm-up.
Problema 2.1: Seja f (x) um polinômio quadrático. Mostre que existem polinômios quadráticos g (x) e
h(x) tais que f (x) f (x +1) = g (h(x)).
Problema 2.2: Sejam P (x) e Q(x) polinômios com coeficientes reais tais que P (x) =Q(x) para todo x 2R.
Mostre que P (z) =Q(z), para todo z 2C.
Problema 2.3: (USAMO 1975) Seja f um polinômio de grau n tal que
f (0) = 0, f (1) = 1
2
, f (2) = 2
3
, . . . , f (n) = n
n +1 .
Encontre f (n +1).
2.2. Problemas.
Problema 2.4: (SL IMO 1997) Seja f um polinômio de coeficientes inteiros e seja p um primo tal que
f (0) = 0, f (1) = 1 e f (k) ¥ 0,1 (mod p) para todo k inteiro positivo. Mostre que deg( f ) é pelo menos
p °1.
Problema 2.5: (OBM 2007) Seja P (x) = x2+2007x+1. Prove que para todo inteiro positivo n, a equação
P (P (. . . (P (x)) . . .)) = 0 possui pelo menos uma solução real, onde a composição é tomada n vezes.
3
Ana Paula Chaves
Problema 2.6: (Putnam 1977) Determine todas as soluções do sistema
x + y + z = w
1
x
+ 1
y
+ 1
z
= 1
w
.
Problema 2.7: (Russia 2002) Dentre os polinômios P (x),Q(x),R(x), com coeficientes reais, pelo menos
um possui grau 2 e um possui grau 3. Se P 2(x)+Q2(x) = R2(x), mostre que um dos polinômios de grau
3, possui três raízes reais.
Problema 2.8: (Putnam 2010) Encontre todos os polinômios P (x),Q(x), com coeficientes reais, tais que
P (x)Q(x +1)°P (x +1)Q(x) = 1.
Problema 2.9: Prove a identidade
nX
k=0
(°1)n°k
√
n
k
!
kn+1 = n(n +1)!
2
.
Problema 2.10: (USAMO 2002) Mostre que todo polinômio mônico 3 de grau n e coeficientes reais, pode
ser escrito como a média de dois polinômios mônicos de grau n com n raízes reais.
Problema 2.11: (IMO 2002) Encontre todos os pares de inteiros m,n > 2 tais que existam infinitos va-
lores de k para os quais
km +k °1
kn +k2 °1,
é inteiro.
3. TEORIA DOS NÚMEROS
Começamos esta seção, destacando um resultado simples, porém bastante útil, quando tratamos
de polinômios com coeficientes inteiros:
Se P (x) 2Z[x], e a,b são inteiros, então a °b | P (a)°P (b).
3Isto é, com coeficiente líder igual a 1
4
Ana Paula Chaves
Ana Paula Chaves
Relembrando que um polinômio emZ[x] é irredutível sobreZ, se não pode ser escrito como o produto
de dois polinômios com coeficientes inteiros. Resultados bastante conhecidos neste tópico, são:
Lema de Gauss: Seja P (x) 2 Z[x] um polinômio. Então, P (x) é irredutível sobre Z se, e somente se, é
irredutível sobreQ.
Critério de Eisenstein: Seja P (x) = an xn +an°1xn°1+·· ·+a1x+a0 2Z[x] um polinômio e p 2P, tal que
p divide a0, a1, . . . , an°1, mas p 6 |an e p2 6 |a0, então P (x) é irredutível.
Critério de Perron: Seja P (x) = xn +an°1xn°1 +·· ·+a1x +a0 2Z[x] um polinômio com a0 6= 0 e
|an°1| > 1+|an°2|+ · · ·+ |a1|+ |a0| .
Então P (x) é irredutível.
Complementamos esta seção, com os seguintes resultados, também bastante conhecidos. O primeiro,
Lema de Schur, afirma que existem infinitos divisores primos dos termos da sequência (P (n))n2N. Já
o segundo resultado, nos dá uma forma rápida de encontrar raízes racionais de um polinômio com
coeficientes inteiros.
Lema de Schur: Seja P (x) 2 Z[x] um polinômio não constante. Então existem infinitos primos entre os
divisores dos termos P (1),P (2),P (3), . . ..
Teste da raiz racional: Seja P (x) = an xn +an°1xn°1 +·· ·+a1x +a0 2Z[x]. Se p/q 2Q, com (p, q) = 1, é
uma raiz de P (x), então p|a0 e q|an.
3.1. Warm-up.
Problema 3.1: Seja p 2P. Mostre que P (x) = xp°1 +xp°2 +·· ·+x +1 é irredutível.
Problema 3.2: (Czech-Slovak1998) Um polinômio P (x) de grau n ∏ 5 com coeficientes inteiros e n raízes
inteiras distintas, são dados. Encontre todas as raízes inteiras de P (P (x)), sabendo que 0 é raiz de P (x).
Problema 3.3: Para quais valores de n, o polinômio 1+ x2 + x4 + ·· · + x2n°2 é divisível pelo polinômio
1+x +x2 +·· ·+xn°1
5
Ana Paula Chaves
3.2. Problemas.
Problema 3.4: Dado um número primo, associe a ele um polinômio cujos coeficientes são os dígitos
decimais desse primo (por exemplo, 9x3 + 4x2 + 3 para o primo 9403). Mostre que este polinômio é
sempre irredutível.
Problema 3.5: Sejam P (x) e Q(x) polinômios mônicos não constantes, com coeficientes inteiros. Para
todo n suficientemente grande, P (n) e Q(n) possuem os mesmos divisores primos. Mostre que P (x) ¥
Q(x).
Problema 3.6:(Irã 2007) Existe uma sequência de inteiros a0, a1, a2, . . ., tais que (ai , a j ) = 1 para i 6= j ,
e, para todo inteiro positivo n, o polinômio
nX
i=0
ai x
i é irredutível?
Problema 3.7: (Russia 2006) Um polinômio (x+1)n°1 é divisível pelo polinômio P (x) = xk+ak°1xk°1+
·· · + a1x + a0, de grau k par, e tal que todos os seus coeficientes são inteiros ímpares. Mostre que n é
divisível por k +1.
"Problema 3.8: (USAMO 2006) Para um inteiro m, seja p(m) o maior divisor primo de m. Por conven-
ção, definimos p(±1) = 1 e p(0) =1. Encontre todos os polinômios f com coeficientes inteiros tais que a
sequência {p( f (n2))°2n}n∏0 é limitada superiormente. (Em particular, f (n2) 6= 0, para n ∏ 0)
Problema 3.9: (IMO SL 2009) Seja P (x) um polinômio não-constante com coeficientes inteiros. Mostre
que não existe função T :Z!Z, tal que a quantidade de inteiros x onde T n(x) = x é igual a P (n)m para
todo n inteiro positivo, onde T n é a composição n°ésima se T .
"Problema 3.10: (Canadá) Seja P (x) um polinômio com coeficientes inteiros. Suponha que existam
quatro inteiros a,b,c e d, tais que P (a) = P (b) = P (c) = P (d) = 5. Prove que não existe k inteiro, tal que
P (k) = 8.
4. RAÍZES DA UNIDADE E POLINÔMIOS CICLOTÔMICOS
Um número complexo ≥ é dito uma raíz n-ésima da unidade, se ≥n = 1. Equivalentemente, as
raízes n°ésimas da unidade são precisamente as raízes do polinômio xn°1. Esse polinômio não possui
raízes múltiplas, donde existem precisamente n raízes n°ésimas da unidade.
Observação 4.1. Alguns fatos importantes, são:
6
i) O conjunto das raízes n°ésimas da unidade é um grupo abeliano multiplicativo de ordem n4, que
denotamos por Rn ;
ii) Pela fórmula de Moivre, as n°ésimas raízes da unidade, são dadas por ≥k = e2kºi /n , com 0 ∑ k ∑
n °1, cujos argumentos são múltiplos de 2º/n;
iii) Seja d a ordem de ≥ 2Rn . Então, a ordem de ≥k é igual a d/(k,d).
iv) (Geometria) As raízes n°ésimas da unidade são os vértices de um n°ágono regular inscrito no
círculo unitário;
v) Se ≥ é uma raiz n°ésima da unidade e ≥ 6= 1, então 1+≥+≥2 +·· ·+≥n°1 = 0.
vi) Seja ≥= e2ºi /n . Então, xn °1 = (x °1)(x °≥)(x °≥2) · · · (x °≥n°1).
vii) Temos que
1+≥m +≥2m +·· ·+≥(n°1)m =
8
>><
>>:
n, se ,n | m,
0, c.c.
Dizemos que ª é uma raiz primitiva n°ésima da unidade se é uma raiz n°ésima da unidade e
Rn =< ª>= {1,ª,ª2, . . . ,ªn°1}. Assim, temos que ≥k = e2ºi k/n é uma raiz primitiva n°ésima da unidade
se, e somente se, (k,n) = 1. Portanto, temos exatamente ¡(n) raízes n°ésimas primitivas da unidade
O n°ésimo polinômio ciclotômico, ©n(x), é o polinômio cujas raízes são as n°ésimas raízes pri-
mitivas da unidade.
Observação 4.2. Sobre o n°ésimo polinômio ciclotômico, temos alguns fatos importantes:
i) ©n(x) tem grau ¡(n);
ii) Como os elementos de Rn são precisamente as raízes n°ésimas da unidade, e cada uma destas
têm ordem dividindo n, obtemos a seguinte fatoração
xn °1 =
Y
d |n
d>0
©d (x).
Lema 4.1. Seja p um polinômio e Æ uma raiz n°ésima primitiva da unidade. Denote por p[n] o coefi-
ciente do termo xn em p. Então, temos que
X
Ø2Rn
p(Ø) =
n°1X
k=0
p(Æk ) = n(p[0]+p[n]+p[2n]+·· · )
A seguir, enunciamos dois resultados poderosos sobre polinômios ciclotômicos. A partir deles,
conseguiremos calcular, sem tantas dificuldades, as formas explícitas destes polinômios em casos es-
peciais.
Teorema 1. Seja n um inteiro positivo. Então,
4Um conjunto G , munido de uma operação ·, é dito um grupo, se: (i) a ·b 2G ,8a,b 2G ; (ii) 9 e 2G , tal que a ·e = e ·a =
a; (iii) 8a 2G ,9 a tal que a ·a = a ·a = e; (iv) (a ·b)·c = a ·(b ·c). Dizemos que o (G , ·) é abel i ano se a operação é comutativa,
ou seja, se a ·b = b ·a,8a,b 2G . A ordem de G , denotada |G|, é a cardinalidade de G .
7
(a) ©n(x) 2Z[x];
(b) ©n(x) é irredutível sobre Z e portanto sobreQ.
A primeira consequência imediata do Teorema acima é a que a fatoração
(1) xn °1 =
Y
d |n
d>0
©n(x),
é de fato a fatoração de xn °1 em polinômios irredutíveis sobre Z (e portantoQ). Contudo, primeiro
vejamos um método para calcular©n(x) explicitamente. Vamos utilizar (1) para obter recursivamente
tal forma explícita, dependendo da quantidade de fatores primos de n. Vamos ilustrar o método, com
alguns casos simples.
Seja p 2P. Então, por (1), xp °1 =©1(x)©p (x) = (x °1)©p (x), donde
©p (x) =
xp °1
x °1 = x
p°1 +xp°2 +·· ·+1.
Usando a mesma ideia, temos por exemplo que xp
2 °1 =©p2 (x)©p (x)©1(x) =©p2 (x)(xp °1), e assim,
©p2 (x) =
xp
2 °1
xp °1 =
(xp )p °1
xp °1 = x
p(p°1) +xp(p°2) +·· ·+xp +1.
Para darmos um último exemplo antes do próximo resultado, tome p, q primos distintos. Temos então
que xpq °1 =©pq (x)©p (x)©q (x)©1(x), daí
©pq (x) =
xpq °1
(x °1)(xp°1 +xp°2 +·· ·+1)(xq°1 +xq°2 +·· ·+1) .
Uma aplicação imediata desta última, nos dá
©6(x) =
x6 °1
(x °1)(x +1)(x2 +x +1) =
(x3 °1)(x3 +1)
(x3 °1)(x +1) = x
2 °x +1.
Mais algumas fórmulas são obtidas no seguinte resultado.
Lema 4.2. :
(a) ©pr (x) =©p (xp
r°1
), para p primo e r > 0;
(b) ©n(x) =©p1···ps (xp
r1°1
1 ···p
rs°1
s ), onde n = pr11 · · ·p
rs
s é a fatoração em primos;
(c) ©2n(x) =©n(°x), para n ∏ 3 ímpar;
(d) ©pn(x) =©n(xp )/©n(x), para p primo e p 6 |n.
8
Combinando as propriedades (b) e (d), é possível explicitar qualquer polinômio ciclotômico.
Abaixo, listamos os primeiros 13:
©1(x) = x °1
©2(x) = x +1
©3(x) = x2 +x +1
©4(x) = x2 +1
©5(x) = x4 +x3 +x2 +x +1
©6(x) = x2 °x +1
©7(x) = x6 +x5 +x4 +x3 +x2 +x +1
©8(x) = x4 +1
©9(x) = x6 +x3 +1
©10(x) = x4 °x3 +x2 °x +1
©11(x) = x10 +x9 +x8 +x7 +x6 +x5 +x4 +x3 +x2 +x +1
©12(x) = x4 °x2 +1
©13(x) = x12 +x11 +x10 +x9 +x8 +x7 +x6 +x5 +x4 +x3 +x2 +x +1
As fatorações de polinômios da forma xp
n °1, para p primo, podem ser obtidas como aplicação
direta de (b):
xp
n °1 =©1(x) ·
nY
k=1
©pk (x) = (x °1)
n°1Y
k=0
©p (x
pk ),
o que nos dá para p = 2 e p = 3,
x2
n °1 = (x °1)
n°1Y
k=0
(x2
k +1), x3n °1 = (x °1)
n°1Y
k=0
(x2·3
k +x3k +1).
4.1. Warm-up.
Problema 4.1: Encontre todos os n 2N, tais que o polinômio x2n +xn +1 é divisível por x2 +x +1.
Problema 4.2: Seja n um múltiplo de 3. Calcule
√
n
0
!
+
√
n
3
!
+
√
n
6
!
+·· ·+
√
n
n
!
.
9
Problema 4.3: (Putnam 1955) Seja A1 A2 . . . An um n°ágono regular inscrito numa circunferência de
centro O e raio R. No segmento O A1, escolha P tal que A1 está entre O e P . Mostre que
nY
i=1
|PAi | = |PO|n °Rn .
4.2. Problemas.
Problema 4.4: Sejam n um inteiro positivo ímpar, e ≥= cos(2º/n)+ i sin(2º/n). Calcule
1
1+1 +
1
1+≥ +
1
1+≥2 +·· ·+
1
1+≥n°1 .
Problema 4.5: Seja f (x) =Pi ai xi um polinômio e ≥= e2ºi /n . Mostre que
f (x)+ f (≥x)+ f (≥2x)+·· ·+ f (≥n°1x)
n
=
X
n|i
ai xi .
Problema 4.6: (USAMO 1977) Encontre todos os pares (m,n) de inteiros positivos, tais que
1+x +x2 +·· ·+xm | 1+xn +x2n +·· ·+xmn .
Problema 4.7: (IMO 1995) Seja p um primo ímpar. Encontre a quantidade de subconjuntos de p ele-
mentos do conjunto {1,2, . . . ,2p} cuja soma é divisível por p.
Problema 4.8: Mostre que cos(º/7) é raiz de um polinômio cúbico com coeficientes inteiros.
Problema 4.9: (Leningrado 1991) Uma sequência finita a1, a2, . . . , an é dita p°balanceada se todas as
somas da forma ak +ak+p +ak+2p +·· · são iguais, para todo k = 1,2, . . . , p. Mostre que se a sequênciacom 50 elementos é p°balanceada para p = 3,5,7,11,13,17, então todos os elementos são iguais a
zero.
Problema 4.10: (India 2015) Seja!= e2ºi /5. Mostre que não existem inteiros positivos a1, a2, a3, a4, a5, a6
tais que o seguinte produto é inteiro:
(1+a1!)(1+a2!)(1+a3!)(1+a4!)(1+a5!)(1+a6!).
10
5. DICAS E SOLUÇÕES
Problema 2.1: Escreva o polinômio f (x) como a(x ° x1)(x ° x2), donde f (x) f (x + 1) = a2(x ° x1)(x °
x2)(x +1° x1)(x +1° x2), e então efetue os produtos (x ° x1)(x +1° x2) e (x +1° x1)(x ° x2) para obter
g (x) = a2(x °x1)(x °x2) e h(x) = x2 ° (x1 +x2 °1)x +x1x2.
Problema 2.3: Utilizando Interpolação de Lagrange para os n +1 valores f (k) = k/(k +1), obtém-se
f (n +1) =
nX
i=0
i
i +1
Y
1∑ j∑n
j 6=i
n +1° j
i ° j .
Analisando o produtório separadamente,
Y
1∑ j∑n
j 6=i
n +1° j
i ° j =
(n +1)(n)(n °1) · · · (n ° i +2)(n ° i ) · · · (2)(1)
(i )(i °1) · · · (1)(°1)(°2) · · · (°(n ° i )) =
(n +1)!
i !(n +1° i )! · (°1)
n°i ,
donde
f (n +1) =
nX
i=0
i
i +1 ·
(n +1)!
i !(n +1° i )! · (°1)
n°i .
Usando i /(i+1) = 1°1/(i+1) e efetuando algumas manipulações para obter binômios do tipo (1°1)n+1,
obtemos
f (n +1) = 1° (°1)
n +1
n +2 = 1 se n é ímpar, e
n
n +2 caso contrário.
REFERÊNCIAS
[1] F. B. Martinez, C. G. A. T. Moreira, N. Saldanha, E. Tengan, Teoria dos Números: Um passeio com primos e outros números
familiares pelo munto inteiro, 3ª Ed. (Projeto Euclides),IMPA, Rio de Janeiro, (2013) 497pp.
[2] P. B. Bhattacharya, S. K. Jain, S. R. Nagpaul, Basic Abstract Algebra, Cambridge University Press, Cambridge, (1994)
487pp.
[3] S. Lang, Algebra, Graduate Texts in Mathematics (211), Springer Science & Business Media, (2005) 914pp.
[4] T. Andreescu, Z. Feng, 101 Problems in Algebra, Vol. 18, Australian Mathematics Trust, (2001) 139pp.
[5] Art of Problem Solving - https://artofproblemsolving.com/
11
	1. Introdução
	2. Álgebra
	2.1. Warm-up
	2.2. Problemas
	3. Teoria dos Números
	3.1. Warm-up
	3.2. Problemas
	4. Raízes da Unidade e Polinômios Ciclotômicos
	4.1. Warm-up
	4.2. Problemas
	5. Dicas e Soluções
	Referências