terça-feira, 19 de junho de 2012

049-Equação de Congruência Linear


[Ref: ver post 048] Equação de Congruência Linear ([;ECL;]) na variável [;x \in \mathbb{Z};] ( [;U=\mathbb{Z};] ), é toda equivalência da forma

[;ax \equiv b;] ([;mod;] [;m;]), onde 

[;m \in \mathbb{N};], com [;m>1;] e

[;a;] e [;b;] [;\in \mathbb{Z;], com [;a\neq 0;] 

A condição [;m>1;] é devido ao fato de que para [;ax \equiv b;] ([;mod;] [;1;]), temos que [;1|(ax-b);] para qualquer valor de [;x \in \mathbb{Z};] e não teria sentido em procurar soluções neste caso.

A condição [;a\neq 0;] é necessária para garantir a existência do monômio com a variável [; x;].

Uma raiz da equação [;ax \equiv b;] ([;mod;] [;m;]) é um inteiro [;x_o \in \mathbb{Z};] , onde, [;ax_0 \equiv b;] ([;mod;] [;m;]).

Existência de raízes em [; \mathbb{Z};]. Uma [;ECL;] nem sempre admite soluções porque

[;ax \equiv b;] ([;mod;] [;m;]) [;\Rightarrow m|(ax-b) \Rightarrow ax-b=my;] , com [;y \in \mathbb{Z};],

e portanto, resolvê-la consiste em solucionar a Equação Diofantina Linear

[;ax-my=b;]

Conforme o ítem [;a);] do post 019, o critério para saber se esta equação tem solução em [;Z;] é verificar se [;(a,m)|b;]. Se [;(a,m)|b;] teremos soluções em [; \mathbb{Z};] e se [;(a,m) \not \mid b;] a equação é insolúvel em [;Z;].

Exemplos: Verificar se as equações [;8x \equiv 36;] ([;mod;] [;12;] ) e [;10x \equiv 32;] ([;mod;] [;15;]) admitem soluções em [;Z;].

No primeiro caso, como [;(a,m)=(8,12)=4;] divide [;b=36;], a equação tem solução em [;\mathbb{Z};].

No segundo caso, temos [;(a,m)=(10,15)=5;] que não divide [;b=32;], logo, a equação é insolúvel em [; \mathbb{Z};].

Temos, então, dois casos particulares clássicos:

[;a;] ) A equação [;ax \equiv \pm 1;] ([;mod;] [;m;]) admitirá soluções apenas se [;(a,m)=1;], porque só desta forma teremos [;(a,m)| \pm 1;];

[;b;] ) Se [;(a,m)=1;] , a equação [;ax \equiv b;] ([;mod;] [;m;]) sempre terá soluções, porque não importa o valor de [;b;], pois sempre [;(a,m)|b;].

Número de soluções. Caso [;(a,m)|b;], a equação [;ax \equiv b;] ([;mod;] [;m;])  admitirá infinitas soluções inteiras. Mas estas soluções são agrupadas em classes de equivalência [;mod;] [;m;] e estas são em número finito:

Exemplo [;1;]. A equação [;46x \equiv 18;] ([;mod;] [;5;] ) admite uma única solução em classe de equivalência que é  [;x \equi 3;] ([;mod;] [;5;] ).  Assim, todos os valores que satisfazem a equação são da forma [;x=3+5k;], com [;k \in \mathbb{Z};];

Exemplo [;2;]. A equação [;12x \equiv 3;] ([;mod;] [;9;] ) admite três soluções em classes de equivalência, que são [;x \equiv 1;] ([;mod;] [;9;] ), [;x \equiv 4;] ([;mod;] [;9;] ) e [;x \equiv 7;] ([;mod;] [;9;] ). Logo, todas as raízes desta equação são da forma [;x=1+9k;] ou [;x=4+9k^';]ou [;x=7+9k^{''};], com [;k,k^',k^{''} \in \mathbb{Z};].

[;\rightarrow;] Observem pelo segundo exemplo, que as raízes que são de classes de equivalência diferentes deixam restos diferentes na divisão por [;9;]. Portanto, estas três classes de equivalência também são chamadas de soluções incongruentes [;mod;] [;9;]. Assim,

Solução incongruente [;mod;] [;m;] é cada classe de equivalência diferente que é solução de uma [;ECL;] ([;mod;] [;m;]).

Desta forma,

A equação [;46x \equiv 18;] ([;mod;] [;5;] ) possui apenas uma solução incongruente [;mod;] [;5;] (exemplo [;1;]); e

A equação [;12x \equiv 3;] ([;mod;] [;9;] ) tem três soluções incongruentes [;mod;] [;9;] (exemplo [;2;]).

Teorema: Se [;d=(a,m);] e [;d|b;], então  a equação [;ax \equiv b;] ([;mod;] [;m;]) tem [;d;] soluções incongruentes [;mod;] [;m;].

Demonstração: Já foi visto acima que a condição para que a equação [;ax \equiv b;] ([;mod;] [;m;]) tenha solução em [;\mathbb{Z};] é que [;d|b;]. Para mostrar que, com esta condição verificada, a [;ECL;] tem [;d;] soluções incongruentes [;mod;] [;m;], usaremos o que já foi provado no art [;019;] na seção Solução Geral ( [;U=\mathbb{Z};] ) da Equação Diofantina Linear onde diz que na equação [;ax \equiv b;] ([;mod;] [;m;]) [;\Rightarrow ax-my=b;] as  raízes [; x;] são dadas por

 [;x=x_0+\frac{m}{(a,m)}.k;]

onde [;x_0;] é uma solução particular qualquer e [;k \in \mathbb{Z};]. Nesta fórmula, fazendo [;k;] variar de [;0;] a [;d-1;], temos

   [;x_0=x_0+m.\frac{0}{d};]

   [;x_1=x_0+m.\frac{1}{d};]

   [;x_2=x_0+m.\frac{2}{d};]
[;........................;]  

  [;x_i=x_0+m.\frac{i}{d};] 

[;........................;]

    [;x_{j}=x_0+m.\frac{j}{d};]   

[;........................;]

    [;x_{d-1}=x_0+m.\frac{d-1}{d};]


[;I);] Para [;i\neq j;], com [;0 \leq i,j \leq d-1;], vamos ter [;x_i \not \equiv x_j;] ([;mod;] [;m;]), ou seja, cada [;x_i;] ( ou [;x_j;]) representa uma classe de equivalência [;mod;] [;m;] diferente.
A primeira vista, isto não é nada óbvio. Mas, fazendo [;x_j-x_i=m\frac{(j-i)}{d};], vejam que 

[;0 \leq i,j \leq d-1 \Rightarrow;] 

[;j-i<d \Rightarrow;]  

[;0<\frac{j-i}{d}<1 \Rightarrow;] 

[;x_j-x_i<m \Rightarrow;]

[;x_i \not \equiv x_j;] ([;mod;] [;m;])


[;II);] Qualquer solução resultante de [;x=x_0+\frac{m}{(a,m)}.k;]pode ser enquadrada em uma das [;d;] classes de equivalência [;x_i=x_0+m.\frac{i}{d};], com [;i \in \left{0,1,2,...,d-1 \right};].

Vejamos. Até agora, analisamos [;k;] no intervalo [;0 \leq k \leq d-1;]. Seja então, [;k=qd+r;], com [;q,r \in \mathbb{Z;] e [;0 \leq r \leq d-1;]. Logo,

[;x=x_0+m.\frac{k}{d} \Rightarrow;]

[;x=x_0+m.\frac{(qd+r)}{d} \Rightarrow;]  

[;x=x_0+mq+m\frac{r}{d} \Rightarrow;] 

[;x \equiv x_0+m\frac{r}{d};] ([;mod;] [;m;])


e como [;0 \leq r \leq d-1;], temos que [; x;] é uma solução que pertence à uma das classes de equivalência estudadas: [;x_i=x_0+m.\frac{i}{d};], com [;0 \leq i \leq d-1;].

Cálculo das raízes. A forma geral de resolver uma equação de congruência linear [;ax \equiv b;] ( [;mod;][;m;] ) consiste nas seguintes etapas:

[;1);] Verificar se a equação é solúvel em [;\mathbb{Z};]. Basta verificar se [;(a,m)|b;] e em caso positivo, a equação tem [;d=(a,m);] soluções incongruentes [;mod;] [;m;] ( ou seja, existem [;d;] classes de equivalência de raízes );


[;2);] Sendo solúvel,converter a equação de congruência na forma diofantina equivalente

[;ax-by=b;],

 e achar uma solução inicial [;x_0;] pelo algoritmo de Euclides ou um dos atalhos mostrados no post Equação Diofantina Linear;

[;3);] Para calcular as [;d;] classes de equivalência das raízes ( [;d;] soluções incongruentes [;mod;] [;m;] ) basta usar a fórmula geral

[;x \equiv x_0+\frac{m}{d}.k;], com [;k=0,1,2,...,d-1;]

Portanto,

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

[;x_1 \equiv x_0+\frac{m}{d};] ([;mod;] [;m;]

[;x_2 \equiv x_0+2.\frac{m}{d};] ([;mod;] [;m;] )
[;...............................................;] 

[;x_{d-1} \equiv x_0+(d-1).\frac{m}{d};] ([;mod;] [;m;] )


Exemplo: Resolver a equação [;51x \equiv 18;] ([;mod;] [;15;] ).

Resolução:

[;1);] [;(51,15)=3;] e [;3|18;]. Logo,  a equação tem [;3;] soluções incongruentes [;mod;] [;15;];

[;2);] [;51x \equiv 18;] ([;mod;] [;15;] ) [;\Rightarrow;] [;51x-15y=18;] [;\Rightarrow;] [;17x-5y=6;] 

Pelo algoritmo de Euclides, temos que  [;17.(-2)-5.(-7)=(17,5)=1;] e multiplicando ambos os membros por [;6;] temos [;17(-12)-5(-42)=6;]. Assim, uma solução inicial da equação de congruência é [;x_0=-12;];

[;3);] Logo, as três soluções de [;51x \equiv 18;] ([;mod;] [;15;] ) são:

[;x_0 \equiv -12;] ([;mod;] [;15;] ) [;\Rightarrow x_0 \equiv 3;] ([;mod;] [;15;] )

[;x_1 \equiv 3+1.\frac{15}{3};] ([;mod;] [;15;] ) [;\Rightarrow x_1 \equiv 8;] ([;mod;] [;15;] )

[;x_2 \equiv 3 + 2.\frac{15}{3};] ([;mod;] [;15;] ) [;\Rightarrow x_2 \equiv 13;] ([;mod;] [;15;] )

Obs: Vejam que  [;3 \not \equi 8 \not \equi 13;] ([;mod;] [;15;] ) ( soluções incongruentes [;mod;] [;15;] )




Tópicos Relacionados

A Combinaçao Linear [;ax+by;]  
O Algoritmo de Euclides e a Representação Binomial do m.d.c [;(a,b);] 
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.  

4 comentários:

  1. 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

    ResponderExcluir
    Respostas
    1. Oi, Marina!

      Fico 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!

      Excluir
    2. 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.

      Excluir
  2. Parabé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