Congruencia-aritmetica modular
Matemática

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^{13.709.286} \equiv 1^{13.709.286}\equi 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!



loading...

- Matemática Através De Problemas - V
Olá, pessoal!  Aqui vamos apresentar mais alguns problemas interessantes, e mostrar algumas soluções pros problemas propostos da ultima vez. Problemas Propostos  1 - (OMERJ-2011) Dada uma sequência de N inteiros não-negativos $a_j$ tal...

- Equações Diofantinas Exponenciais: Como O Lema De Hensel Pode Salvar Sua Vida!
Quando resolvemos problemas de teoria dos números, são muito importantes os problemas em que é dada uma equação diofantina cujas incógnitas são expoentes. Há muitas maneiras de resolver tais equações: analisar módulo algum primo conveniente,...

- Critérios De Multiplicidade De 3, 7, 9, 11, 13 E Potências De 2 E 5
Olá gente! Hoje eu enunciarei e demonstrarei os mais populares critérios de multiplicidade. Inicialmente, um fato que nos ajudará muito é o seguinte: No sistema de numeração decimal, um número representa: Assim, Critério de multiplicidade de...

- Equações Diofantinas Lineares.
Olá! O que você acha da equação abaixo? Acha que não possui solução, que possui somente 1 solução ou acha possui infinitas soluções? Hoje mostrarei como resolver equações diofantinas lineares. Que são equações da forma onde x e y são...

- Teorema Da Decomposição De Polinômios
Os primeiros registros encontrados sobre a resolução de algumas equações de segundo grau são de aproximadamente $1700a.C.$ e pertence à civilizações antigas dos sumérios, egípcios e babilônios. Os gregos aperfeiçoaram a técnica de resolução...



Matemática








.