If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Curso: Computer science theory > Unidade 2

Lição 5: Aritmética modular
Computação
Computer science theory
Criptografia
Aritmética modular
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies

Relações equivalentes

Google Sala de Aula

Afirmações equivalentes

Antes de prosseguir, é importante lembrar que as afirmações a seguir são equivalentes
  • A≡B (mod C)
  • A mod C=B mod C
  • C | (A−B) (O | símbolo significa dividir, ou é um fator de)
  • A=B+K⋅C (onde K é um inteiro)
Isto nos permite alternar entre diferente formas de expressar a mesma ideia.
Por exemplo, a seguintes expressões são equivalentes:
  • 13≡23 (mod 5)
  • 13 mod 5=23 mod 5
  • 5 | (13−23) ( 5 | −10, que é verdadeiro, já que 5×(−2)=−10 )
  • 13=23+K⋅5. Nós podemos satisfazer isso com K=−2: 13=23+(−2)×5

O Modulo de Congruência é uma Relação de Equivalência

tortas

Convença a si mesmo que as fatias usadas no exemplo anterior possuem as seguintes propriedades:
  • Todos pares de valores em uma fatia são relacionados uns aos outros
  • Nós nunca vamos encontrar um valor em mais de uma fatia (fatias são mutuamente disjuntas)
  • Se nós combinássemos todas as fatias, elas formariam uma torta contendo todos os valores
Uma torta com fatias que têm essas propriedades têm uma relação de equivalência.
Uma relação de equivalência define como nós podemos cortar nossa torta (como podemos particionar nosso conjunto de valores) em pedaços (classes equivalentes).
Em geral, as relações de equivalência devem ter essas propriedades:
  • A torta: Uma coleção de todos os valores nos quais nós estamos interessados
  • Uma fatia da torta: uma classe equivalente
  • Como nós cortamos a torta em pedaços: relação de equivalência
Especificamente, para o nosso exemplo anterior:
  • A torta: a coleção de todos os números inteiros
  • Um pedaço da torta rotulado B: classe equivalente onde todos os valores mod C=B
  • Como nós cortamos a torta em pedaços: usando a relação Módulo de Congruência C, ≡(mod C)
É por isso que nós dizemos que Módulo de Congruência C é uma relação de equivalência. Ela particiona os números inteiros em C classes equivalentes diferentes.

Por que nos preocupamos que o módulo de congruência C seja uma relação de equivalência?

Sabendo que o módulo de congruência C é uma relação de equivalência, nos permite saber sobre algumas propriedades que ele deve ter.
Relações de equivalência são relações que possuem as seguintes propriedades:
  • Eles são reflexivos: A é relacionado a A
  • Eles são simétricos: se A é relacionado com B, então B é relacionado com A
  • Eles são transitivos: se A é relacionado com B e B é relacionado com C então A é relacionado com C
Uma vez que o módulo de congruência é uma relação de equivalência para (mod C). Isso significa:
  • A≡A (mod C)
  • se A≡B (mod C) então B≡A (mod C)
  • se A≡B (mod C) e B≡D (mod C) então A≡D (mod C)

Exemplo

mod5
Vamos aplicar essas propriedades a um exemplo concreto, usando mod 5:
  • 3≡3 (mod 5) (propriedade reflexiva)
  • se 3≡8 (mod 5) então 8≡3 (mod 5) (propriedade simétrica)
  • se 3≡8 (mod 5) e se 8≡18 (mod 5) então 3≡18 (mod 5) (propriedade transitiva)

Quer participar da conversa?

Entrar
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.