Geometria Analítica 2

UABMAT017 INTRODUC AO A TEORIA DOS NUMEROS 11 AULA 11 SISTEMA COMPLETO DE RESTOS E CLASSES RESIDUAIS 111 Sistema completo de restos Definicao 111 Seja m um inteiro positivo fixo Chamase sistema completo de restos modulo m SCR mod m todo conjunto S r1 r2 rm de m inteiros tal que um inteiro qualquer a e congru ente modulo m a um unico elemento de S Proposicao 111 O conjunto S 0 1 2 m 1 e um sistema completo de restos modulo m ou SCR mod m Demonstracao Queremos mostrar que todo inteiro a e congruente modulo m a exatamente um dos valores 0 1 2 m 1 Seja a Z Pelo algoritmo da divisao de a por m existem unicos inteiros q e r tais que a mq r com 0 r m1 Logo ar mq e a r mod m Pela unicidade de r obtemos o resultado Corolario 111 S r1 r2 rm Z e um SCR mod m se e somente se cada elemento de S 0 1 2 m 1 e congruente modulo m a um unico elemento de S Demonstracao Seja s S Entao s r mod m para um unico r S pois S e um SCR mod m por hipotese Seja a Z Entao a k mod m para um unico k S pois S e um SCR mod m pela proposicao anterior Por hipotese existe um unico r S tal que k r mod m logo existe um unico r S tal que a r mod m Portanto S e um SCR mod m 54 Exemplo 111 S 12 4 11 13 22 82 91 e um SCR mod 7 pois 0 91 mod 7 1 22 mod 7 2 12 mod 7 3 4 mod 7 4 11 mod 7 5 82 mod 7 e 6 13 mod 7 112 Classes residuais 1121 Revisao de relacao Sejam A e B dois conjuntos nao vazios Uma relacao de A em B e qualquer subconjunto do produto cartesiano A B Uma relacao sobre A e uma relacao de A em A Uma relacao de equivalˆencia R sobre A e uma relacao sobre A que satisfaz as seguintes propriedades 1 Reflexiva x A x R x 2 Simetrica x Ay A x R y y R x 3 Transitiva x Ay Az A x R y e y R z x R z Se R e uma relacao de equivalˆencia sobre A e a A definimos Cla a x A x R a classe de equivalˆencia de a A pela relacao de equivalˆencia R AR a a A conjunto quociente de A pela relacao de equivalˆencia R 1122 Definicao e propriedades Definicao 112 Seja m um inteiro positivo fixo Se a e um inteiro qualquer entao a classe residual modulo m de a denotada por a ou am ou am consiste do conjunto formado por todos os inteiros que sao congruentes ao inteiro a modulo m isto e a x Z x a mod m x Z m x a a km k Z Observacao 111 1 A notacao a deve ser usada somente quando ficar claro pelo contexto o valor do inteiro m utilizado do contrario a notacao am e a mais indicada 2 A classe residual de um inteiro e a classe de equivalˆencia deste inteiro pela relacao de congruˆencia que e uma relacao de equivalˆencia como visto anteriormente 3 Se m 1 e a Z temos a x Z 1 x a Z 4 As classes residuais modulo m tambem sao denominadas inteiros modulo m ou classes de restos modulo m ou classes de congruˆencia modulo m 5 Se a Z entao a pois como a a mod m temos que a a 55 Exemplo 112 Seja m 12 Temos 3 x Z x 3 mod 12 x Z 12 x 3 x Z x 12k 3 para algum k Z 21 9 3 15 15 x Z x 15 mod 12 Como 15 3 mod 12 entao x 15 mod 12 se e somente se x 3 mod 12 Logo 15 x Z x 3 mod 12 3 Proposicao 112 Seja m um inteiro positivo fixo e sejam a e b as classes residuais modulo m de dois inteiros quaisquer a e b Entao 1 a b a b mod m 2 a b ou a b Demonstracao 1 Se a b entao b a donde a b mod m Seja c a Entao c a mod m e como a b mod m segue que c b mod m isto e c m Assim a b Analogamente dado c b temos que c a e entao b a Portanto a b 2 Suponha que a b Entao existe c a b Assim c a e c b donde c a mod m e c b mod m Segue entao que a b mod m e pelo item anterior a b Observacao 112 A classe residual a dizse determinada ou definida pelo inteiro a o qual chamase um representante de a Pelo resultado anterior dois inteiros sao representantes de uma mesma classe residual modulo m a b se e somente se sao congruentes modulo m a b mod m 1123 O conjunto das classes residuais O conjunto formado por todas as classes residuais modulo m ou seja a a Z e indicado por Zm ou ZmZ Observacao 113 1 A notacao Zm comumente usada no Brasil e tambem utilizada para denotar o conjunto dos inteiros padicos estudados em Teoria Analıtica dos Numeros Como no nosso curso nao tra taremos de inteiros padicos usaremos a notacao acima para o conjunto das classes residuais modulo m 2 Se m 1 entao a Z a Z logo Z1 Z 3 Zm e o conjunto quociente de Z pela relacao de equivalˆencia congruˆencia modulo m Proposicao 113 O conjunto Zm tem exatamente m elementos Demonstracao Vamos mostrar que Zm 0 1 m 1 e que 0 1 m 1 tem exatamente m elementos 56 1 E claro que 0 1 m 1 Zm 2 Seja a Zm onde a Z Pelo algoritmo da divisao de a por m existem inteiros q e r tais que a mq r 0 r m 1 Assim a r mq donde m a r Logo a r mod m e pela proposicao anterior temos a r Como 0 r m 1 entao a r 0 1 m 1 Portanto Zm 0 1 m 1 De 1 e 2 concluımos que Zm 0 1 m 1 3 Suponha que r s onde r s Z tais que 0 r s m 1 Pela proposicao anterior temos que r s mod m Assim s r mod m e m s r Mas isto e um absurdo pois 0 s r m Portanto 0 1 m 1 tem exatamente m elementos Observacao 114 1 Zm e um conjunto finito embora Z seja um conjunto infinito 2 Para achar a classe residual modulo m de um inteiro qualquer y basta determinar o resto r da divisao de y por m pois y r com 0 r m 1 3 As classes residuais 0 1 m 1 que formam o conjunto Zm sao subconjuntos nao vazios de Z disjuntos dois a dois e sua reuniao e o conjunto Z Logo Zm e uma particao de Z 4 O conjunto de m representantes um de cada uma das classes residuais 0 1 m 1 e um sistema completo de restos modulo m 5 A imagem geometrica correspondente a Zm e de uma circunferˆencia onde estao marcados m pontos equidistantes Cada ponto corresponde a uma das classes de equivalˆencia de Zm Enrolamos Z na reta em uma circunferˆencia Colamos o ponto m ao ponto 0 Como a reta e infinita continuamos a enrolala na circunferˆencia Exemplo 113 1 Qual e a classe residual modulo 8 de 75 Temos que 75 8 9 3 donde 75 3 mod 8 e entao 75 3 3 8k k Z 2 Z2 0 1 onde 0 2k k Z 4 2 0 2 4 1 2k 1 k Z 3 1 0 1 3 Observe que 0 1 e 0 1 Z 3 Z5 0 1 2 3 4 onde 0 5k k Z 1 5k 1 k Z 2 5k 2 k Z 3 5k 3 k Z 4 5k 4 k Z Essas classes sao duas a duas disjuntas e sua reuniao e o conjunto Z 57 1124 Exercícios 1 Achar a classe residual módulo 8 de 5 2 Achar a classe residual módulo 9 de 1913 3 O inteiro 17 pertence à classe residual módulo m de 24 Determinar m 4 Os inteiros 29 e 41 pertencem a uma mesma classe residual módulo m Determinar m 5 Mostrar que a 103 13 b 8419 819 c 87 207 1125 Adição e Multiplicação em Zm Seja m um inteiro positivo fixo Vamos definir as operações de adição e multiplicação no conjunto Zm das classes residuais módulo m Sejam a x b y Zm Temos que se a x e b y então a x mod m e b y mod m logo a b x y mod m e ab xy mod m e consequentemente a b x y e ab xy Isto torna lícitas as seguintes definições Definição 113 1 Dadas duas classes a b Zm chamase soma a b a classe a b que é única independentemente do representante tomado para a ou para b Zm Zm Zm a b a b a b 2 Dadas duas classes a b Zm chamase produto ab a classe ab que é única independentemente do representante tomado para a ou para b Zm Zm Zm ab ab ab Proposição 114 Sejam a b c Zm 1 Associatividade da soma a b c a b c 2 Comutatividade da soma a b b a 3 Elemento neutro para a soma a 0 a 4 Elemento simétrico para a soma a m a 0 58 5 Associatividade do produto abc abc 6 Comutatividade do produto ab ba 7 Elemento neutro para o produto a1 a 8 Distributividade da multiplicacao em relacao a adicao ab c ab ac Demonstracao Exercıcio Dica a maioria segue das propriedades de congruˆencia Proposicao 115 a Zm e simetrizavel para a multiplicacao isto e admite inverso multiplicativo se e somente se mdca m 1 Demonstracao a Zm admite inverso multiplicativo b Zm tal que ab 1 ab 1 ab 1 mod m m ab 1 q Z tal que ab 1 mq ab mq 1 ab mq 1 mdca m 1 mdca m 1 x y Z tal que ax my 1 ax 1 my m ax 1 ax 1 mod m ax 1 ax 1 a admite inverso multiplicativo Observacao 115 O conjunto dos elementos de Zm que tˆem inverso multiplicativo sera denotado por Um isto e Um a Zm mdca m 1 Exemplos Para p primo temos Up a Zp mdca p 1 Zp 0 U4 1 3 U8 1 3 5 7 1126 Exercıcios 1 Construa as tabelas de adicao de Z4 e Z5 2 Construa as tabelas de multiplicacao para Z4 e Z5 3 Determine todos os elementos inversıveis de Z9 e encontre os seus respectivos inversos multipli cativos 59 1 Note que 5 81 3 Daí 5 3 mod 8 e então 5 3 3 8k k Z 2 Note que 1913 9212 5 Daí 1913 5 mod 9 e então 1913 5 5 9k k Z 3 Note que 17 240 17 Daí 17 17 mod 24 e então 17 pertence à classe residual módulo 17 de 24 4 Se 29 e 41 pertencem à mesma classe residual módulo m então 29 41 mod m 41 29 mod m m 41 29 ou seja m 12 Logo m 1 2 3 4 6 12 5 Note que a 10 33 1 Daí 10 1 mod 3 e portanto 103 13 b Note que 84 194 8 Daí 84 8 mod 19 e portanto 8419 819 c Note que 8 72 6 e 20 72 6 Daí 8 6 mod 7 e 20 6 mod 7 e portanto 87 207 3 Z4 0 1 2 3 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Z5 0 1 2 3 4 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 2 Z4 0 1 2 3 0 1 2 3 0 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 Z5 0 1 2 3 4 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 4 2 1 4 0 4 3 2 1 3 Z9 0 1 2 3 4 5 6 7 8 Note que mdc 1 9 1 mdc 2 9 1 mdc 4 9 1 mdc 5 9 1 mdc 7 9 1 mdc 8 91 Portanto pela Proposição 115 os elementos inversíveis de Z9 são U9 1 2 4 5 7 8 Note que 33 1 portanto 3 é inverso multiplicativo de 3 em Z9 25 1 portanto 2 é inverso multiplicativo de 5 em Z9 47 1 portanto 7 é inverso multiplicativo de 4 em Z9 88 1 portanto 8 é inverso multiplicativo de 8 em Z9 52 1 portanto 2 é inverso multiplicativo de 5 em Z9 74 1 portanto 4 é inverso multiplicativo de 7 em Z9