24

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.265

Passo 1 de 17keyboard_arrow_downkeyboard_arrow_up

A relação congruente nos número inteiros é definida como , se um número positivo inteiro n, dois inteiros a e b são considerados congruentes de módulo n e escrito como se a diferença deles a-b for inteiro e múltiplo de n. O número n é chamado o módulo de congruência.

Passo 2 de 17keyboard_arrow_downkeyboard_arrow_up

Agora definindo um grupo com operações binárias de adição e multiplicação. A classe equivalente de dois inteiros determinados unicamente pela classe de equivalência de suas somas ou produtos. Ou seja se e então, temos que:

Passo 3 de 17keyboard_arrow_downkeyboard_arrow_up

Então, nós podemos definir a adição e muliplicação modulo n, denotada por e , respectivamente como sendo:

Passo 4 de 17keyboard_arrow_downkeyboard_arrow_up

Usando a definição de adição e multiplicação de módulo n , nós podemos obter o grupo aditivo modulo n, como e o grupo multiplicativo como .

Passo 5 de 17keyboard_arrow_downkeyboard_arrow_up

A tabela abaixo nos fornece o grupo de operação para o grupo

0

1

2

3

0

0

1

2

3

1

1

2

3

0

2

2

3

0

1

3

3

0

1

2

Passo 6 de 17keyboard_arrow_downkeyboard_arrow_up

A tabela abaixo nos fornece o grupo de operação para o grupo

1

2

3

4

1

1

2

3

4

2

2

4

1

3

3

3

1

4

2

4

4

3

2

1

Passo 7 de 17keyboard_arrow_downkeyboard_arrow_up

Agora devemos mostrar que esses grupos são isomorficos , mostrando a corespondência um-por-um de e elementos como se e somente se:

Passo 8 de 17keyboard_arrow_downkeyboard_arrow_up

Vamos definir a função como:

de forma que

Passo 9 de 17keyboard_arrow_downkeyboard_arrow_up

Onde e

Passo 10 de 17keyboard_arrow_downkeyboard_arrow_up

A função f de A para B é chama um-por-um (ou 1-1) sempre que:

Passo 11 de 17keyboard_arrow_downkeyboard_arrow_up

Claramente é uma função 1-1 , já que , nenhum elemento de possui a imagem com um elemento a mais que .

Passo 12 de 17keyboard_arrow_downkeyboard_arrow_up

Seja , e , ou seja todos eles pertecem ao grupo

Passo 13 de 17keyboard_arrow_downkeyboard_arrow_up

Simplificando as contas temos que:

Ou seja, que é divisivel por 4.

Passo 14 de 17keyboard_arrow_downkeyboard_arrow_up

Em relação a multiplicação temos que:

Passo 15 de 17keyboard_arrow_downkeyboard_arrow_up

Substituindo os valores encontramos que:

Passo 16 de 17keyboard_arrow_downkeyboard_arrow_up

Efetuando a multiplicação temos que:

Ou seja é divisivel por 5.

Passo 17 de 17keyboard_arrow_downkeyboard_arrow_up

Com isso n ós provamos que se , portanto esses grupos são isomórficos mostrando sua correspondencia 1-1 de e os elementos se e somente se .

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.