1- Seja
. Dada a relação de congruência módulo
por
é divisível por
, mostrar que é uma relação de equivalência e descrever as classes de equivalência para
.
Passo 1
O enunciado dá a relação de congruência módulo
, definida por
onde
. O que se pede:
- Mostrar que essa relação é uma relação de equivalência (ou seja, provar reflexividade, simetria e transitividade).
- Descrever as classes de equivalência (os conjuntos de inteiros congruentes entre si) nos casos
, e .
As informações relevantes fornecidas:
é um inteiro positivo e a definição de quando dois inteiros são congruentes módulo
.
Passo 2
Provar reflexividade.
Definição: uma relação é reflexiva se todo satisfaz
relacionado com
. Aqui devemos mostrar
para todo
.
Cálculo: para todo tem-se
. O zero é divisível por
porque
. Portanto
é múltiplo de
, isto é
. Conclusão: a relação é reflexiva.
Definição: uma relação é reflexiva se todo
Cálculo: para todo
Passo 3
Provar simetria.
Definição: uma relação é simétrica se relacionado com
implica
relacionado com
. Aqui: se
então
.
Demonstração: suponha . Então existe
tal que
. Portanto
, que é múltiplo de
. Logo
. Conclusão: a relação é simétrica.
Definição: uma relação é simétrica se
Demonstração: suponha
Passo 4
Provar transitividade.
Definição: uma relação é transitiva se relacionado com
e
relacionado com
implicam
relacionado com
. Aqui: se
e
então
.
Demonstração: suponha e
. Então existem
tais que
e
. Somando as duas igualdades obtém-se
Definição: uma relação é transitiva se
Demonstração: suponha
ou seja,
é múltiplo de
. Logo
. Conclusão: a relação é transitiva.
Passo 5
Conclusão geral sobre equivalência.
Como a relação é reflexiva, simétrica e transitiva, ela é uma relação de equivalência em . Por teoria geral, uma relação de equivalência particiona
em classes de equivalência. Agora vamos descrever explicitamente essas classes para o caso da congruência módulo
.
Como a relação é reflexiva, simétrica e transitiva, ela é uma relação de equivalência em
Passo 6
Definição e forma explícita de uma classe de equivalência.
A classe de equivalência de um é o conjunto
A classe de equivalência de um
Mostraremos que essa classe é exatamente
Prova das duas inclusões:
- Se
então , logo existe com . Assim , então . - Se
com , então é múltiplo de , logo e .
Portanto. Interpretação intuitiva: a classe de contém todos os inteiros que dão o mesmo resto que na divisão por .
Passo 7
Representantes canônicos e número de classes.
Pelo algoritmo da divisão, para qualquer existem inteiros únicos
e
tais que
Pelo algoritmo da divisão, para qualquer
Isso mostra que
, ou seja, cada classe tem pelo menos um representante em
. Se
então
(pois
é um inteiro entre
e
, não múltiplo de
), logo as classes
são distintas e cobrem todas as classes possíveis. Conclusão: existem exatamente
classes de equivalência módulo
, representadas por
.
Passo 8
Descrição explícita das classes para
.
- Para
: os representantes possíveis são apenas . De segue que todo inteiro é congruente a . Portanto
Há apenas uma classe.
- Para
: os representantes são e . As classes são
Essas duas classes são disjuntas e cobrem todos os inteiros.
- Para
: os representantes são . As classes são
Novamente são disjuntas e a união delas é
. Exemplos úteis:
porque
;
porque
.
Resposta
Para
Para
Para