TEORIA DOS NÚMEROS - CONGRUÊNCIAS (3)

CONGRUÊNCIAS

8.4 – CONGRUÊNCIAS LINEARES          Definição:- Chamamos de congruência linear a toda equação da forma r +  ax º s (mod. m).           Equações desse tipo pode ser reduzida à forma ax º b (mod.m) bastando para isto fazer ax º s – r (mod.m), condição esta prevista nas propriedades das congruências. Na solução de equações desse tipo, é permitido substituir “a”  por a – km e “b” por b – km de acordo com as propriedades das congruências. Entretanto, a e b não podem ser divididos por um divisor comum dos dois, pois isto não é válido para as congruências.          Tomando por exemplo a equação   314 + 172x  1312 (mod.5) podemos fazer: 314 =  62.5 + 4 è 314 º 4 (mod.5)      172 = 34.5 + 2 è 172 º 2 (mod.5)     1312 = 262.5 + 2 è 1312 º 2 (mod.5)          Efetuando estas substituições na equação dada temos:  4 + 2x º 2 (mod.5) è 2x º 2 – 4 (mod.5) è 2x º -2 (mod.5) è 2x º -2 + 5 (mod. 5) è 2x º 3 (mod.5). Aqui, devemos procurar um inteiro que multiplicado por 2 seja congruente a 3 (mod.3). Isto é, um inteiro x, tal que 2x – 3 seja múltiplo de 5. Por tentativa, obtém-se x = 4 pois 2.4 – 3 = 5 (= 5.1) 8.5 – PROCESSOS DE RESOLUÇÃO DE CONGRUÊNCIAS LINEARES          Para facilidade de resolução de congruência lineares define-se o inverso de um inteiro x, ao inteiro x*, tal que x*.x º 1 mod.m.         Na aplicação do inverso teremos,   a.x º b (mod.m) è a*.a.x º a*.b (mod.m) è 1.x  º a*.b (mod.m) è x º a*.b (mod.m)        Tomando por exemplo, o módulo 5 teremos  2* = 3 pois  2.3 º 1 (mod.5). Isto é, o inverso de 2 é o 3. Da mesma forma  4* = 4 pois 4.4 = 16 º 1 (mod.5) 1º processo - Tabelas operacionais          Consideremos, por exemplo, congruências módulo 7. Para a multiplicação teremos

Para resolver a equação   67x º  159 (mod.7) teremos:   67 º 2 (mod.7) e 159 º 5 (mod.7). Portanto, 67x º 159 (mod.7) equivale à 2.x º 5 (mod.7). Observando a tabela, e de x º 2*.5 (mod.7) teremos x º 4.5 = 20 º 6 (mod. 7). Portanto, a solução da equação acima é x º 6 (mod.7) 2º processo -  Transformando em equação diofantina          A equação ax º b (mod.m), conforme definição equivale a ax – my = b. Resolvendo esta equação conforme já foi estudado, obtém-se o valor de x.         A transformação de uma equação diofantina em congruência linear, muitas vezes facilita a solução da mesma.        Tomando por exemplo a equação  11x + 27y = 4, podemos transformar a mesma em 27y º 4 (mod.11). Observe que devemos escolher o menor entre 11 e 27 para ser o módulo. Como 27 º 5 (mod.11), temos 5y º 4 (mod.11).Devemos procurar um inteiro de dividido por 11 deixe resto 4 e que seja múltiplo de 5. Por tentativa, encontramos esse inteiro igual a 15 pois 15 = 1.11 + 4. Assim, y = 3. Substituindo esse valor na equação 11x + 27y = 4, obtemos 11x + 27.3 = 4 è 11x = 4 – 81 è 11x = - 77 e x = -7. 8.6 – CONDIÇÃO DE EXISTÊNCIA E NÚMERO DE SOLUÇÕES          A equação  ax º b (mod.m) é equivalente a ax – my = b. Conforme já estudado, esta equação só terá solução quando b é um múltiplo do mdc(a, m).          Aplicando este fato às congruências lineares, pode-se concluir que ax º b (mod.m) terá solução se e somente se mdc(a,m) | b.          Em itens anteriores, vimos que se (xo, yo) é solução da equação ax + by = c então x = xo + t.b/(mdc(a,b)  e y = yo – t.a/mdc(a,b) também são soluções dessa equação.          Como conseqüência, a equação ax º b (mod.m) também terá infinitas soluções. Entretanto,  o número de soluções incongruentes será igual a d, onde d é o mdc de a e m. EXERCÍCIOS 1 – Resolva as congruências lineares a) 2x º 1 (mod.17)   b) 3x º 1 (mod.17)   c) 3x º 6 (mod.18)  d) 25x º 15 (mod.29) e) 5x º 2 (mod.26)   f) 14x º 36 (mod.48) 2 – Resolva as equações diofantinas a) 4x + 51y = 9     b) 12x + 25y = 331     c) 5x – 53y = 17     d) 7x + 6y = 9      e) 65x + 77y = 200      f) 51x + 85y = 1037          g) 75x – 131y = 6. 3 – Dê o número de soluções incongruentes das equações a) 3x º 6 (mod.15)   b) 4x º 8 (mod.15)  c) 5x º 10 (mod.15)  d) 6x º 11 (mod.15)