[obm-l] Re: [obm-l] RES: [obm-l] Congruência, módulo m

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Dois inteiros a e b sao ditos congruentes modulo m quando ambois deixam o mesmo resto quando divididos por m.
Isso eh a mesma coisa (verifique!) que dizer que a-b eh divisivel por m.
A notacao usual nesta lista eh a == b (mod m).

A utilidade do conceito de congruencia vem dos seguintes fatos (faceis de provar - tente)
1) a == a (mod m)
2) se a == b (mod m) entao b == a (mod m)
3) se a == b (mod m) e b == c (mod m) entao a == c (mod m)
(essas tres condicoes implicam que congruencia modulo m eh uma relacao de equivalencia. Assim, para cada m >= 1, o conjunto 
dos inteiros fica particionado em m subconjuntos mutuamente disjuntos - as classes de congruencia mod m - tais que quaisquer 
dois elementos de uma mesma classe sao congruentes mod m - por exemplo, congruencia mod 2 particiona os inteiros em pares 
e impares)

se a == b (mod m) e c == d (mod m) entao:
4) a + c == b + d (mod m)
5) a - c == b - d (mod m)
6) ac == bd (mod m)
(em geral, se p(x) eh um polinomio com coeficientes inteiros e a == b (mod m), entao p(a) == p(b) (mod m))

7) se a == b (mod m) e k eh um inteiro qualquer, entao ka == kb (mod m)

8) se a == b (mod m) e q divide a, b e m, entao a/q == b/q (mod m/q)
9) se a == b (mod m), q divide a e b, q eh primo com m, entao a/q == b/q (mod m).

Por exemplo, usando congruencia mod 10 podemos descobrir o ultimo algarismo (algarismo mais a direita) de um numero bem 
grande.
Por exemplo, qual o ultimo algarismo de 2^100?
Trabalhando mod 10, teremos:
2^1 == 2; 2^2 == 4; 2^3 == 8; 2^4 == 6; 2^5 == 2; 2^6 == 4.
Repare que quando chegamos a 2^5, descobrimos que 2^5 == 2^1 (mod m).
Usando (6) acima n-1 vezes, com a = c = 2^5  e  b = d = 2^1, obteremos:
(2^5)^n == (2^1)^n (mod 10), para todo n natural.
Em particular, para n = 20, teremos 2^100 = (2^5)^20 == (2^1)^20 = 2^20 (mod 10).
Para n = 4, teremos (2^20) = (2^5)^4 == (2^1)^4 = 2^4 = 16 == 6 (mod 10).
Logo, 2^100 == 2^20 == 6 (mod 10), ou seja, o ultimo algarismo de 2^100 eh 6.

Espero ter ajudado.

[]s,
Claudio.
 
---------- Cabeçalho original -----------

De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia: 
Data: Sun, 25 Mar 2007 03:07:14 -0300
Assunto: Re: [obm-l] RES: [obm-l] Congruência, módulo m

> Eu ainda não conseguir entender. Nunca fiquei tão perdida assim em
> matemática. Não entra na minha cabeça isso de congruência. Eu leio, leio e
> leio sobre o assunto e parece que sei menos a cada leitura.
> descupas pela minha ignorãncia, juro que estou me esforçando para aprender.
> Bjos a todos.
> 
> 


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================