[Ref: ver post 048] Equação de Congruência Linear () na variável ( ), é toda equivalência da forma
( ), onde
, com e
e , com
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
( ) , com ,
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 ( ) 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:
) A equação ( ) admitirá soluções apenas se , porque só desta forma teremos ;
) Se , a equação ( ) sempre terá soluções, porque não importa o valor de , pois sempre .
Número de soluções. Caso , a equação ( ) admitirá infinitas soluções inteiras. Mas estas soluções são agrupadas em classes de equivalência e estas são em número finito:
Número de soluções. Caso , a equação ( ) admitirá infinitas soluções inteiras. Mas estas soluções são agrupadas em classes de equivalência e estas são em número finito:
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
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
onde é uma solução particular qualquer e . Nesta fórmula, fazendo variar de a , temos
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 ( ) 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 );
Cálculo das raízes. A forma geral de resolver uma equação de congruência linear ( ) 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
,
e achar uma solução inicial pelo algoritmo de Euclides ou um dos atalhos mostrados no post Equação Diofantina Linear;
Para calcular as classes de equivalência das raízes ( soluções incongruentes ) basta usar a fórmula geral
, com
Portanto,
( )
( )
( )
( )
Exemplo: Resolver a equação ( ).
Resolução:
e . Logo, a equação tem soluções incongruentes ;
( )
Pelo algoritmo de Euclides, temos que e multiplicando ambos os membros por temos . Assim, uma solução inicial da equação de congruência é ;
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
Obs: Vejam que ( ) ( soluções incongruentes )
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