Re: [obm-l] Divisão de polinômios

["Bruno França dos Reis" <bfreis@xxxxxxxxx>]

Olá

Bonito o problema. Vou usar um argumento geométrico. Talvez seja melhor
vc tentar explicar um pouco mais as demonstrações, mas lá vai.

Vamos observar algumas coisas a respeito de polinômios.
Def.: Seja q um polinômio qualquer. Vou chamar R(q) o conjunto das raízes do polinômio q, isto é:
R(q) = { z \in C | q(z) = 0 }
(note que estou falando de raizes complexas, nao apenas reais)

OBS: vou trabalhar somente com polinômios mônicos, isto é, polinômios
cujos coeficientes do termo de maior grau são iguais a 1. Isso não tira
a generalidade da teoria: se um polinômio p' for mônico, existe uma
constante K ( = 1/a, onde a é o coef. dominante) tal que p = Kp' é
mônico. Basta então fazer mudanças pequenas com essa constante para
generalizar a teoria.

Lema: Note que, se p = ab, onde a,b são polinômios, então R(p) = R(a) U R(b), certo?
Isto é fácil de provar. Se z é tal que a(z) = 0, então p(z) = a(z) *
b(z) = 0 * b(z) = 0. Logo R(a) está contido em R(p). De forma análoga,
R(b) está contido em R(p). Temos também que, se z é tal que p(z) = 0,
então p(z) = 0 = a(z) * b(z), e como a(z) e b(z) são números reais
(satisfazendo assim os axiomas de corpos), devemos ter que ao menos um
deles é igual a 0, e portanto R(p) está contido em R(a) U R(b). Logo
R(p) = R(a) U R(b).

Cuidado com a recíproca. Para que ela valha, precisamos adicionar uma
hipótese quanto às multiplicidades das raízes de a,b e p. Vamos
enunciar algo um pouco mais fraco que essa recíproca, mas que usaremos:

Lema: Sejam p, q polinômios tais que R(p) contém R(q), e que as
multiplicidades das raízes de q sejam no máximo iguais às de p, podendo
ser menores.. Então existe um polinômio d tal que p = qd, e R(p) = R(q)
U R(d).
Tome o conjunto R(p) = {a_1, a-2, ..., a_n}. Para cada a_i, seja m_i
igual à multiplicidade de a_i em p, se a_i não for raíz de q, ou igual
à diferença entre as multiplicidades de a_i em p e em q. O polinômio d
= prod[i=1..n] {(x-a_i)^(m_i)}, resolve o problema: Ao polinômio q,
adicionamos as raízes de p que não estavam presentes, e aumentamos as
multiplicidades das raízes que já estavam presentes de forma a igualar
os dois polinômios.


É bom também ter na cabeça um tipo de fatoração de polinômios.
Considere x^2 - 1. É fácil ver que x^2 - 1 = (x-1) * (x+1)
E x^3 - 1? Veja que 1 e raiz e faça a divisão, ficando com x^3 - 1 = (x-1)*(x^2 + x + 1).
E x^4 - 1? É de se esperar que x^4 - 1 = (x-1)*(x^3 + x^2 + x + 1)
É de fato o que ocorre. Temos então:
x^n - 1 = (x-1) * (sum[k=0..(n-1)] {x^k}) = (x-1) * (x^(n-1) + x^(n-2) + ... + x^2 + x + 1)
(prove isso)


Mas chega de viajar e voltemos agora ao seu problema.
Vamos fazer umas mudanças nos polinômios. Note inicialmente que p(x) = g(x^1111).
Temos: g(x) * (x-1) = x^10 - 1 = G(x)
Sendo u = x^1111, p(x) = g(u). Seja então P(x) = g(u) * (u - 1) = u^10
- 1 ==> P(x) = x^11110 - 1 = p(x) * h(x), h(x) = x^1111 - 1

Temos então que R(G) = R(g) U {1} e R(P) = R(p) U R(h)

Note que todas as raízes de G são as 10 raízes décimas de 1 (pensando
nos complexos!), e as raízes de P são as 11110 raízes 11110-ésimas de
1. Todos esses números estão sobre a circunferencia |z| = 1, correto?
Ainda mais: R(G) é o conjunto dos vértices de um decágono regular
inscrito na circ |z| = 1, de tal forma que o ponto z = 1 seja um de
seus vértices e R(P) é o cjto dos vértices de um polígono regular de
11110 lados, e z=1 é um de seus vértices.

É fácil notar que R(P) contém R(G): o polígono regular de 11110 lados
pode ser cortado em 10 fatias, tais que cada uma contém 1111 vértices
adjacentes, a partir do vértice z = 1, no sentido anti-horário; o
primeiro vértice de cada um desses pedaços, se unidos aos adjacentes,
formarão um decágono regular. Estes vértices primeiros de cada um dos
10 grupinhos de 1111 vértices são os elementos de R(G)!

Também, R(P) contém R(g), já que este útimo está contido em R(G).

Note agora que R(p) inter R(h) = {}.
Cada raíz de P tem multiplicidade 1. Como P = ph, não pode haver raízes
em comum entre p e h, senão alguma raiz r tal que p(r)=h(r)=0 teria
multiplicidade pelo menos 2 em P, mostrando que R(p) inter R(h) = {}.

Vamos mostrar agora que R(h) inter R(G) = {1}.
É fácil ver que 1 \in R(h) inter R(G). Agora note que 10 e 1111 são
primos entre sí. Assim, caminhando por sobre as raízes de h, a partir
de z=1, no sentido anti-horário, não encontraremos nenhuma raíz de G
(encontraríamos raízes em comum a cada D raízes de h, sendo D o MDC
entre 10 e 1111). Isso é o mesmo que notar que nos polígonos regulares
de 10 e 1111 lados centrados na origem com 1 como vértice não possuem
outros vértices em comum.

Assim, temos que R(h) inter R(g) = {}.

Agora basta notar que R(g) está contido em R(p). Geometricamente, dos
vértices R(P), arrancamos o z=1, e aqueles de h, obtendo R(p). Como
R(g) contido em R(G) contido em R(P), e de R(P) não arrancamos nenhum
vértice que estivesse R(g) para obter R(p), temos que R(g) contido em
R(p).

Em forma de conjuntos, R(P) contém todo mundo: R(g), R(p) e R(h). Temos
que R(p) U R(h) = R(P), e R(g) inter R(h) = {}, o que só é possível se
todos os elementos de R(g) estiverem dentro de R(p) (já que R(p) e R(h)
juntos formam todo o R(P), e não tem nada em comum, e R(g) não tem nada
em comum com R(h)). Mesma conclusão: R(g) contém R(h). Mas
geometricamente é mais bonito!

Além disso, todas as raízes em questão são simples. Então, segundo o lema acima, existe um polinômio d tal que p = gd.


Ufa!
Espero não ter errado em nada aí!
Ficou grande isso, mas pode ser encurtado bastante, ficando um pouco mais complicado de entender.

Qualquer erro, avise que tentarei arrumar!

Abraço
Bruno

On 5/4/06, J. Renan <jrenan@gmail.com> wrote:

Olá à todos da lista, esse é o primeiro tópico que inicio aqui.  Estudando divisibilidade de polinômios me deparei com o seguinte exercício (a fonte diz que é IME, mas não encontrei esse exercício entre os exercícios do IME):

Prove que o polinômio p(x) = x^9999 + x^8888 + x^7777 + ... + x^1111 + 1 é divisível por g(x)= x^9 + x^8 + x^7 + .... + x^1 + 1

Creio eu que tenha que utilizar a teoria das congruências (mod). agradeço desde já pela ajuda.

--
Um Grande Abraço,
Jonas Renan

-- 
Bruno França dos Reis
email: bfreis - gmail.com
gpg-key: 
http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
icq: 12626000

e^(pi*i)+1=0