Pular para o conteúdo principal

Congruência módulo m

A congruência módulo m é uma operação muito importante na aritmética. As noções de congruência foram introduzidas por Gaussem seu livro Disquisitiones Arithmeticae em 1801 e ainda hoje são utilizadas em várias áreas, como o desenvolvimento de algorítmos de criptografia, como o RSA, para demonstrar e justificar matematicamente os critérios de divisibilidade, para encontrar restos, entre outras aplicações.



Dizemos que dois números, a e b, são congruentes módulo m e anotamos a congruente a b módulo m se e somente se a e b deixam o mesmo resto na divisão euclidiana por m.


Por exemplo: 13 é congruente a 19 módulo 6 (lemos 13 é congruente a 19 módulo 6) pois 13 dividido por 6 deixa resto 1 e 19 dividido por 6 também deixa resto 1. Por outro lado, 2 não é congruente a 4 módulo 3 (lemos 2 não é congruente a 4 módulo 3) pois 2 dividido por 3 deixa resto 2 e 4 dividido por 3 deixa resto 1.


Existe outra forma correta de se definir congruência: dizemos que a congruente a b módulo m se e somente se m | (a - b).


Dem: Se a congruente a b módulo m então existem inteiros r, q e q' tais que a = m . q + r e b = m . q' + r. Assim, a - b = m(q - q') e, portanto, m | (a - b).


Reciprocamente, suponha que m | (a - b). Logo, a = m . q + r e b = m . q' + r', com r e r' menores ou iguais a 0 e menores do que m. Desta forma, a - b = m(q - q') + r - r'. Assim, m | m(q - q') e m | (r - r'), mas isso só é possível se r = r', pois | r - r' | < m, então a congruente a b módulo m.


A congruência módulo m apresenta as seuintes propriedades:


1) a é congruente a a módulo m


2) Se a congruente a b módulo m então b é congruente a a módulo m.


3) Se a congruente a b módulo m e b é congruente a c módulo m então a é congruente a c módulo m.


4) Se a congruente a b módulo m e c é congruente a d módulo m então a + c é congruente a b + d módulo m.


5) Se a congruente a b módulo m e c é congruente a d módulo m então .


6) Se a congruente a b módulo m então a elevado a n é congruente a b elevado a n módulo m.


As três últimas propriedades, em particular, são muito úteis para resolver questões que envolvam descobrir o resto de uma divisão euclidiana. Por exemplo: qual o resto da divisão de 230 por 17?


Evidentemente, nós poderíamos calcular o valor de 230 e, a seguir, dividí-lo por 17, mas essa não seria uma tarefa fácil, pois 230 é um número extremamente grande, o qual apenas softwares especializados podem calcular com precisão e, ainda assim, após um certo tempo. Fazer uma divisão dessas em uma calculadora comum, considerando-se que ela consiga calcular o valor de 230 certamente nos daria um resultado impreciso e dificultaria nossa tarefa de encontrar o resto desejado. Será que não existe uma forma mais rápida e fácil de fazer essa conta?


Através das propriedades das congruências módulo m, podemos encontrar o resto de divisões como essa sem muito esforço e de forma precisa. Inicialmente, notemos que 2 elevado a 4 é congruente a -1 módulo 17. Utilizando a propriedade 6, podemos elevar ambos os lados da congruência a 7 e obtemos que 2 na 28 é congruente a -1 módulo 17. Multiplicando-se os dois termos da congruência por 4, que na verdade é 22, obtemos que 2 na 30 é congruente a -4 módulo 17 e como 4 é congruente a 13 módulo 17, pela propriedade 3 temos que 2 na 30 é congruente a 13 módulo 17 e, dessa forma, concluímos que o resto da divsão é 13.


(Partes desse post tiveram como base o livro Curso de Álgebra, Volume I, de Abramo Hefez)

Comentários

  1. Olá André, sou estudante do 2º ano do curso de Licenciatura em Matemática, e gostei muito do seu artigo, gostaria de saber se vc pode me ajudar a resolver o seguinte:
    qual o resto da soma modulo 7 =
    2222^5555+5555^2222 (dois mil duzentos e vinte e dois elevado á cinco mil quinhentos e cinquenta e cinco)

    ResponderExcluir
  2. 1º passo: Transformar as bases em congurência módulo 7
    2222~3mod7 e 5555~4mod7

    2º passo: Observar as potências de 3 e 4 módulo 7
    potências de 3 módulo 7= 3, 2, 6, 4, 5, 1 (repete nessa ordem)
    potências de 4 módulo 7= 4,2,1 (repete nessa ordem)

    3º passo: Analisar as potências 5555 e 2222
    Como a repetição das potências de 3 é dada a cada 6 números:
    5555~5 mod6 =>3^5555~3^5~5 mod7
    Como a repetição das potências de 4 é dada a cada 3 números:
    2222~2 mod3 =>4^2222~4^2~2 mod7

    4º passo: Basta somarmos as parcelas
    2222^5555 + 5555^2222= (5+2) mod7 => 0 mod7

    Logo, provamos que 2222^5555+5555^2222 deixa resto zero na divisão por 7.

    ResponderExcluir
  3. Parabéns pelo espaço criado. Vou indicar para os meus alunos.
    Segue uma contribuição, foi uma das questões do Colégio Naval-RJ-2011:
    (Questão 4 da Prova Verde)
    É correto afirmar que o número (5^2011) + 2(11^2011) é múltiplo de
    (A) 13
    (B) 11
    (C) 7
    (D) 5
    (E) 3

    ResponderExcluir
  4. Gabriel dos Santos13 de março de 2012 11:41

    Parabéns pelo artigo, muito interessante. Gostaria da resolução deste exercício :
    a) Encontre todos os inteiros positivos n para os quais (2^n ) - 1 é divisível por 7.

    b) Prove que não há inteiro positivo n para o qual (2^n) + 1 é divisível por 7.

    ResponderExcluir
  5. No texto há uma falha pois 4 não é congruente a 13 módulo 17. O correto seria - 4 é côngruo a 13 módulo 17.

    ResponderExcluir
  6. EVALDO MORAES DE SOUZA23 de abril de 2013 03:35

    como resolver esta questão:

    a) ache o menor inteiro positivo que seja congruente a - 513 módulo 9

    ResponderExcluir
  7. Sou aluna do curso de matemática como resolver
    sejam a e b inteiros tal que a=b^3. mostre que a=1mod(9) ou a=0mod(9)ou a=8mod(9)
    Obrigada

    ResponderExcluir
  8. como se resolve a questão 2^340=1(
    mod341)???

    ResponderExcluir
  9. Cleonice Pereira dos Santos13 de novembro de 2014 00:21

    Um conjunto de m inteiros, m > 0, forma um sistema completo de restos módulo m denominando uma partição em classes de equivalência, que correspondem aos possíveis restos da divisão.

    Lembrando que a congruência é uma relação de equivalência definida no conjunto Z.

    Considerando a congruência módulo 6, escreva como é formado o sistema completo de restos, ou seja, as suas classes de equivalência. (É necessário que escreva pelo menos 8 elementos em cada sistema

    ResponderExcluir
  10. Olá André, sou estudante do 2º ano do curso de Licenciatura em Matemática, e gostei muito do seu artigo, tem como vc me ajudar a resolver a seguinte questões
    Qual o algarismo das unidades do números 222^333+333^222 ?
    Encontrar os resto das divisões 5^3^20 por 13
    Encontrar os restos da divisões (116 - 17 ^17) por 8

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.