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;]

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;]

). 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

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

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

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!

- 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