Congruência módulo n

Seguem algumas observações sobre congruência módulo n que pesquisei na internet.
Importa observar que existem funções em C e JavaScript tipo x = y%2 que retorna x com valor 0 se y for par ou x com valor 1 se y for ímpar. Extendendo a observação x = y%3 só pode retornar valores de x sendo 0, 1 ou 2.
Boa leitura.

ARITMÉTICA MODULAR

A congruência módulo n é a aritmética modular em que se opera com partes dos números, é outra forma de olhar a divisão. Nornalmente quando executa-se uma divisão procura-se o valor do quociente que é o resultado entre o dividendo e o divisor, mas a divisão proporciona outra forma de ser observada: se prestarmos atenção no resto e no divisor verifica-se que à medida que varia o dividendo o resto forma um ciclo:
Divisão por 2:
10/2=5 resto 0; 11/2=5 resto 1; 12/2=6 resto 0; 13/2=6 resto 1 --> variando o dividendo e mantendo o divisor como 2 o resto somente assume os valores de 0 ou 1.
Divisão por 3:
10/3=3 resto 1; 11/3=3 resto 2; 12/3=4 resto 0; 13/3=4 resto 1; 14/3=4 resto 2; 15/3=5 resto 0 --> variando o dividendo e mantendo o divisor como 3 o resto somente assume os valores de 0, 1 ou 2.
Por estes exemplos fica fácil observar que o resto assume valores entre 0 e (divisor -1), assim:
divisor 2 --> os restos podem assumir os valores 0 ou 1.
divisor 3 --> os restos podem assumir os valores 0, 1 ou 2.
divisor 4 --> os restos podem assumir os valores 0, 1, 2 ou 3.
divisor 10 --> os restos podem assumir os valores 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9.
E por aí vai...

Observando desta forma e tomando os exemplos das divisões acima temos em notação matemática que:
10/2=5 resto 0 --> 10 ≡ 0 (mod 2) --> 10 é congruente a 0 em módulo 2, ou em outras palavras, 10 deixa resto 0 quando dividido por 2.
10/3=3 resto 1 --> 10 ≡ 1 (mod 3) --> 10 é congruente a 1 em módulo 3, ou em outras palavras, 10 deixa resto 1 quando dividido por 3.
100/10=10 resto 0 --> 100 ≡ 0 (mod 10) --> 100 é congruente a 0 em módulo 10, ou em outras palavras, 100 deixa resto 0 quando dividido por 10.
E por aí vai...

Mas qual a importância prática disso?
Principalmente por formar grupos distintos (em linguagem de conjuntos: a aritmética modular forma subconjuntos disjuntos que são aqueles em que os subconjuntos formados não tem elementos em comum).

Na verdade a aritmética modular sempre esteve presente no cotidiano, por exemplo:
- As horas do relógio (analógico) é formado em módulo 12, por exemplo: 14 horas e 2 horas da tarde são a mesma coisa? sim (os ponteiros das horas estarão localizados exatamente no mesmo lugar). Em aritmética modular diz-se que 14 ≡ 2 (mod 12) ou 2 ≡ 14 (mod 12).
- Os minutos das horas seguem o módulo 60, assim, se o ponteiro dos minutos percorrer 120 minutos ou 60 minutos estará localizado no mesmo lugar, dessa forma 120 ≡ 60 (mod 60) ou 60 ≡ 120 (mod 60).
- Os anos bissextos seguem módulo 4, desa forma o calendário do ano 2000 pode ser usado em 2004, 2008, 2012, 2016 em diante. Em linguagem da aritmética modular, 2000 ≡ 2004 (mod 4); 2004 ≡ 2008 (mod 4); 2000 ≡ 2012 (mod 4); 2012 ≡ 2008 (mod 4); ...

Existem problemas que podem ser resolvidos com mais facilidade pela aritmética modular?
Um exemplo: 255000 é divisível por 3?
Se é divisível deixa resto zero.
255000 = 255 x 1000
255 é divisível por 3 (fazendo na mão) dá quociente 85 e resto zero, assim, 255 ≡ 0 (mod 3).
pela propriedade das congruências, pode-se multiplicar ambos os termos por um número que a congruência se mantém, assim, 255 x 1000 ≡ 0 x 1000 (mod 3), dessa forma 255000 ≡ 0 (mod 3), então 255000 é divisível por 3.

O método criptográfico RSA, de chave pública e privada, o mais usado no mundo, é baseado na congruência.

No primeiro exemplo das horas do relógio onde 14 ≡ 2 (mod 12) ou 2 ≡ 14 (mod 12) o segundo caso pode parecer estranho porque apresenta resto 14 sendo o módulo 12, na verdade se no processo da divisão depara-se com 14 e divisor 12 o quociente seria 1 com resto 2, assim basta passar 12 para o outro lado dessa forma 2 + 12 ≡ 14 - 12 (mod 12) --> 14 ≡ 2 (mod 12) voltando para o primeiro caso.
Então pode-se olhar para a congruência de duas formas:
1) 14 ≡ 2 (mod 12) --> com o 2 sendo o resto da divisão entre 14 e 12; ou
2) 14 ≡ 2 (mod 12) --> com o 2 pertencendo à mesma classe do 14, ou seja, ambos apresentam o mesmo resto 2 quando divididos por 12. Explico:

Acima foi dito que a aritmética modular forma subconjuntos disjuntos e que um divisor forma ciclos de restos. Dessa forma:
- O divisor 2, ou, o módulo 2 forma dois ciclos, ou, duas classes: o ciclo (classe) 0 e o ciclo (classe) 1. Pertencem à classe 0 os números que deixam resto 0 quando divididos por 2 {0, 2, 4, 6, 8, ...} e pertencem à classe 1 os números que deixam resto 0 quando divididos por 2 {1, 3, 5, 7, 9, ...}. Assim, pode-se dizer:
4 ≡ 2 (mod 2); 28 ≡ 34 (mod 2); 1012 ≡ 3968 (mod 2) e assim por diante porque todos pertencem à mesma classe 0.
5 ≡ 1 (mod 2); 1 ≡ 15 (mod 2); 155 ≡ 1799 (mod 2) e assim por diante porque todos pertencem à mesma classe 1.

Da mesma forma tanto faz afirmar que 14 horas e 2 horas da tarde no módulo 12 são congruentes, ou, 2 horas da tarde e 14 horas no módulo 12 são igualmente congruentes.

Percebe a relação de igualdade da afirmação acima? Não é à toa, a congruência tem muita proximidade com a relação de igualdade (mas não são a mesma coisa). Veja:
- A congruência é reflexiva porque a ≡ a (mod n), ou seja, qualquer número é congruente consigo mesmo em qualquer módulo.
- A congruência é simétrica porque a ≡ -a (mod n), ou seja, qualquer número é congruente com seu oposto em qualquer módulo.
- A congruência é transitiva porque sendo a ≡ b (mod n) e b ≡ c (mod n) implica que a ≡ c (mod n), ou seja, qualquer número é congruente com outro número dentro da sua classe (se a é congruente com b que por sua vez é congruente com c, todos em um mesmo módulo, significa que a, b e c pertencem à mesma classe portanto os três são congruentes entre si).
Se a relação de congruência é simétrica, reflexiva e transitiva, logo ela apresenta relação de equivalência, dessa forma 5 ≡ 1 (mod 2); 1 ≡ 15 (mod 2) , os últimos exemplos acima, 1, 5 e 15 no módulo 2 são equivalentes (são simétricos, reflexivos e transitivos).

Particularmente interessante observar congruência e relação de equivalência na geometria em quaisquer triângulos que tenham os lados múltiplos, são congruentes e equivalentes, mas não são iguais mesmo porque podem pertencer a planos diferentes.

Fica fácil perceber diversas propriedades das congruências:
- a ≡ a (mod n) pois a - a = 0 e zero dividido por qualquer número é zero.
- a ≡ b (mod n) então a + x ≡ b + x (mod n), ao somar o mesmo número aos dois números da congruência está mudando a classe desses números, mas permanecerão congruentes.
- a ≡ b (mod n) então a . x ≡ b . x (mod n), quase a mesma explicação acima sendo que não há mudança de classe.
- a ≡ b (mod n) então ax ≡ bx (mod n).


Referências:
http://amatematicapura.blogspot.com/2011/01/congruencia-aritmetica-modular.html
http://www.somatematica.com.br/coluna/gisele/11052005.php
http://www.atractor.pt/mat/alg_controlo/arit_modular/mod_texto.htm