Re: [obm-l] Re: [obm-l] Congruência modular
Olá Bruna. Vc pode pensar assim que não está errado. Creio que sua pergunta tem a ver com propriedades da congruência quevc ainda não está familiarizada. Por exemplo: Se b ≡ 1 mod 2 então b^2 ≡ 1 mod 2A pergunta q vc deve estar se fazendo, é como isso é concluído? As congruências podem ser somadas e multiplicadas, por exemplo tomeduas congruências:a ≡ b mod cc ≡ d mod c então temos que (ac) ≡ (bd) mod c Voltando ao exemplo anterior, tome duas congruencias b ≡ 1 mod 2b ≡ 1 mod 2 multiplique as duas: b^2 ≡ 1 mod 2 (sacou?). Agora tome duas congruências: b^2 ≡ 1 mod 2 1 ≡ 1 mod 2 some uma com a outra: b^2 + 1 ≡ ( 1 + 1) mod 2 ≡ 2 mod 2 ≡ 0 mod 2 2 e 0 pertencem a mesma classe de congruência módulo 2 (os pares) portanto .. ≡ 8 ≡ 6 ≡ 4 ≡ 2 ≡ 0 mod 2 Acho que essa página pode acrescentar algo:: http://math.usask.ca/encryption/lessons/lesson05/page4.html Em relação a exercícios novos é só vc entrar em contato com o pessoal que jáparticipou de olimpiadas brasileiras ou internacionais que eles tem bastantematereial e experiência podem te fornecer. Espero que minha humilde contribuição tenha te ajudado. []s Ronaldo Luiz Alonso On 3/29/07, Bruna Carvalho [EMAIL PROTECTED] wrote: Marcelo, muito obrigado acho que agora foi, só fiquei na dúvida em uma coisa, só pra ver se estou no caminho certo. quando você afirno que b^2+1 ≡ 2 ≡ 0 (mod 2) b^2+1 = 0 (mod 2) porque 2 ≡ 0 (mod 2) assim 2 divide 2, ou seja, deixa resto 0. assim b^2+1 ≡ 0 ≡ 2 (mod 2). mais uma coisa vocês tem mais alguns exercicios desse tipo pra mim treinar um pouco. Bjnhos, muito obrigado pela atenção e paciência comigo. -- -Analista de DesenvolvimentoConselho Regional de Engenharia, Arquitetura e Agronomia de SP. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Re: [obm-l] Congruência modular
Marcelo, muito obrigado acho que agora foi, só fiquei na dúvida em uma coisa, só pra ver se estou no caminho certo. quando você afirno que b^2+1 ≡ 2 ≡ 0 (mod 2) b^2+1 = 0 (mod 2) porque 2 ≡ 0 (mod 2) assim 2 divide 2, ou seja, deixa resto 0. assim b^2+1 ≡ 0 ≡ 2 (mod 2). mais uma coisa vocês tem mais alguns exercicios desse tipo pra mim treinar um pouco. Bjnhos, muito obrigado pela atenção e paciência comigo.
Re: [obm-l] Congruência modular
Olá Bruna, vou acrescentar alguns comentários 'as demonstrações dos colegas que podem passar despercebidos a você em uma primeira leitura. On 3/24/07, saulo nilson [EMAIL PROTECTED] wrote: n^2-1=(2t+1)^2-1 =4t^2+4t=4t(t+1) Se n é impar n se escreve como n = 2t+ 1 para todo t, logo temos que n^2 -1 = 4t(t+1) que é divisível por 4, logo é congruente a zero mod 4 (resto da divisão é zero). Por outro lado o colega Saulo está afirmando que t(t+1) é congruente a zero mod 2, ou seja, é divisivel por 2. Veja, temos que : 1) Se t for par então automaticamente t(t+1) é divisivel por 2, porque é o produto de um par por um impar, respectivamente (t é par e t+1 é impar). Se t for impar então t é impar, mas t+1 é par e t(t+1) é o produto de um impar por um par, respectivamente. logo 4t(t+1)=0mod8 Agora note que 4t(t+1) é divisivel por 4, por causa do quatro na frente. E que 4t(t+1) também é divisivel por 2, mas agora não por causa do 4, mas porque t(t+1) é divisivel por 2 e isso não tem nada a ver com o fator 4. Logo essas divisibilidades são independentes e 4t(t+1) é divisivel por 8, porque é divisivel por 4 e por 2. Assim podemos escrever: 4t(t+1) = 0mod8 aqui o = significa congruente e não igual. Uma coisa que é mais ou menos óbvia, mas que pode ser muito dificil de perceber a priori para resolver esse exercício é perceber que t (t+1) é sempre divisível por 2 para todo valor de t inteiro. Isso pode ser verificado por inspeção (tome t= 1, 2, 3 etc e verifique). Ou também por indução. Sallab mostrou, inclusive, que o problema todo pode ser resolvido por indução, como você deve ter checado. Bem, espero que minhas explicações não a tenham deixado mais confusa. Qq dúvida pergunte! Abraço! Ronaldo Luiz Alonso On 3/24/07, Bruna Carvalho [EMAIL PROTECTED] wrote: Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna -- - Analista de Desenvolvimento Conselho Regional de Engenharia, Arquitetura e Agronomia de SP.
Re: [obm-l] Congruência modular
Vamos ver se consigo, peguei um exercício bem simples pra tentar. Sejam a e b números naturais assim relacionados: a = 1 + b^2. Se b é ímpar, provar que a é par. fiz assim: a = 1 + b^2 b = 2k + 1 então temos: a = 1 + (2k+1)^2 a = 1 + 4k^2 + 4k + 1 a = 4k^2 + 4k + 2 a = 2(2k^2 + 2k + 1) como a tem um fator 2 ele vai ser par, se ele é par deixa 0 na divisão por 2, então: a ≡ 0 (mod 2). mas se eu for começar a fazer o exercício por congruência eu não consigo, só consigo concluir que a ≡ 0 (mod 2).
[obm-l] Re: [obm-l] Congruência modular
Ola Bruna, veja bem: b = 2k+1... entao b = 1 (mod 2) elevando ao quadrado: b^2 = 1 (mod 2) agora, somando 1, temos: b^2+1 = 2 = 0 (mod 2) espero que tenha ajudado abracos, Salhab - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Wednesday, March 28, 2007 7:53 PM Subject: Re: [obm-l] Congruência modular Vamos ver se consigo, peguei um exercício bem simples pra tentar. Sejam a e b números naturais assim relacionados: a = 1 + b^2. Se b é ímpar, provar que a é par. fiz assim: a = 1 + b^2 b = 2k + 1 então temos: a = 1 + (2k+1)^2 a = 1 + 4k^2 + 4k + 1 a = 4k^2 + 4k + 2 a = 2(2k^2 + 2k + 1) como a tem um fator 2 ele vai ser par, se ele é par deixa 0 na divisão por 2, então: a ≡ 0 (mod 2). mas se eu for começar a fazer o exercício por congruência eu não consigo, só consigo concluir que a ≡ 0 (mod 2).
[obm-l] Res: [obm-l] Congruência modular
É só fazer n =2k + 1 ou se vc preferir n = 2k -1. - Mensagem original De: Bruna Carvalho [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sábado, 24 de Março de 2007 14:19:14 Assunto: [obm-l] Congruência modular Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna __ Fale com seus amigos de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com/
[obm-l] Congruência modular
Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna
[obm-l] Re: [obm-l] Congruência modular
dá para fazer essa questão por PIF foi mal, eu nao vou fazer pq eu já tou de saída, mai essa questão é feita por isso tipo, se o caso( n ) acontece, logo o caso ( n+1 ), ocorre, ok?? abraços - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Saturday, March 24, 2007 2:19 PM Subject: [obm-l] Congruência modular Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna
[obm-l] Re: [obm-l] Congruência modular
Olá, n = 1(mod 8) ... n^2 = 1 (mod8) ... n^2-1 = 0(mod 8) n = 3(mod 8) ... n^2 = 9 = 1 (mod8) ... n^2 - 1 = 0 (mod 8) n = 5(mod 8) ... n^2 = 25 = 1(mod 8) ... n^2 - 1 = 0 (mod 8) n = 7(mod 8) ... n^2 = 49 = 1(mod 8) ... n^2 - 1 = 0 (mod 8) logo, esta provado que se para n impar, n^2 - 1 é divisivel por 8.. uma outra demonstracao seria: n = 2k+1 ... n^2 - 1 = 4k^2 + 4k = 4(k^2 + k) temos que mostrar que k^2 + k = 0 (mod2) se k = 0 (mod2), entao: k^2 = 0(mod2) ... k^2+k = 0(mod2) se k = 1 (mod2), entao: k^2 = 1(mod2) ... k^2+k = 2 = 0(mod2) tambem esta provado.. outro jeito ainda seria: se k é par, k^2 é par, k^2 + k é par, logo, é divisivel por 2... se k é impar, k^2 é impar, k^2 + k é par (a soma de 2 impares é sempre par), logo, é divisivel por 2 [esse demonstracao eh analoga a anterior] abracos, Salhab - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Saturday, March 24, 2007 2:19 PM Subject: [obm-l] Congruência modular Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna
[obm-l] Re: [obm-l] Re: [obm-l] Congruência modular
Olá, vamos testar para n=1 ... 1^2 - 1 = 0 ok para n=3 ... 3^2 - 1 = 8 ok suponha que vale para n ímpar, entao, vamos mostrar que vale para n+2 (proximo impar) (n+2)^2 - 1 = n^2 + 4n + 4 - 1 = (n^2 -1) + 4n + 4 .. opa, por hipotese: n^2 - 1 é divisivel por 8, entao temos que mostrar que 4n+4 tambem é... de fato: 4n+4 = 4(n+1) ... como n é impar, n+1 é par, logo, 4(n+1) é divisivel por 8... e esta provado por inducao abracos, Salhab - Original Message - From: R Parenti To: obm-l@mat.puc-rio.br Sent: Saturday, March 24, 2007 3:18 PM Subject: [obm-l] Re: [obm-l] Congruência modular dá para fazer essa questão por PIF foi mal, eu nao vou fazer pq eu já tou de saída, mai essa questão é feita por isso tipo, se o caso( n ) acontece, logo o caso ( n+1 ), ocorre, ok?? abraços - Original Message - From: Bruna Carvalho To: obm-l@mat.puc-rio.br Sent: Saturday, March 24, 2007 2:19 PM Subject: [obm-l] Congruência modular Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna
Re: [obm-l] Congruência modular
^n^2-1=(2t+1)^2-1 =4t^2+4t=4t(t+1) logo 4=4mod0 t*(t+1)=0mod2 logo 4t(t+1)=0mod8 On 3/24/07, Bruna Carvalho [EMAIL PROTECTED] wrote: Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna
Re: [obm-l] Congruência modular
Se n é ímpar, então n=1,3,5 ou 7(mod 8). Portanto n^2 -1=0(mod 8). Tertuliano. Bruna Carvalho [EMAIL PROTECTED] escreveu:Se n é ímpar, prove que n²-1 é divisível por 8. Eu quero aprender como faz esse tipo de questão por congruência, alguém pode me dar uma ajudinha. bjos. -- Bjos, Bruna __ Fale com seus amigos de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com/
