Congruencia-aritmetica modular

 Olá gente! Hoje falarei de um dos assuntos que mais gosto.
Já ouviram falar de congruência ?
Sendo sim ou não, vamos adiante.
A ideia de congruência se baseia em criar uma aritmética com os restos.
Ao escrevermos $a\equiv b\pmod{n}$ lemos: "a é congruente a b modulo n". Queremos dizer que$a/n$ deixa resto igual a $b/n$.

Exemplo:
$7\equiv 15\pmod{8}$ porque 7 dividido por 8 da 0 e deixa resto 7 e 15 dividido por 8 da 1 e deixa resto 7
Dessa definição fica claro que $a\equiv 0\pmod{n}$ implica que $a=kn$$ k \in \mathbb{N}$.
Que $a\equiv 1 \pmod{n}$ implica que $a=kn+1$ $k \in  \mathbb{N}$.
E por ai vai...
Proposições:
1 Tem-se que $a\equiv b\pmod {m}$ se e somente se m divide $b-a$.
Demonstração:
Podemos escrever $a=mq_1+r_1$ e $b=mq_2+r_2$ onde $0\le r_1<m$ e $0\le r_2<m$ sem perda de generalidade podemos supor que $r_1\le r_2$ (se o contrario ocorrer, basta trocar os papeis de $r_1$ e $r_2$). Assim, podemos escrever $b-a = m(q_2-q_1)+r_2-r_1.$ Por isso podemos concluir que m divide $b-a$ se e somente se, m divide $r_2-r_1$. Por termos $0\le r_2-r_1<m$ m divide $b-a$ se e somente se $r_2-r_1=0$ ou seja.... se e somente se $r_2=r_1$. C.Q.D.

2- Sejam $a_1,a_2,b_1,b_2$ inteiros quaisquer e seja m um inteiro maior que 1. Se $a_1\equiv b_1$$\pmod{m}$ e $a_2\equiv b_2$ $\pmod{m}$, então $a_1\pm a_2\equiv b_1\pm b_2 \pmod m$
Demonstração:
De fato, como $a_1\equiv b_1 \pmod m$ e $a_2\equiv b_2 \pmod m$, então m divide $b_1-a_1$ e divide $b_2-a_2$ Logo, m divide $(b_1-a_1) \pm (b_2 - a_2) = (b_1\pm b_2)-(a_1\pm a_2)$, mostrando que $b_1 \pm b_2 \equiv a_1 \pm a_2$ $\pmod{m}$.  C.Q.D.
Concluindo então que congruências de mesmo modulo somam-se e subtraem-se membro a membro tal qual as igualdades.

3 - Sejam $a_1,a_2,b_1,b_2$ inteiros quaisquer e seja m um inteiro maior que 1. Se $a_1\equiv b_1$$\pmod{m}$
e $a_2\equiv b_2$ $\pmod{m}$ então $a_1.a_2\equiv b_1.b_2 \pmod {m}$.
Demonstração:
Fazendo $a_1=mq + r_1$ e $b_1=mq + r_1$; onde $m>r_1$ e $a_2=mq + r_2$ e $b_2=mq + r_2$; onde $m>r_2$. Temos: $a_1 \equiv b_1 \equiv r_1 \pmod{m}$ e $a_2 \equiv b_2 \equiv r_2 \pmod{m}$, assim, $a_1 \cdot a_2 \equiv r_1 \cdot r_2 \pmod{m}$ e $b_1 \cdot b_2 \equiv r_1 \cdot r_2 \pmod{m}$. Logo, $a_1 \cdot a_2 \equiv b_1 \cdot b_2 \pmod{m}$. C.Q.D.

Há também vários teoremas importantíssimos em teoria dos números que envolvem congruência . Alguns deles já foram tratados nessa postagem do João: Congruência e Aritmética Modular – Teoremas úteis.

Problemas:

1- Determine se o número $17^{27418572}$ é divisível por 3.
Para isso ocorrer devemos ter $17^{27418572}\pmod{3}$ note que $17\equiv 2 \pmod{3}$ logo,
$17^{27418572}\equiv 2^{27418572} \pmod{3}$ (é fácil de ver que isso é apenas um caso da propriedade 3). Observe que: $ 2^{27418572} \equiv 4^{13709286} \equiv 1^{13709286} \equiv 1 \pmod{3}$.

2- Se hoje é dia 17 de Dezembro e é Sábado, que dia será daqui a exatamente 1 ano, sabendo que ano que vem não é ano bissexto?
Se ano que vem não é ano bissexto, então de hoje (17 de Dezembro) até 17 de Dezembro do ano que vem passarão exatos 365 dias. Como a semana tem 7 dias, devemos analisar 365 módulo 7. Temos então:
$365= 52 \times 7 + 1$ logo, $365 \equiv 1\pmod{7}$ logo, daqui a 1 ano será Domingo.

A ideia de congruência também é muito utilizada em Criptografia, assunto que tratarei com mais calma em postagens futuras.

Bom pessoal, por enquanto é isso provavelmente ainda terá algumas postagens minhas sobre esse tema. Se você gostou do blog, inscreva por e-mail e no blog para receber as novas atualizações e curta nossa página no Facebook. Todas essas opções se encontram na barra lateral do blog e abaixo da postagem. Para melhorar a qualidade de nossas postagens avalie o conteúdo aqui embaixo. É rapidinho! Lembre-se que todo tipo de comentário que respeitar as regras é bem vindo.

Até mais!