Lista de Exercícios Resolvidos - Estruturas Algébricas e Congruências

Lista de Exercícios 2 Estruturas Algébricas Problema 1 Resposta Um sistema básico de resíduos para m é 0 1 2 m 1 Um SCR tem exatamente m elementos e se pegamos x y a a 1 a 2 a m 1 é tal que x y m 1 Assim nenhuma dessas classes é equivalente por módulo m Assim são m classes distintas que mostra que devem equivaler a 0 1 2 m 1 Problema 2 Resposta Basta observar que a bp sumi0p p choose i ai bp1 a observação que nos leva a esta conclusão é que como p é primo p i e i não têm fator p Assim p choose i 0 mod p e portanto temos a bp sumi0p p choose i ai bp1 ap bp mod p Problema 3 Resposta Observe que 7n 2r1 1 7n 3r2 1 7n 4r3 1 7n 5r4 1 7n 6r5 1 Usando as duas primeiras relações 2r1 1 7n 3r2 1 Isto implica que 2 divide r2 e 3 divide r1 Podemos escrever 7n 6s 1 1 a b mod m a c b c mod m 2 ι c b c mod m a b mod mm c Corolário 6 Sejam a b c m Z com m 1 e m c 1 Temse que a c b c mod m a b mod m Roteiro Congruˆencias Elisabete Sousa Freitas UFMS 11 de marco de 2023 1 Congruˆencias Definicao 1 Seja m um numero natural Dois numeros inteiros a e b sao congruentes modulo m se os restos das divisoes euclidianas de a e b por m forem iguais Neste caso escrevemos a b mod m Proposicao 1 Sejam a b m Z com m 1 Temse que a b mod m mb a Proposicao 2 Seja m N Para todos a b c Z temse que 1 a a mod m 2 Se a b mod m entao b a mod m 3 Se a b mod m e b c mod m entao a c mod m 4 Se a b mod m e c d mod m entao a c b d mod m 5 Se a b mod m e c d mod m entao a c b d mod m 6 Se a b mod m entao an bn mod m para todo numero natural n Teorema 3 Pequeno Teorema de Fermat Se p e um numero primo e a Z entao ap a mod p Alem disso se p a entao ap1 1 mod p Definicao 2 Um Sistema Completo de Resıduos modulo m e um conjunto qualquer de m numeros inteiros cujos restos das divisoes por m sao exatamente os numeros 0 1 m 1 Observamos que se a1 a2 am sao inteiros dois a dois nao congruentes modulo m entao a1 a2 am e um Sistema Completo de Resıduos modulo m SCR Proposicao 4 Sejam a b c m Z com m 1 Temse que a b mod m a c b c mod m Proposicao 5 Sejam a b c m Z com m 1 Temse que 1 a b mod m a c b c mod m 2 a c b c mod m a b mod m m c Corolario 6 Sejam a b c m Z com m 1 e m c 1 Temse que a c b c mod m a b mod m Proposicao 7 Considere inteiros a b e m m1 m2 mr 1 Temse que 1 Se a b mod m e nm entao a b mod n 2 a mod mi para todo i 1 2 r a b mod m1 m2 mr 3 Se a b mod m entao a m b m Exercıcio 1 Prove que a a 1 a m 1 e um SCR para todo a Z Exercıcio 2 Se p e um numero primo e a b Z prove que a bp ap bp mod p Exercıcio 3 Determine o menor multiplo positivo de 7 que deixa resto 1 quando dividido por 2 3 4 5 e 6 Exercıcio 4 Determine o resto da divisao de 23829 por 13 Exercıcio 5 Mostre que 45133n 173n para todo n inteiro ımpar Exercıcio 6 Determine o algarismo das unidades do numero 717 Exercıcio 7 Ache o menor numero natural que deixa restos 5 4 3 e 2 quando dividido respectivamente por 6 5 4 e 3 Exercıcio 8 Mostre que a soma dos quadrados de quatro numeros naturais consecutivos nunca pode ser um quadrado Exercıcio 9 Determine o algarismo das unidades do numero 999 Exercıcio 10 Determine o resto da divisao de a 117 171721 por 8 b 1316 225 515 por 3 c 1 2 1010 por 40 d 2100 por 11 Exercıcio 11 Determine o resto da divisao por 7 do numero a 1010 10102 1010100 b 22225555 55552222 Exercıcio 12 Determine os algarismos das unidades do numero 7999999 2 Exercıcio 13 Mostre para todo n N que a 102n 1 mod 11 b 102n1 1 mod 11 Exercıcio 14 Mostre que um numero natural na base 10 e divisıvel por 6 se e somente se a soma do algarismo das unidades com o quadruplo de cada um dos outros algarismos e divisıvel por 6 Exercıcio 15 Mostre que se n 2 entao o numero de Fermat Fn 22n 1 tem algarismo das unidades igual a 7 3 Referˆencias Bibliograficas 1 DOMINGUES Hygino IEZZI Gelson Algebra Moderna 4Ed Sao Paulo Atual 20032011 2 GONCALVES Adilson Introducao a Algebra 5 Ed Rio de Janeiro IMPA 20062012 Projeto Euclides 3 HEFEZ Abramo Curso de Algebra Volume I 2 Ed Rio de Janeiro IMPA 1997 Colecao Matematica Universitaria 4 MILIES Cesar Polcino COELHO Sonia Numeros Uma Introducao a Matematica 3 Ed Sao Paulo EDUSP 2013 4 1 Se a b mod m e nm então a b mod n 2 a mod mi para todo i 1 2 r a b mod m1 m2 mr 3 Se a b mod m então a m b m Exercício 1 Prove que a a 1 a m 1 é um SCR para todo a Z Exercício 2 Se p é um número primo e a b Z prove que a bp ap bp mod p Exercício 3 Determine o menor múltiplo positivo de 7 que deixa resto 1 quando dividido por 2 3 4 5 e 6 Exercício 4 Determine o resto da divisão de 23829 por 13 Exercício 5 Mostre que 45133n 173n para todo n inteiro ímpar Exercício 6 Determine o algarismo das unidades do número 717 Exercício 7 Ache o menor número natural que deixa restos 5 4 3 e 2 quando dividido respectivamente por 6 5 4 e 3 Exercício 8 Mostre que a soma dos quadrados de quatro números naturais consecutivos nunca pode ser um quadrado Exercício 9 Determine o algarismo das unidades do número 99 Exercício 10 Determine o resto da divisão de a 117 171721 por 8 b 1316 225 515 por 3 c 1 2 1010 por 40 d 2100 por 11 Exercício 11 Determine o resto da divisão por 7 do número a 1010 10102 1010100 b 22225555 55552222 Exercício 12 Determine os algarismos das unidades do número 7999999 que é igual a última equação Portanto a última é redundante Usaremos esta equação com 7n 4r3 1 que dá 6s 1 7n 4r3 1 que implica que 3 divide r3 e 2 divide s Assim chegamos à 7n 12t1 Por fim precisamos comparar com 7n 5r4 1 e obtemos 12t 1 7n 5r4 1 que nos leva a 7n 60u 1 Isto permite dizer que o número múltiplo de 7 que reúne essas propriedades satisfaz 7n 60u 1 7n 60u 1 temos que 60 7 8 4 7 4 1 3 4 31 1 resultando em 1 4 1 7 1 4 1 1 1 4 2 7 1 1 60 1 7 8 2 7 1 60 2 7 17 Os valores que satisfazem a equação são n 2 7t u 17 60t Um primeiro é 43 7 301 Problema 4 Resposta Pelo teorema de Fermat como 13 não divide 238 temos que 23812 1 mod 13 Assim temos 23829 2381225 238122 2385 2385 45 mod 13 23829 13 78 10 10 mod 13 Assim o resto é 10 Problema 5 2 Resposta Problema 6 Resposta Problema 7 Resposta Problema 8 Resposta Problema 9 Resposta Problema 10 Resposta Problema 11 Resposta a A soma é 1010 10102 1010100 Pelo teorema de Fermat temos que 7 divide 10 implica em 106 1 mod 7 Os elementos são dados por 1 O número é 1010 106 104 104 34 4 mod 7 2 O número é 10102 1098 102 102 32 2 mod 7 3 O número é 101000 1010010 10210 210 26 24 2 mod 7 4 Indutivamente se percebe que se k 2 temos 1010k1 1010k 10 210 26 24 24 mod 7 2 mod 7 Assim temos que os restos somados são 4 2 99 1 mod 7 b Para a soma 22225555 55552222 22226925 5 55556370 2 Pelo teorema de Fermat como 7 não divide 2222 e nem 5555 temos que 22226925 22225 35 5 mod 7 55556370 55552 42 2 mod 7 Assim sendo o resto desta soma é 0 pois resta 5 da primeira parcela e 2 da segunda parcela sendo assim 7 que é divisível por 7 Problema 12 Resposta Vamos começar investigando os algarismos da unidade nos primeiros casos 1 Observe que 71 é o próprio 7 2 Observe que 72 é 49 que tem na unidade 9 3 Observe que 73 é 343 que tem na unidade 3 4 Observe que 74 é 2401 que tem na unidade 1 Isso que vimos antes nos permite fazer 742499993 2401249999 73 243 3 mod 10 Isto é consequência na generalização do teorema de Fermat chamado de teorema de EulerFermat Note que ϕ10 4 e assim como 74 1 mod 10 segue o que fizemos acima Problema 13 Resposta a Por indução observe que 1020 1 mod 11 1021 100 1 mod 11 Agora suponha por hipótese de indução que 102k 1 mod 11 teremos que 102k2 1 mod 11 Se transforma em 102k 102 1 mod 11 Logo para todo k ℕ temos que 102k 1 mod 11 b Como vimos antes 102n 1 mod 11 Assim sendo temos 102k1 102k 10 1 10 1 mod 11 Como queríamos demonstrar Problema 14 Resposta Suponha que um número n é divisível por 6 Sabemos que este número é par e divisível por 3 Vamos representar ele por seus algarismo n Xk X1 satisfazendo m X1 X2 Xk significa que 3 divide m Observe que X1 3r X1 3r 1 ou X1 3r 2 Vamos tratar cada caso a Se X1 3r X1 0 6 temos m X1 X2 Xk Lembre que m é divisível por 3 Assim temos se X1 0 que X14m X1 4 3 l Por outro lado se X1 6 temos que 6 4m X1 6 4 3 l Ambos são divisíveis por 6 b Se X1 3r 1 X1 4 temos m 4 X2 Xk Resulta em X1 4X2 4Xk 4 4 m 4 4 43l 4 12l 12 c Se X1 3r 2 X1 2 8 temos m X1 X2 Xk Em caso de X1 2 temos X1 4X2 4Xk 2 43l 2 2 12l 8 12l 6 que é divisível por 6 Se X1 8 temos X1 4X2 4Xk 8 43l 8 8 12l 32 12l 24 também divisível por 6 5 Isto permite concluir que X1 4X2 4Xk é sempre divisível por 6 Por outro lado se m X1 4X2 4Xk é divisível por 6 então é divisível por 3 Temos que X1 X2 Xk m 3X2 Xk assim n é divisível por 3 Além disso como X1 m 4X2 Xk que implica que X1 é par Assim n é um número divisível por 6 Problema 15 Resposta Observe que F2 24 1 17 e podemos supor que para k vale que Fk tem dígito das unidades igual 7 Fk1 22k1 1 podemos manipular de modo que Fk1 22k1 1 22k2 1 22k 1 22k 22k 1 Como sabemos 22k 1 mod 10 implica 22k 1 0 mod 10 Assim podemos concluir que 22k 1 22k é múltiplo de 10 e assim a soma termina com dígito das unidades igual a 7