quinta-feira, 27 de janeiro de 2011

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!

14 comentários:

  1. Debbie Kindly send my earring by priority mail.

    Have a look at my homepage: cuisibase.fr

    ResponderExcluir
  2. Hello! Someone in my Myspace group shared this site with
    us so I came to check it out. I'm definitely enjoying the information. I'm book-marking and
    will be tweeting this to my followers! Outstanding blog
    and fantastic design and style.

    Also visit my website xerox 8560 phaser

    ResponderExcluir
  3. I have made my mailing list of addresses for Christmas much
    like the video clip shows using MS word 2010 with no issues.
    I can print one tag every web page or I can print the same label on the web page 30 times.
    I want to publish my list of different address on the web page
    so I have 30 different tags to mail. I can not obtain that done in the tag area.
    If I publish with the regular going to file, then print, I obtain the file to print out
    however not formatted for the kind of labels I am making use of.
    I just don't see exactly how I can do the different address tags to publish in the label tab.
    Thanks,.

    Here is my blog post; xerox phaser 8560 maintenance kit

    ResponderExcluir
  4. I enjoy the Bird on the Scroll earrings, plus the Scroll and Heart earrings:
    -)

    my website :: silver jewellery for women

    ResponderExcluir
  5. I handle the exact same trouble with Samsung ML-1510I loosened numerous
    hours fighting until I locate your remedy.

    Here is my weblog; xerox phaser 8560 printer

    ResponderExcluir
  6. How do you spell the name of the chemical?


    My web site ... xerox phaser 8560 printer (http://www.redmascota.com.mx/)

    ResponderExcluir
  7. What's Happening i'm nеω to this, Ι stumblеd upon thiѕ I've discovered It absolutely helpful and it has helped me out loads. I hope to contribute & assist different users like its helped me. Good job.

    Check out my web-site ... facebook australia (http://onlinebookkeepers.co.nz/)

    ResponderExcluir
  8. May I simply just say what a relief to discover an individual who genuinely knows
    what they are discussing online. You actually know how to bring an issue to light and make it important.

    More people have to look at this and understand this side of the story.

    It's surprising you aren't more popular since you certainly have
    the gift.

    Take a look at my web-site :: xerox 8560 ram error

    ResponderExcluir
  9. Sometimes the simplest means to taken out embedded command series is to duplicate and insert
    the afflicted section to notepad, clean the content you desire kept, then copy and
    insert it back.

    Here is my website; xerox phaser 8560 printer ()

    ResponderExcluir
  10. you're really a good webmaster. The site loading speed is incredible. It sort of feels that you're doing any unique trick.

    Moreover, The contents are masterpiece. you've done a excellent job in this topic!

    my blog post; pilgrim jewellery wholesale :: www.blogymate.com ::

    ResponderExcluir
  11. I like the helpful information you provide in your articles.
    I will bookmark your blog and take a look at once more here
    frequently. I'm rather certain I'll learn many new stuff right here!
    Good luck for the next!

    Here is my web blog: Private Cloud Hosting

    ResponderExcluir
  12. Have you ever thought about creating an ebook or guest authoring on other websites?
    I have a blog based on the same ideas you discuss and would love to have
    you share some stories/information. I know my audience would enjoy your work.
    If you are even remotely interested, feel free to shoot
    me an email.

    Feel free to surf to my web page; Buy LG 42LS5600

    ResponderExcluir
  13. Clive Parkin said on August 14, 2012

    Here is my site - danon jewellery fashion jewelry

    ResponderExcluir

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...