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

CONGRUÊNCIAS

8.1 – INTRODUÇÃO          O estudo das congruências tem sua objetividade na resolução de equações diofantinas, bem como na verificação de algumas propriedades dos números inteiros.          Definição:- Sejam a e b dois inteiros e m um inteiro positivo. Dizemos que a e b são congruentes oucôngruos módulo m, se m | (a – b).          Indicamos a congruência de a e b módulo m por:  a º b (mod.m) São conseqüências da definição: (1)  a  é côngruo com b, se os restos da divisão de a e b por m forem iguais. (lembre-se que 0 < r < m ) (2)  a º b (mod.m) Û  existe k inteiro, tal que a – b = km. Note que a equivalência implica na validade da propriedade nos dois sentidos. Assim, se a – b = km, k inteiro, então a º b. Exemplos:   5 º 3 (mod.2)  pois 2 | 5 – 3  ou o resto da divisão de 5 e 3 por 2 é 1;                    -13 º 27 (mod.5)   pois 5 | -12 – 27 ou resto da divisão de –12 e 27 por 5 é 2. No segundo exemplo, deve-se observar que  -13 = 5.(-3) + 2. Portanto o resto é 2. 8.2 – PROPRIEDADES DAS CONGRUÊNCIAS P1) a º a (mod.m)  (reflexiva)      Temos a – a = 0 e m | 0. P2) Se a º b (mod.m) então b º a (mod.m) (simétrica)      Se a º b (mod.m) então m | a – b è a – b = km è b – a = -km è b – a = (-k)m è m | b – a è b º a. P3) Se a º b (mod.m) e b º c (mod.m) então a º c (mod. m) (transitiva)      De a º b (mod. m) tiramos  a – b = km e de b º c (mod.m) tiramos b – c = k’m. Subtraindo a segunda igualdade da primeira, resulta (a – b) – (b – c) = km – k’m è a – c = (k – k’)m è a º c (mod.m)  P4) Se a º b (mod.m) e se n | m, com n > 0, então a º b (mod.n)       a º b (mod.m) è a – b = km è a – b = k(k’n) pois n | m è a – b = (kk’)n è a º b (mod.n).  P5) Se a º b (mod.m) e se c º d (mod.m), então (I) a + c º b + d (mod.m) e (II) ac º bd (mod.m).       De a º b (mod.m) e c º d (mod.m) tiramos a – b = km è a = b + km  e  c = d + k’m. Somando as duas igualdades, tiramos: a + c = b +  d + km + k’m è a + c = b + d + (k + k’)m è a + c º b + d (mod.m). Multiplicando as duas igualdades, ac = bd + bk’m + kmd + kk’m2 è ac = bd + (bk’ + kd + kk’m)m è ac º bd (mod.m). P6) Conseqüências da propriedade anterior:       1ª) se a º b (mod.m) então a + c º b + c (mod.m)        2ª) se a + b º c (mod.m) então a º c – b (mod.m)        3ª) se a º b (mod.m) então ac º bc (mod.m)             A recíproca não é verdadeira. Isto é se ac º bc (mod.m) não se pode garantir que a º c (mod.m), exceto quando  mdc(c,m) = 1. Exemplo: 3x15 º 3x5 (mod.15) pois 45 – 14 = 30 e 15 | 30, mas 15 º 5 (mod.15).         4ª) se an º bn (mod.m) então a º b (mod.m)            A recíproca não é verdadeira como pode ser visto no exemplo: 43 º 23 (mod.8) pois 43 – 23 = 64 – 8 = 56 e 8 | 56. Mas 4 º 2 (mod.8) pois 4 – 2 = 2 e 8 não divide 2. P7) Se a º b (mod.m) então a º b – mk. EXERCÍCIOS RESOLVIDOS 1 – Indique por V ou F      a)     91 º 0 (mod. 7). A congruência é verdadeira pois 91 – 0 = 91 e 91 = 13.7  è 7 | 91.       b)     –2 º 2 (mod.8). A congruência é falsa pois –2 – 2 = -4 e 8 não divide 4. 2 – Uma das aplicações mais antigas com relação às congruências é a prova dos 9 (também chamada noves fora) onde as parcelas são convertidas em inteiros côngruos. Faz-se o mesmo com a soma.        Assim, para verificar a possibilidade da exatidão da operação   423 + 112 + 313 + 237 = 1083, fazemos:        423 º 0 (mod.9), 112 º 4 (mod.9), 313 º 7 (mod.9), 237 º 3 (mod.9) e 1083 º 3 (mod.9). Somando as parcelas, 0 + 4 + 7 + 3 º 5 (mod.9). Como a soma 1083 é côngruo com 3 mod.9, a operação está errada.       É bom observar que o processo serve para verificar se há erro, mas não prova se a operação está certa. 3 – Ache o menor inteiro positivo que representa a soma    6 + 2 – 5 + 7 + 3 (mod. 7). Temos: 6 + 2 = 8 º 1 (mod.7);   1 – 5 = -4 º -4 + 7 = 3;   3 + 3 º 6 (mod.7) 4 – Mostre que 1110 º 1 (mod.100)      Fazendo 1110 = (112)5 = 1215 º 215 = (21)2.(21)2.21 = 441 x 441 x 21 º 41 x 41 x 21 = 41 x 3 x 41 x 7 =  123 x 287 º 23 x 87 = 2001 º 1 (mod.100) Observe que separamos potencias de 11 mais próximas de 100. EXERCÍCIOS: 1. Indique por Verdadeiro ou falso a) 17 º 9 (mod.2)     b) 42 º -8 (mod.10)      c) 1213 º  112 (mod.17) 2. Ache o menor inteiro positivo e o maior inteiro negativo que represente a soma: a)     5 + 3 + 2 + 1 + 8 (mod. 6) b)     2 + 3 – 1 + 7 – 2 (mod. 4) 3. Se 1066 º 1776 (mod. m), quais são os possíveis valores de m? 4. Ache todos os inteiros x, tais que 0 < x < 15 e 3x º 6 (mod. 15) 5.- Dê todos os inteiros positivos menores que 100, côngruos a 8  mod. 13. 6 – Mostre que 41 divide 220 – 1. Sugestão prove que 220 º 1 (mod.41) 7 – Ache os restos da divisão de 250 e 4165 mod. 7. 8 – Mostre que 89 | 244 – 1    e    que 97 | 248 – 1.