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 () que relaciona o número de raízes incongruentes 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 , sendo que a quantidade destas classes pode ser finita. Dentro de uma mesma classe, cada raíz é congruente com qualquer outra considerada. Já as raízes de classes diferentes são todas incongruentes . 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 .
Também vimos que uma equação de congruência linear, embora de grau , pode ter mais de uma raíz incongruente . O mesmo acontece com a equação de congruência polinomial de grau , ou seja, o número de soluções incongruentes pode ser menor (inclusive zero) ou maior que o grau da equação.
Foi demonstrado que o número de soluções incongruentes da equação de congruência linear ( ) é , ou seja, o máximo divisor comum de e .
Referente a equação de congruência polinomial de grau , o teorema de Lagrange diz que, se o módulo de congruência da equação for primo e ( ), sendo o coeficiente do termo de maior grau, então esta equação tem, no máximo, soluções incongruentes . A demonstração deste teorema é o objetivo deste post.
Sejam
,
, ,..., , com e
.
Nestas condições, a expressão
é chamada de polinômio inteiro na variável , com .
Seja, também, . Calcular valores de , de forma que , é resolver a equação de congruência polinomial
( )
Neste caso, temos que encontrar os inteiros , onde múltiplo de . Assim, será uma raiz particular de se
Equação de Congruência Linear
Fundamentos de Congruência Modular
( )
Assim todo ( ) representa uma única raiz incongruente módulo desta equação ( classe de equivalência de ).
Lema ( Teorema da fatoração ). Se ( ) é raiz de ( ) de grau , então ( ), onde é um polinômio inteiro de grau .
Demonstração. Tendo em vista que ( ) não implica necessariamente que , temos que pelo quociente de Newton, resulta em um polinômio de grau em . Seja este resultado. Assim,
Demonstração. Tendo em vista que ( ) não implica necessariamente que , temos que pelo quociente de Newton, resulta em um polinômio de grau em . Seja este resultado. Assim,
( )
Mas, por hipótese
( )
E pela propriedade da soma algébrica (prop ) :
( )
( )
A recíproca deste teorema é válida. Se partimos de ( ) e queremos mostrar que ( ), fazemos da seguinte forma:
Desde que a condição já não é mais necessária, é óbvio que ( ) ( ).
Lema . Sejam um primo e , e três polinômios inteiros, tais que ( ). Seja também uma raiz de ( ).
Então, ( ) implica em ( ) ou ( )
Demonstração: ( ) ( ), portanto .
Como é primo, temos ou . Logo, ( ) ou ( ).
Teorema de Lagrange. Seja um primo, onde ( ) e
( )
Então esta equação tem, no máximo, raízes incongruentes módulo .
Demonstração. Será por indução sobre o grau .
Se , temos ( ), por hipótese, e a equação não tem solução. Logo, o teorema é válido neste caso;
Vamos supor que o teorema seja verdadeiro para um polinômio inteiro de grau e em seguida mostraremos que isto implica a validade do teorema para o grau ;
Se ( ), de grau , for insolúvel em , o teorema ainda continua válido;
Suponha, então, que ( ), de grau , admita a raíz ( ). Pelo lema , temos que
( ),
Como , a equação de congruência linear ( ) tem raíz incongruente módulo , ou seja ( );
Pela hipótese de , tem, no máximo, raízes incongruentes ;
Pela hipótese de , tem, no máximo, raízes incongruentes ;
E sendo um primo, pelo lema qualquer outra raíz particular de ( ) ou é raíz de ( ) ou é raíz de ( ). Assim, ou ( ) (mesma raíz) ou é congruente à uma das raízes de ( );
Logo, a equação ( ) de grau tem, no máximo, raízes incongruentes módulo .
Logo, a equação ( ) de grau tem, no máximo, raízes incongruentes módulo .
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;
Excelente post. Sempre apanho muito dessa parte da teoria dos números. Vou ler o post novamente.
ResponderExcluirDá 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/
Oi, Hugocito!
ResponderExcluirJá salvei este interessante PDF.
Sobre o teorema de Newton, vi no seu blog e gostei bastante. Deixei um comentário lá.
Obrigado!
Os símbolos não estão aparecendo.
ResponderExcluir