[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Chines dos Restos para Polinomios
Oi Morgado,
Para ser sincero, eu só tinha visto o link outro dia e
achei diferente. Não li direito, li bem por cima.
Agora que li, achei meio esquisito sim (eu mesmo não
acharia a fórmula no teorema chinês dos restos - eu
gosto mais das suas aplicações, como no problema 6 da
Cone Sul desse ano). Eu sempre achei as duas coisas
bem diferentes.
Mas achei interessante a demonstração não indutiva do
teorema chinês dos restos (eu só conhecia a
demonstração por indução). Apesar disso, a
demonstração por indução tem uma vantagem que é ajudar
a entender os casos "zebrosos" (nos quais os m's não
são primos dois a dois), o que a demonstração do
artigo não cobre bem. Nada contra demonstrações por
indução (ainda mais vindo de mim, que gosto de teoria
dos grafos), é claro, mas achei interessante aprender
outra demonstração.
E no fundo, a parte da analogia usa o que o Claudio
mostrou e, de fato, é bem parecida com aquela
demonstração do teorema chinês.
O que eu acho é que aquela demonstração do teorema
chinês foi "inspirada" na demonstração de que o
polinômio interpolador funciona.
Agora, concordo que aquela parte do final "e se os z's
não são todos distintos?" é, no mínimo, muito
esquisita...
De qualquer forma, peço desculpas se o artigo não tem
um nível de qualidade satisfatório.
[]'s
Shine
--- Augusto Cesar de Oliveira Morgado
<morgado@centroin.com.br> wrote:
> Shine, voce leu o artigo?
> Eu e o Claudio lemos e achamos uma !#&¨&@$%W*!
> Morgado
>
> Em Thu, 24 Jul 2003 11:23:48 -0700 (PDT), Carlos
> Yuzo Shine <cyshine@yahoo.com> disse:
>
> > Oi Claudio e demais membros da lista,
> >
> > Na página do prof. Kahan, de Berkeley, tem um
> artigo
> > traçando um paralelo entre o teorema chinês dos
> restos
> > e o polinômio interpolador de Lagrange (em pdf):
> >
> >
>
http://www.cs.berkeley.edu/~wkahan/MathH90/CRTasLIF.pdf
> >
> > []'s
> > Shine
> >
> >
> > --- Claudio Buffara <claudio.buffara@terra.com.br>
> > wrote:
> > > Oi, Pessoal:
> > >
> > > Por favor desconsiderem a ultima frase da
> mensagem
> > > abaixo. Eu troquei as
> > > bolas. Realmente, um polinomio p(x) sobre Q[x]
> ou
> > > R[x] possui um inverso se
> > > e somente se p(x) = a, onde a eh um numero
> (racional
> > > ou real) nao nulo, ou
> > > seja, grau(p(x)) = 0.
> > >
> > > No entanto, dado um polinomio q(x), primo com
> p(x),
> > > existem polinomios r(x)
> > > e s(x) tais que r(x)*p(x) + s(x)*q(x) = 1
> (Teorema
> > > de Bezout para
> > > polinomios, que pode ser demonstrado de forma
> > > totalmente analoga ao caso
> > > inteiro).
> > >
> > > Mas isso quer dizer que r(x) eh um inverso de
> p(x)
> > > (mod q(x)) e s(x) um
> > > inverso de q(x) (mod p(x)).
> > >
> > > Ou seja, eu confundi os conceitos de inverso
> > > absoluto com inverso (mod m).
> > > Nada como uma boa noite de sono pra clarear as
> > > ideias...
> > >
> > > -----
> > >
> > > Suponhamos que estejamos trabalhando sobre Q[x]
> ou
> > > R[x] ou, em geral, sobre
> > > F[x] onde F eh um corpo qualquer.
> > >
> > > m(x) e n(x) sao primos entre si ==>
> > > existem m1(x) e n1(x) tais que:
> > > m(x)*m1(x) == 1 (mod n(x)) e n(x)*n1(x) == 1
> > > (mod m(x))
> > >
> > > Tomemos f(x) = a(x)*n(x)*n1(x) + b(x)*m(x)*m1(x)
> > >
> > > Nesse caso:
> > > f(x) == a(x) (mod m(x)) e f(x) == b(x) (mod
> > > n(x))
> > >
> > > Suponhamos que exista g(x) tal que:
> > > g(x) == a(x) (mod m(x)) e g(x) == b(x) (mod
> > > n(x))
> > >
> > > Entao teremos:
> > > f(x) == g(x) (mod m(x)) e f(x) == g(x) (mod
> > > n(x))
> > >
> > > E como m(x) e n(x) sao primos entre si:
> > > f(x) == g(x) (mod m(x)*n(x))
> > >
> > > Ou seja, f(x) eh unico (mod m(x)*n(x)).
> > >
> > >
> > > Um abraco,
> > > Claudio.
> > >
> > >
> > > *****
> > >
> > >
> > > on 24.07.03 00:30, Claudio Buffara at
> > > claudio.buffara@terra.com.br wrote:
> > >
> > > > Caros colegas da lista:
> > > >
> > > > Eh bem sabido que se m e n sao inteiros primos
> > > entre si, entao o sistema de
> > > > congruencias:
> > > > x == a (mod m)
> > > > x == b (mod n)
> > > > tem uma solucao unica (mod m*n) para quaisquer
> > > inteiros a e b.
> > > > Esse eh justamente o Teorema Chines dos
> Restos.
> > > >
> > > > Um problema que eu resolvi hoje na lista me
> fez
> > > pensar numa generalizacao
> > > > para polinomios:
> > > > Sejam m(x) e n(x) dois polinomios primos entre
> si.
> > > > Dados polinomios quaisquer a(x) e b(x), serah
> que
> > > existe um polinomio f(x)
> > > > que deixe resto a(x) quando dividido por m(x)
> e
> > > deixe resto b(x) quando
> > > > dividido por b(x)?
> > > > Caso exista, sob que condicoes f(x) serah
> unico
> > > (isto eh, unico a menos da
> > > > adicao de multiplos de m(x)*n(x))?
> > > > Os resultados acima serao validos tanto em
> Z[x]
> > > quanto em Q[x] ou R[x]?
> > > > E quanto a Z/(p)[x]?
> > > >
> > > > A demonstracao padrao (construtiva) do TCR nao
> se
> > > estende a aneis de
> > > > polinomios pois envolve inversos mod m e mod
> n, os
> > > quais nao existem se m e
> > > > n forem polinomios nao constantes.
> > > >
> > > > Um abraco,
> > > > Claudio.
> > > >
> > >
> > >
> >
>
=========================================================================
> > > Instruções para entrar na lista, sair da lista e
> > > usar a lista em
> > >
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> > >
> >
>
=========================================================================
> >
> >
> > __________________________________
> > Do you Yahoo!?
> > Yahoo! SiteBuilder - Free, easy-to-use web site
> design software
> > http://sitebuilder.yahoo.com
> >
>
=========================================================================
> > Instruções para entrar na lista, sair da lista e
> usar a lista em
> >
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> >
>
=========================================================================
> >
> >
>
>
=========================================================================
> Instruções para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
=========================================================================
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================