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
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
(
)
(
)
(
)
(
) ![\Rightarrow [;\Rightarrow;]](http://thewe.net/tex/%5CRightarrow)
(
)
(
)
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
;
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
.
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
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
.
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