(2 pts) Seja
um corpo e
o conjunto dos polinômios com coeficientes em
.
(a) Enuncie o algoritmo da divisão para o conjunto
.
(b) Execute o algoritmo da divisão para
em
a em
.
(a) Enuncie o algoritmo da divisão para o conjunto
(b) Execute o algoritmo da divisão para
Passo 1
O enunciado pede duas coisas distintas:
- (a) Enunciar o algoritmo da divisão para o conjunto
. - (b) Executar esse algoritmo para dividir
por em duas situações: em e em .
Informações relevantes dadas:
Não foi dada nenhuma outra restrição; portanto
é não nulo e podemos aplicar o algoritmo da divisão em corpos (como
e
).
Passo 2
Enunciado do algoritmo da divisão (forma usual, curto e preciso):
Seja
um corpo. Dados
com
, então existem polinômios únicos
tais que
e
Algoritmo construtivo (procedimento para obter
e
):
- Notação: escrevemos
para o coeficiente líder de um polinômio e para seu grau. - Enquanto
: - Calcule o monômio
. Aqui a divisão de coeficientes é em . - Atualize
. - Atualize
.
- Calcule o monômio
- Quando
, o polinômio atual é o resto e o acumulado é o quociente.
Explicação didática do porquê funciona (resumo):
- Cada iteração reduz o grau do polinômio restante, porque subtraímos o termo de maior grau. Como os graus são inteiros não-negativos, o processo termina em número finito de passos.
- A unicidade decorre do fato de que se existissem
e com e , então . O lado direito tem grau menor que (ou é zero), então deve ser zero, implicando e .
Passo 3
Agora aplicamos o algoritmo em
.
Dados:
Vamos executar passo a passo mantendo todas as contas.
1ª iteração: comparar graus:
,
. Dividimos o termo líder:
Monômio a subtrair:
Multiplicamos e subtraímos:
Subtraindo de
:
Atualizamos: quociente parcial
e resto atual
.
Passo 4
2ª iteração: agora
. Dividimos termo líder:
Monômio:
Multiplicamos e subtraímos:
Subtraindo:
Atualizamos: quociente
e resto atual
.
Passo 5
Agora
, portanto o algoritmo termina. Concluímos em
:
Verificação (checar que
):
Multiplicamos :
Multiplicamos
Somando o resto:
que é exatamente
. Verificação OK.
Passo 6
Agora aplicamos o algoritmo em
. Primeiro reescrevemos os coeficientes de
e
reduzidos módulo
.
Reduções módulo
:
Portanto, trabalharemos com:
(Neste passo eu transformei os coeficientes de
e
usando as congruências acima.)
Passo 7
Executando a divisão em
:
1ª iteração: divisão do termo líder
por
:
Multiplicação em
:
Subtração (tudo reduzido módulo
):
Quociente parcial
, resto atual
.
Passo 8
2ª iteração: dividir
por
:
Multiplicação:
Reduzindo
módulo
, temos
. Então
Subtração:
Atualizamos quociente
e resto
.
Passo 9
O novo resto tem grau
, logo o algoritmo termina em
. Concluímos:
Verificação rápida (em
): calcular
.
pois
. Somando
:
que coincide com a forma reduzida de
em
. Verificação OK.
Resposta
(a) Sejam
com
. Existem únicos
tais que
O algoritmo construtivo: enquanto
calcular
, fazer
e
; o
final é
.
(b) Em
:
Em
: