A condição
é devido ao fato de que para
(
), temos que
para qualquer valor de
e não teria sentido em procurar soluções neste caso.
A condição
é necessária para garantir a existência do monômio com a variável
.
Uma raiz da equação
(
) é um inteiro
, onde,
(
).
Existência de raízes em
. Uma
nem sempre admite soluções porque
e portanto, resolvê-la consiste em solucionar a Equação Diofantina Linear
Conforme o ítem
do post 019, o critério para saber se esta equação tem solução em
é verificar se
. Se
teremos soluções em
e se
a equação é insolúvel em
.
Exemplos: Verificar se as equações
(
) e
(
) admitem soluções em
.
No primeiro caso, como
divide
, a equação tem solução em
.
No segundo caso, temos
que não divide
, logo, a equação é insolúvel em
.
Temos, então, dois casos particulares clássicos:
Exemplos: Verificar se as equações
No primeiro caso, como
No segundo caso, temos
Temos, então, dois casos particulares clássicos:
Número de soluções. Caso
Exemplo
. A equação
(
) admite uma única solução em classe de equivalência que é
(
). Assim, todos os valores que satisfazem a equação são da forma
, com
;
Exemplo
. A equação
(
) admite três soluções em classes de equivalência, que são
(
),
(
) e
(
). Logo, todas as raízes desta equação são da forma
ou
ou
, com
.
Observem pelo segundo exemplo, que as raízes que são de classes de equivalência diferentes deixam restos diferentes na divisão por
. Portanto, estas três classes de equivalência também são chamadas de soluções incongruentes
. Assim,
Solução incongruente
é cada classe de equivalência diferente que é solução de uma
(
).
Desta forma,
A equação
(
) possui apenas uma solução incongruente
(exemplo
); e
A equação
(
) tem três soluções incongruentes
(exemplo
).
Teorema: Se
e
, então a equação
(
) tem
soluções incongruentes
.
Demonstração: Já foi visto acima que a condição para que a equação
(
) tenha solução em
é que
. Para mostrar que, com esta condição verificada, a
tem
soluções incongruentes
, usaremos o que já foi provado no art
na seção Solução Geral (
) da Equação Diofantina Linear onde diz que na equação
(
)
as raízes
são dadas por
Solução incongruente
Desta forma,
A equação
A equação
Teorema: Se
Demonstração: Já foi visto acima que a condição para que a equação
onde
é uma solução particular qualquer e
. Nesta fórmula, fazendo
variar de
a
, temos
![x_{d-1}=x_0+m.\frac{d-1}{d} [;x_{d-1}=x_0+m.\frac{d-1}{d};]](http://thewe.net/tex/x_%7Bd-1%7D=x_0+m.%5Cfrac%7Bd-1%7D%7Bd%7D)
Para
, com
, vamos ter
(
), ou seja, cada
( ou
) representa uma classe de equivalência
diferente.
A primeira vista, isto não é nada óbvio. Mas, fazendo
, vejam que
(
)
Qualquer solução resultante de
pode ser enquadrada em uma das
classes de equivalência
, com
.
(
)
Vejamos. Até agora, analisamos
no intervalo
. Seja então,
, com
e
. Logo,
e como
, temos que
é uma solução que pertence à uma das classes de equivalência estudadas:
, com
.
Cálculo das raízes. A forma geral de resolver uma equação de congruência linear
( ![mod [;mod;]](http://thewe.net/tex/mod)
) consiste nas seguintes etapas:
Verificar se a equação é solúvel em
. Basta verificar se
e em caso positivo, a equação tem
soluções incongruentes
( ou seja, existem
classes de equivalência de raízes );
Sendo solúvel,converter a equação de congruência na forma diofantina equivalente
,
Para calcular as
classes de equivalência das raízes (
soluções incongruentes
) basta usar a fórmula geral
, com
(
)
(
)
(
)
(
)
e
. Logo, a equação tem
soluções incongruentes
;
(
)
Logo, as três soluções de
(
) são:
(
)
(
)
(
)
(
)
(
)
(
)
Obs: Vejam que
(
) ( soluções incongruentes
)
A Combinaçao Linear
O Algoritmo de Euclides e a Representação Binomial do m.d.c
Equação Diofantina Linear
Fundamentos de Congruência Modular
Cálculo das raízes. A forma geral de resolver uma equação de congruência linear
e achar uma solução inicial
pelo algoritmo de Euclides ou um dos atalhos mostrados no post Equação Diofantina Linear;
Portanto,
Exemplo: Resolver a equação
(
).
Resolução:
Pelo algoritmo de Euclides, temos que
e multiplicando ambos os membros por
temos
. Assim, uma solução inicial da equação de congruência é
;
Obs: Vejam que
Tópicos Relacionados
A Combinaçao Linear
O Algoritmo de Euclides e a Representação Binomial do m.d.c
Equação Diofantina 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.
Funções Aritméticas - Números Notáveis, de Edgard de Alencar Filho, Editora Nobel,1988.
Seu blog tem sido de INESTIMÁVEL ajuda para que eu possa prosseguir no meu mestrado profissional. Os livros usados no meu mestrado não mostram as explicações de forma CLARA, DETALHADA, EXEMPLIFICADA como você faz. Precisariam APRENDER a como ENSINAR com você... Novamente MUITO OBRIGADA!!! Abs. Marina
ResponderExcluirOi, Marina!
ExcluirFico bastante feliz de estar contribuindo com seus estudos. Além disso, estou aprimorando meu próprio aprendizado pois nunca aprendi tanto fazendo este blog.
Obrigado pela visita!
Já falei para o Aloísio que ele tem um grande talento em matemática e que poderia ser até doutor nesta área do conhecimento.
ExcluirParabéns, consegui resolver uma lista de uma matéria que tenho na faculdade que tem congruência linear, a disciplina é matemática para criptografia. obrigado! ótimo blog.
ResponderExcluir