[obm-l] Re: [obm-l] Outro de congruência módulo m.
Uma ideia é calcular isto módulo 8 e módulo 125. Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- /**/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
272 algarismos. Em 3 de maio de 2014 20:58, Pedro José petroc...@gmail.com escreveu: Boa noite! Já que foi resolvido. Aqui vai outra solução. Procurando o menor expoente x 0 que 7^x ≡ 1 mod 10. 7^1 ≡ 7 mod 10. 7^2 ≡ 9 mod 10. 7^3 ≡ 9*7 ≡ 3 mod 10. 7^4 ≡ 9*9 ≡ 1 mod 10. Se você conhecer função totiente de Euler. e ordem de a módulo m, onde mdc(a,m) =1 (que é o menor inteiro d 0 tal que a^d ≡ 1 mod m e é também o período mínimo do expoente para repetição das congruências 7^x mod m. Outra coisa é orda m divide a função totiente de Euler aplicada em m. como φ(10)= 4 só poderia ser para 1, 2 ou 4. Fica óbvio que seria 4, como achado por tentativas, anteriormente. Um outro macete para procurar é que quando achar o primeiro expoente que dê -1 o dobro desse expoente é orda m. No exemplo de tentativas o 9 ≡ -1 mod 10. Já podíamos ter inferido que ord7 10 =4. Outro macete. Quando for buscar a orda m no braço, use sempre o resultado anterior e multiplique por a para achar a próxima congruência. Verificando qual a congruência mod 100 de 7^4 temos: 7^4 ≡ 1 mod 100. Então temos que ord7 10 = ord7 100 = 4. Vamos verificar para mod1000, temos: 7^4 ≡ 801 mod 1000. Para um número ter resto 1 quando se divide por 1000, necessita ter resto 1 quando o dividimos por 100, como 4 é ord7 100 e a ordem é o período mínimo, ord7 1000 será um múltiplo de 4. Por tentativas: 7^4 ≡ 401 mod 1000. 7^8 ≡ 401^2 ≡ 801≡ -199 mod 1000. 7^12 ≡ 401*-199 ≡ 201 mod 1000. 7^16 ≡ (-199)^2 ≡ 601 mod 1000. 7^20 ≡ 601*401 ≡ 1 mod 1000. Usando a função totiente temos: φ(1000)= 400, logo os divisores comuns de 400 e que sejam múltiplos de 4 são: 4, 8, 16, 20.40, 80, 100, 200 e 400. Dessa feita não ajudou muito. Só evitaria calcular o 7^12. como = 499*20 + 19 temos que 7^ = 7^(20*499 + 19) = (7^20)^499*7^19 ≡ 1^499*7^19 ≡ 7^19 mod 1000. 7^19 ≡ 7^16*7^3 ≡ 601*343 ≡ 143 mod 1000. Portanto os últimos três algarismos são 1, 4 e 3 nessa ordem. *Problema proposto: Seja um número formado apenas de algarismos 4, ou seja, 444...444; quantos algarismos no mínimo são necessários para que esse número seja divísivel* *por *289? Saudações PJMS Em 3 de maio de 2014 02:40, profc...@yahoo.com.br profc...@yahoo.com.brescreveu: Nossa bem q tava facil demais. Desculpem, n vi q eram os 3 ultimos. E obrigado pela dica do endereco. Tb vou dar uma lida. Enviado do Yahoo Mail no Androidhttps://br.overview.mail.yahoo.com/mobile/?.src=Android -- * From: * Douglas Oliveira de Lima profdouglaso.del...@gmail.com; * To: * obm-l@mat.puc-rio.br; * Subject: * [obm-l] Re: [obm-l] Outro de congruência módulo m. * Sent: * Fri, May 2, 2014 6:16:48 PM Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�us e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Boa tarde! São 272 algarismos. Correto. Saudações, PJMS Em 4 de maio de 2014 14:43, Douglas Oliveira de Lima profdouglaso.del...@gmail.com escreveu: 272 algarismos. Em 3 de maio de 2014 20:58, Pedro José petroc...@gmail.com escreveu: Boa noite! Já que foi resolvido. Aqui vai outra solução. Procurando o menor expoente x 0 que 7^x ≡ 1 mod 10. 7^1 ≡ 7 mod 10. 7^2 ≡ 9 mod 10. 7^3 ≡ 9*7 ≡ 3 mod 10. 7^4 ≡ 9*9 ≡ 1 mod 10. Se você conhecer função totiente de Euler. e ordem de a módulo m, onde mdc(a,m) =1 (que é o menor inteiro d 0 tal que a^d ≡ 1 mod m e é também o período mínimo do expoente para repetição das congruências 7^x mod m. Outra coisa é orda m divide a função totiente de Euler aplicada em m. como φ(10)= 4 só poderia ser para 1, 2 ou 4. Fica óbvio que seria 4, como achado por tentativas, anteriormente. Um outro macete para procurar é que quando achar o primeiro expoente que dê -1 o dobro desse expoente é orda m. No exemplo de tentativas o 9 ≡ -1 mod 10. Já podíamos ter inferido que ord7 10 =4. Outro macete. Quando for buscar a orda m no braço, use sempre o resultado anterior e multiplique por a para achar a próxima congruência. Verificando qual a congruência mod 100 de 7^4 temos: 7^4 ≡ 1 mod 100. Então temos que ord7 10 = ord7 100 = 4. Vamos verificar para mod1000, temos: 7^4 ≡ 801 mod 1000. Para um número ter resto 1 quando se divide por 1000, necessita ter resto 1 quando o dividimos por 100, como 4 é ord7 100 e a ordem é o período mínimo, ord7 1000 será um múltiplo de 4. Por tentativas: 7^4 ≡ 401 mod 1000. 7^8 ≡ 401^2 ≡ 801≡ -199 mod 1000. 7^12 ≡ 401*-199 ≡ 201 mod 1000. 7^16 ≡ (-199)^2 ≡ 601 mod 1000. 7^20 ≡ 601*401 ≡ 1 mod 1000. Usando a função totiente temos: φ(1000)= 400, logo os divisores comuns de 400 e que sejam múltiplos de 4 são: 4, 8, 16, 20.40, 80, 100, 200 e 400. Dessa feita não ajudou muito. Só evitaria calcular o 7^12. como = 499*20 + 19 temos que 7^ = 7^(20*499 + 19) = (7^20)^499*7^19 ≡ 1^499*7^19 ≡ 7^19 mod 1000. 7^19 ≡ 7^16*7^3 ≡ 601*343 ≡ 143 mod 1000. Portanto os últimos três algarismos são 1, 4 e 3 nessa ordem. *Problema proposto: Seja um número formado apenas de algarismos 4, ou seja, 444...444; quantos algarismos no mínimo são necessários para que esse número seja divísivel* *por *289? Saudações PJMS Em 3 de maio de 2014 02:40, profc...@yahoo.com.br profc...@yahoo.com.brescreveu: Nossa bem q tava facil demais. Desculpem, n vi q eram os 3 ultimos. E obrigado pela dica do endereco. Tb vou dar uma lida. Enviado do Yahoo Mail no Androidhttps://br.overview.mail.yahoo.com/mobile/?.src=Android -- * From: * Douglas Oliveira de Lima profdouglaso.del...@gmail.com; * To: * obm-l@mat.puc-rio.br; * Subject: * [obm-l] Re: [obm-l] Outro de congruência módulo m. * Sent: * Fri, May 2, 2014 6:16:48 PM Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�us e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Nossa bem q tava facil demais. Desculpem, n vi q eram os 3 ultimos. E obrigado pela dica do endereco. Tb vou dar uma lida. Enviado do Yahoo Mail no Android -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Boa noite! Já que foi resolvido. Aqui vai outra solução. Procurando o menor expoente x 0 que 7^x ≡ 1 mod 10. 7^1 ≡ 7 mod 10. 7^2 ≡ 9 mod 10. 7^3 ≡ 9*7 ≡ 3 mod 10. 7^4 ≡ 9*9 ≡ 1 mod 10. Se você conhecer função totiente de Euler. e ordem de a módulo m, onde mdc(a,m) =1 (que é o menor inteiro d 0 tal que a^d ≡ 1 mod m e é também o período mínimo do expoente para repetição das congruências 7^x mod m. Outra coisa é orda m divide a função totiente de Euler aplicada em m. como φ(10)= 4 só poderia ser para 1, 2 ou 4. Fica óbvio que seria 4, como achado por tentativas, anteriormente. Um outro macete para procurar é que quando achar o primeiro expoente que dê -1 o dobro desse expoente é orda m. No exemplo de tentativas o 9 ≡ -1 mod 10. Já podíamos ter inferido que ord7 10 =4. Outro macete. Quando for buscar a orda m no braço, use sempre o resultado anterior e multiplique por a para achar a próxima congruência. Verificando qual a congruência mod 100 de 7^4 temos: 7^4 ≡ 1 mod 100. Então temos que ord7 10 = ord7 100 = 4. Vamos verificar para mod1000, temos: 7^4 ≡ 801 mod 1000. Para um número ter resto 1 quando se divide por 1000, necessita ter resto 1 quando o dividimos por 100, como 4 é ord7 100 e a ordem é o período mínimo, ord7 1000 será um múltiplo de 4. Por tentativas: 7^4 ≡ 401 mod 1000. 7^8 ≡ 401^2 ≡ 801≡ -199 mod 1000. 7^12 ≡ 401*-199 ≡ 201 mod 1000. 7^16 ≡ (-199)^2 ≡ 601 mod 1000. 7^20 ≡ 601*401 ≡ 1 mod 1000. Usando a função totiente temos: φ(1000)= 400, logo os divisores comuns de 400 e que sejam múltiplos de 4 são: 4, 8, 16, 20.40, 80, 100, 200 e 400. Dessa feita não ajudou muito. Só evitaria calcular o 7^12. como = 499*20 + 19 temos que 7^ = 7^(20*499 + 19) = (7^20)^499*7^19 ≡ 1^499*7^19 ≡ 7^19 mod 1000. 7^19 ≡ 7^16*7^3 ≡ 601*343 ≡ 143 mod 1000. Portanto os últimos três algarismos são 1, 4 e 3 nessa ordem. *Problema proposto: Seja um número formado apenas de algarismos 4, ou seja, 444...444; quantos algarismos no mínimo são necessários para que esse número seja divísivel* *por *289? Saudações PJMS Em 3 de maio de 2014 02:40, profc...@yahoo.com.br profc...@yahoo.com.brescreveu: Nossa bem q tava facil demais. Desculpem, n vi q eram os 3 ultimos. E obrigado pela dica do endereco. Tb vou dar uma lida. Enviado do Yahoo Mail no Androidhttps://br.overview.mail.yahoo.com/mobile/?.src=Android -- * From: * Douglas Oliveira de Lima profdouglaso.del...@gmail.com; * To: * obm-l@mat.puc-rio.br; * Subject: * [obm-l] Re: [obm-l] Outro de congruência módulo m. * Sent: * Fri, May 2, 2014 6:16:48 PM Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�us e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Outro de congruência módulo m.
Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Boa tarde! Use congruência módulo 1000. Os últimos três algarismos de um número (logicamente com 3 ou mais dígitos) são os mesmos que aparecem no resto da divisão por mil (congruência módulo m). Podemos afirmar que se (a^k) ≡1 mod m (a^k)^n ≡ (a^k) ≡1 mod m, a,k,n,m *Ɛ Z* e k,m 0 Logicamente se a ≡ x mod m^3, a ≡ x modm^2, a ≡ x mod m Basta ver que a ≡ x mod m^3 0xm^3 == Existe k *Ɛ Z | *a* = *k*m^3 + x* ==* a= (k*m)*m^2 + x Pelo fechamento da multiplicação em Z*, *temos que: a ≡ x modm^2. Com o mesmo raciocínio você chega nas potências menores. Você tem que pensar assim adoraria saber qual potência, de 7 dá congruente a 1 mod 1000. Seja a^b ≡1 mod 1000. Usando divisão Euclidiana temos que 999 = k*b+r, k,b,r *Ɛ Z *e 0rb*.*Portanto podemos escrever 7^999= (7^b)^k*7^r=7^r *. * Como 7^b ≡1 mod 1000, por hipótese temos que (7^b)^k ≡ (1)^k ≡1 mod 1000. Logo 7^999 ≡ 7^r mod 1000. se tivermos sorte de achar um b pequeno temos que r b, facilita. Primeiramente vá fazendo a potência de 7 até que você ache uma congruente a 1 mod 10. (Se você conhecer ordem, teorema de Euler-Fermat e função totiente de Euler fica mais fácil achar esse valor). Caso contrário mão na massa (i) 7^1 , 7^2, 7^3 7^4, 7^5 até que você encontre uma potência congruente a 1 mod 10. Digamos x. (ii) Verifique se ela congruente a 1 mod 100. Caso seja pule o passo (iii) (iii) Procure a menor potência múltipla de x (depois explicarei por que) que é congruente a 1 mod 100. 7^(2*x), 7^(3*x),7^(4*x) . Digamos y (iv) Verifique se ela já é congruente a 1 mod 1000. Caso seja pule o passo (v) (v) Procure a menor potência múltipla de y (depois explicarei por que, como já dito) que é congruente a 1 mod 100. 7^(2*x), 7^(3*x),7^(4*x) . Digamos z. (vi) Calcule o resto de 999 por z e ache a congruência a mod 1000, onde 0 a 1000. É essa a resposta. É óbvio que se (a^k) ≡1 mod m (a^k)^n ≡ (a^k) ≡1 mod m, a,k,n,m *Ɛ Z* e k,m 0*, * como (a^k)^n = a^(k*n), temos que toda potência de k também é côngruo mod m. Seja s a menor potência de a | a^s ≡1 mod m. Se a^x ≡1 mod m == x é mútiplo de s. Vamos mostrar por absurdo Suponha que exista x e x não seja múltiplo de m. Para m 1, se x não é múltiplo de m == Existe k *Ɛ Z | *k*s x ( k+1)*s Como (k+1)*s - k*s= s == x - k*s s, pois x (k+1)*s. a^x ≡1 mod m== a^(k*s + (x-k*s)) ≡1 mod m . Como a^(k*s + (x-k*s))= a^(k*s) * a^(x-k*s) == a^(k*s) * a^(x-k*s) ≡1 mod m Como a (k*s) ≡1 mod m == a^(x-k*s) ≡1 mod m == Existe t = x-k*s | a^t ≡1 mod m Porém t é menor que s, que por suposição é mínimo, absurdo. Dica as potências podem ficar tão grandes que nem as planilhas de Excel suportem. Por exemplo 7^x ≡ 801 mod m 7^(2x) ≡ 801^2 mod m (outra dica se o número for maior que a metade de m, use o complemento de (801- m), no caso m =1000, vale a pena. Lembre que as classes de equivalência conservam, adição, multiplicação e potenciação. Se subtrair m, o resultado permanece na mesma classe de equivalência. 7^2x ≡ 601 mod m 7^3x≡ (601*801) mod m Note que assim você estará multiplicando sempre dois números com módulos inferiores a 1000, o que qualquer lápis e caderno suportam, quanto mais o excel. Mas será que o excel suporta achar o mod 100 de 7^24 por exemplo. Agora mais uma dica, a melhor forma de agradecer é aprender. Você está precisando de estudar teoria dos números. Tem um artigo muito bom: http://www.icmc.usp.br/pessoas/etengan/imersao/imersao.pdf, vale a pena estudá-lo e um artigo vai puxando o outro. Espero que você consiga resolver. Saudações, PJMS Em 2 de maio de 2014 15:16, Douglas Oliveira de Lima profdouglaso.del...@gmail.com escreveu: Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Outro de congruência módulo m.
Vamos finalizar, Os dois últimos são periódicos sempre, 01, 49, 43, 07 , entao 7^(4k) termina em 01, 7^(4k+1) termina em 07, 7^(4k+2) termina em 49 e 7^(4k+3) termina em 43, como que nos interessa, e =4t+3 possui os dois finais 43, e como te falei o algarismo das centenas na jogada são periódicos ex: 7^3= 343 7^7=.543 7^11=...743 7^15=...943 7^19=...143 7^23=...343 Agora ja da pra perceber que o algarismo das centenas termina em 1,3,5,7ou 9(período 5) Considerando o 7^3 como o primeiro termo de uma seqüência onde se deseja o final de 7^ , a seqüência (3,7,11,15,19,...,) possui (-3)/4 +1 termos , ou seja , 2500 , 2500/5 da resto 0 significa que os três últimos são 143. Abracos do Douglas Oliveira. Em 2 de maio de 2014 15:16, Douglas Oliveira de Lima profdouglaso.del...@gmail.com escreveu: Entao percebi que os dois ultimos digitos das potencias de 7 sao periodicos e sempre terminam em 01, 49, 43, 07, assim os digitos das centenas com certeza devem ser periodicos tambem. Verifique!! Abracos do Douglas Oliveira Em 30 de abril de 2014 16:38, ruymat...@ig.com.br escreveu: Quais os três últimos dígitos de 7^?. Sempre agreço muito quem resolve sempre o faço antecipadamente. Obrigado. Abraço. R.O. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Entao To meio enferrujado. Nao pode ser assim?? 7^9 = (7^3)3=(243)^3=(3)^3 mod10=7mod10 7^10=-1 mod10 7^ = (7^9)^=(7)^=7^(1110+1)=7.(7^10)^111=7.(-1)=-7=3 (mod 10). Enviado do Yahoo Mail no Android -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Outro de congruência módulo m.
Oi profcabi, O que fizeste é para calcular o último dígito, ok ? Pacini Em 2 de maio de 2014 21:36, profc...@yahoo.com.br profc...@yahoo.com.brescreveu: Entao To meio enferrujado. Nao pode ser assim?? 7^9 = (7^3)3=(243)^3=(3)^3 mod10=7mod10 7^10=-1 mod10 7^ = (7^9)^=(7)^=7^(1110+1)=7.(7^10)^111=7.(-1)=-7=3 (mod 10). Enviado do Yahoo Mail no Androidhttps://br.overview.mail.yahoo.com/mobile/?.src=Android -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
