quarta-feira, 20 de junho de 2012

050-Equação de Congruência Polinomial

Nesta introdução às equações de congruência  mais gerais, trataremos apenas do número de soluções, onde veremos o teorema de Lagrange ([;1736-1813;]) que relaciona o número de raízes incongruentes [;mod;] [;m;] com o grau de uma equação de congruência polinomial.

Conforme vimos no post anterior, infinitas raízes de uma equação de congruência podem ser organizadas em classes de equivalência [;mod;] [;m;], sendo que a quantidade destas classes pode ser finita. Dentro de uma mesma classe, cada raíz é congruente [;mod;] [;m;] com qualquer outra considerada. Já as raízes de classes diferentes são todas incongruentes [;mod;] [;m;]. Convenciona-se que cada classe representa uma única raíz da equação de congruência. Assim, o número de classes de equivalência será o número de raízes incongruentes [;mod;] [;m;].

Também vimos que uma equação de congruência linear, embora de grau [;1;], pode ter mais de uma raíz incongruente [;mod;] [;m;]. O mesmo acontece com a equação de congruência polinomial de grau [;>1;], ou seja, o número de soluções incongruentes [;mod;] [;m;] pode ser menor (inclusive zero) ou maior que o grau da equação.

Foi demonstrado que o número de soluções incongruentes [;mod;]  [;m;] da equação de congruência linear [;ax \equiv b;] ([;mod;] [;m;] ) é [;d=(a,m);], ou seja, o máximo divisor comum de [;a;] e [;m;].

Referente a equação de congruência polinomial de grau [;n;], o teorema de Lagrange diz que, se o módulo de congruência da equação for  [;m=p;] primo e [;A_n \not \equiv 0;] ([;mod;] [;p;]), sendo [;A_n \neq 0;] o coeficiente do termo de maior grau, então esta equação tem, no máximo, [;n;] soluções incongruentes [;mod;] [;p;]. A demonstração deste teorema é o objetivo deste post.

Sejam
[;n \in \mathbb{N};]

[;A_0;], [;A_1;],...,[;A_n;] [;\in \mathbb{Z};], com [;A_n \neq 0;] e

[;x \in \mathbb{Z};].

Nestas condições, a expressão

[;P(x)=A_nx^n+A_{n-1}x^{n-1}+...+A_1x+A_0;]

é chamada de polinômio inteiro na variável [; x;], com [;P(x) \in \mathbb{Z};]

Seja, também, [;m \in \left{2,3,...\right};]. Calcular valores de [; x;], de forma que [;m|P(x);], é resolver a equação de congruência polinomial

[;A_nx^n+A_{n-1}x^{n-1}+...+A_1x+A_0 \equiv 0;]  ([;mod;] [;m;]

Neste caso, temos que encontrar os inteiros [; x;], onde [;P(x)=;] múltiplo de [;m;]. Assim, [;x_0;] será uma raiz particular de [;P(x);] se

[;P(x_0) \equiv 0;] ([;mod;] [;m;] )

Assim todo [;x \equiv x_0;] ([;mod;] [;m;] ) representa uma única raiz incongruente módulo [;m;] desta equação ( classe de equivalência de [;x_0;] ).


Lema [;1;] ( Teorema da fatoração ). Se  [;x \equiv a;] ([;mod;] [;m;] ) é raiz de [;P(x) \equiv 0;] ([;mod;] [;m;] ) de grau [;n;], então [;P(x) \equiv (x-a)G(x);] ([;mod;] [;m;] ), onde [;G(x);] é um polinômio inteiro de grau [;n-1;].

Demonstração. Tendo em vista que [;x \equiv a;] ([;mod;] [;m;] ) não implica necessariamente que [;x=a;], temos que pelo quociente de Newton, [;\frac{P(x)-P(a)}{x-a};] resulta em um polinômio de grau [;n-1;] em [; x;]. Seja [;G(x);] este resultado. Assim,

[;\frac{P(x)-P(a)}{x-a}=G(x) \Rightarrow;]  

[;P(x)-P(a)=(x-a)G(x);] 

Pela propriedade reflexiva, temos que

     [;P(x)-P(a) \equiv (x-a)G(x);] ([;mod;] [;m;] )
Mas, por hipótese

[;P(a) \equiv 0;] ([;mod;] [;m;]

E pela propriedade da soma algébrica (prop [;2;]) :

[;P(x)-P(a)+P(a) \equiv (x-a)G(x)+0;] ([;mod;] [;m;] ) [;\Rightarrow;]

[;P(x) \equiv (x-a)G(x);] ([;mod;] [;m;] )

A recíproca deste teorema é válida. Se partimos de [;P(x) \equiv (x-a)G(x);] ([;mod;] [;m;] ) e queremos mostrar que [;P(a) \equiv 0;] ([;mod;] [;m;] ), fazemos da seguinte forma:

Desde que a condição [;x \neq a;] já não é mais necessária, é óbvio que  [;P(a) \equiv (a-a)G(x);] ([;mod;] [;m;] ) [;\Rightarrow;] [;P(a) \equiv 0;] ([;mod;] [;m;] ).


Lema [;2;]. Sejam [;p;] um primo e [;f(x);], [;g(x);] e [;h(x);]  três polinômios inteiros, tais que [;f(x) \equiv g(x)h(x);] ([;mod;] [;p;] ). Seja também [;a \in \mathbb{Z};] uma raiz de [;f(x) \equiv 0;]([;mod;] [;p;]).

Então, [;f(a) \equiv 0;] ([;mod;] [;p;]) implica em [;g(a) \equiv 0;] ([;mod;] [;p;]) ou [;h(a) \equiv 0;] ([;mod;] [;p;]

Demonstração: [;f(a) \equiv 0;] ([;mod;] [;p;]) [;\Rightarrow;] [;g(a)h(a) \equiv 0;] ([;mod;] [;p;]), portanto [;p|[g(a)h(a)];].

Como [;p;] é primo, temos [;p|g(a);]  ou [;p|h(a);]. Logo,  [;g(a) \equiv 0;] ([;mod;] [;p;]) ou [;h(a) \equiv 0;] ([;mod;] [;p;]). 

Teorema de Lagrange. Seja [;p;]um primo, onde [;A_n \not \equiv 0;] ([;mod;] [;p;]) e

[;A_nx^n+A_{n-1}x^{n-1}+...+A_1x+A_0 \equiv 0;]  ([;mod;] [;p;])

Então esta equação tem, no máximo, [;n;] raízes incongruentes módulo [;p;].

Demonstração. Será por indução sobre o grau [;n;].

[;a);] Se [;n=0;], temos [;P(x)=A_n \not \equiv 0;] ([;mod;] [;p;]), por hipótese, e a equação não tem solução. Logo, o teorema é válido neste caso;

[;b);] Vamos supor que o teorema seja verdadeiro para um polinômio inteiro de grau [;\leq n-1;] e em seguida mostraremos que isto implica a validade do teorema para o grau [;n;];

[;c);] Se [;P(x) \equiv 0;] ([;mod;] [;p;]), de grau [;n;], for insolúvel em [;\mathbb{Z};], o teorema ainda continua válido; 

[;d);] Suponha, então, que [;P(x) \equiv 0;] ([;mod;] [;p;]), de grau [;n;], admita a raíz [;x \equiv a;] ([;mod;] [;p;]). Pelo lema [;1;], temos que

 [;P(x) \equiv (x-a)G(x);] ([;mod;] [;p;]),

com [;G(x);]de grau [;n-1;]  

[;e);] Como [;(1,p)=1;], a equação de congruência linear  [;(x-a) \equiv 0;] ([;mod;] [;p;]) tem [;1;] raíz incongruente módulo [;p;], ou seja  [;x \equiv a;] ([;mod;] [;p;]);

[;f);] Pela hipótese de [;b);], [;G(x);] tem, no máximo, [;n-1;] raízes incongruentes [;mod;] [;p;];

[;g);] E sendo [;p;] um primo, pelo lema [;2;] qualquer outra raíz particular [;x=b;] de [;P(x) \equiv 0;] ([;mod;] [;p;]) ou é raíz de [;(x-a) \equiv 0;] ([;mod;] [;p;]) ou é raíz de [;G(x) \equiv 0;] ([;mod;] [;p;]). Assim, ou [;b \equiv a;] ([;mod;] [;p;]) (mesma raíz) ou [;b;] é congruente à uma das raízes de [;G(x) \equiv 0;] ([;mod;] [;p;]);

[;h);] Logo, a equação [;P(x) \equiv 0;] ([;mod;] [;p;]) de grau [;n;] tem, no máximo, [;n;] raízes incongruentes módulo [;p;].



Tópicos Relacionados

Equação de Congruência Linear
Fundamentos de Congruência Modular  


Referência Bibliográfica 

Teoria dos Números, de Salahoddim Shokranian, Marcus Soares e Hemar Godinho; Editora UNB, 1999;
O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Ciência Moderna, 2000;
Funções Aritméticas  - Números Notáveis, de Edgard de Alencar Filho, Editora Nobel,1988. 

 

3 comentários:

  1. Excelente post. Sempre apanho muito dessa parte da teoria dos números. Vou ler o post novamente.
    Dá uma olhada nesse artigo, é bem interessante.

    http://www.rumoaoita.com/site/matematica/72-topicos-adicionais/65-apostila-de-congruencia

    Têm alguns exemplos no uso de congruência linear na fatoração de polinômios (abordagem um pouco mais simplista).
    Dá uma olhada no post que fiz sobre o Teorema de Newton que você havia citado no fatosmatemáticos.

    http://hugocito.wordpress.com/

    ResponderExcluir
  2. Oi, Hugocito!

    Já salvei este interessante PDF.

    Sobre o teorema de Newton, vi no seu blog e gostei bastante. Deixei um comentário lá.

    Obrigado!

    ResponderExcluir
  3. Os símbolos não estão aparecendo.

    ResponderExcluir