Resto de divisão polinomial e congruência

por **gilberto97** Qua 27 Jan 2016, 21:29

Olá a todos. Encontrei na última prova do ita a questão 29 que pergunta o resto da divisão de (1+x+x²)^40 por (1+x)^3. A resposta é 820x² + 1600x + 781. Minha pergunta é:

É possível obter esse resto utilizando congruência? Algo como (1+x+x²)^40 = R mod [(1+x)^3].

por Convidado Qua 27 Jan 2016, 21:42

Oi amigo, boa noite.

Tem sim, e a ideia é muito parecida com os inteiros. Você pode encontrar toda a teoria de congruência para polinômios nesse material disponibilizado pelo site do Rumo ao ITA:

Material e Congruência - Rumo ao ITA

Espero que te ajude, abraço!

por Convidado Qui 28 Jan 2016, 00:38

Como exemplo da questão do ITA, veja que podemos escrever 1+x+x² na forma de x(x+1)+1 e, então podemos expandir o binômio:

(x(x+1)+1)^{40} \equiv \sum_{n=0}^{40} \binom{40}{n}[x(x+1)]^n \mod (1+x)^3

Só que: [x(x+1)]ⁿ = xⁿ(x+1)ⁿ que por sua vez, podemos fatorar todos os termos (x+1)ⁿ em que n ≥ 3 de forma que:

\tiny (x^2+x+1)^{40} \equiv \underset{\equiv 0}{\underbrace{(x+1)^3}}\;\sum_{n=3}^{40} \binom{40}{n}x^n(x+1)^{n-3} + \binom{40}{2}x^2(x+1)^2+\binom{40}{1}x(x+1)+\binom{40}{0}\mod (1+x)^3

Uma vez que (x+1)^3 \equiv 0 \mod (x+1)^3 , teremos:

(x^2+x+1)^{40} \equiv \binom{40}{2}x^2(x+1)^2+\binom{40}{1}x(x+1)+\binom{40}{0}\mod (1+x)^3

(x^2+x+1)^{40} \equiv 780x^4+1560x^3+820x^2+40x+1 \mod (1+x)^3

\small \\ (x^2+x+1)^{40} \equiv 780x \underset{\equiv 0}{\underbrace{(x^3+3x^2+3x+1)}}-780x^3-1520x^2-740x+1 \mod (1+x)^3

\small (x^2+x+1)^{40} \equiv -780 \underset{\equiv 0}{\underbrace{(x^3+3x^2+3x+1)}}+820x^2+1600x+781 \mod (1+x)^3

(x^2+x+1)^{40} \equiv 820x^2+1600x+781 \mod (1+x)^3

Dei uma olhada nas resoluções dos cursinhos e o método que a maioria usou pareceu ser bem mais eficiente que fazer por congruência. Verifique nas apostilas que eu te passei os tipos de exercícios que merecem o uso de congruência.
Espero ter te ajudado, abraço!

por **gilberto97** Qui 28 Jan 2016, 00:47

Perfeito Gabriel. A maioria dos cursinhos utilizou derivadas e no caso do objetivo binômio de Newton seguido de método da chave. Eu particularmente prefiro congruência até porque estou estudando esse assunto agora.

Muito obrigado!

por Convidado Qui 28 Jan 2016, 01:24

Veja este exercício que encontrei aqui no fórum:

Divisão polinomial

Outro exemplo. Se você conseguir fazer sem desenvolver o numerador, poste lá. Abraço!