[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Potenciação
A resolução MESMO é mais complicada que isso. Se s(n) é a soma dos dígitos de n, queremos s(s(s(31^31))). Por sorte, o problema já deu as somas dos dígitos. Então este número não terá uma soma dos dígitos maior que a de 999...99, o que dá 47*9=423. Logo, s(N)<=423 Dados todos os inteiros menores que 423, qual tem a maior soma de dígitos? Certamente é o 399, cuja soma dará 21: s(s(N))<=21 Dados todos os inteiros menores que 21, qual tem a maior soma de dígitos? Certamente é o 19, cuja soma dará 10: s(s(s(N)))<=10 Assim, magicamente, s(s(s(N))) tem apenas um dígito! Como s(N)=N mod 9, a resposta é a mesma que o resto da divisão de 31^31 por 9. E segue o que os colegas já mostraram! Em 28 de novembro de 2014 22:02, saulo nilson escreveu: > 4 714 714714 fica repetindo na soma dos diigitos. > 2014-11-23 22:00 GMT-02:00 Iuri Rezende Souza : > > Olá! >> >> A primeira congruência: >> >> Como 31 tem mesmo resto que 4 ao dividir por 9, 31*31*31*...*31 (n vezes) >> tem o mesmo resto que 4*4*4*...*4 (n vezes) ao dividir por 9. Logo, 31^31 = >> 4^31 (mod 9) >> >> A segunda congruência: >> >> Observe o que acontece com os restos (mod 9) ao multiplicar o 4 várias >> vezes. Temos a sequência 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, ..., que é >> periódica com período 3. Então basta olhar o resto do expoente (31) por 3. >> >> Outro modo de ver isso é qual potência de 4 tem resto 1 ao ser dividida >> por 9 (isso é possível, já que 4 e 9 são primos entre si). 4^3 é essa >> potência. Então podemos separar os termos do produto de 3 em 3. Observe que >> 4^31 = 4*4*4*4*4*...*4 = (4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*4 >> = ((4^3)^6)*4. Sabendo que 4^3 tem resto 1 ao ser dividido por 9, o resto >> desse número é igual a (1^6)*4 = 4. >> >> Mudando um pouco de problema, um exemplo disso em que podemos simplificar >> uma potência com aritmética modular é o critério da divisão por 9 na base >> decimal. O número com algarismos abcd é igual a a*10^3 + b*10^2 + c*10^1 + >> d*10^0. Observe que 10 deixa mesmo resto que 1 ao ser dividido por 9, ou, >> em outras palavras, 10 = 1 (mod 9). Assim, a*10^3 + b*10^2 + c*10^1 + >> d*10^0 = a*1^3 + b*1^2 + c*1^1 + d*1^0 (mod 9). Continuando, a*1^3 + b*1^2 >> + c*1^1 + d*1^0 = a+b+c+d (mod 9). Acho que isso já dá o que pensar sobre >> aritmética modular. >> >> Att, >> Iuri >> >> >> On 19-11-2014 12:16, Vanderlei Nemitz wrote: >> >> Muito obrigado! Confesso que não entendo muito disso, mas vou procurar o >> teorema e estudar. Uma parte que não entendi bem foi: >> >> Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além disso, a >> cada 3 potências de 4, o resto se repete. Como 31 = 1 (mod 3), temos que >> >> 31^31 = 4^31 = 4^1 = 4 (mod 9). >> >> Se puder esclarecer, agradeço muito! >> >> Um abraço! >> >> Em 18 de novembro de 2014 12:25, Iuri Rezende Souza > > escreveu: >> >>> Sim. >>> >>> A soma da soma da soma ... da soma dos algarismos de um número nos dá o >>> resto do número ao ser dividido por 9. >>> >>> 31 = 4 (mod 9), ou seja, 31 deixa o mesmo resto que 4 quando dividido >>> por 9. >>> >>> Observe o padrão do resto das potências de 4 divididas por 9: >>> 4^2 = 4*4 = 7 (mod 9) >>> 4^3 = 7*4 = 1 (mod 9) >>> 4^4 = 1*4 = 4 (mod 9) >>> >>> Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além disso, a >>> cada 3 potências de 4, o resto se repete. Como 31 = 1 (mod 3), temos que >>> >>> 31^31 = 4^31 = 4^1 = 4 (mod 9). >>> >>> PS: existe um resultado em teoria dos números que diz que se mdc(a, n) = >>> 1, o menor inteiro não-nulo t tal que a^t = 1 (mod n) divide o número >>> phi(n), onde phi(n) é o número de inteiros x menores que n tais que mdc(x, >>> n) = 1. Com esse resultado, não precisa procurar padrões: basta saber que >>> phi(9) = 6 e usar 31 = 1 (mod 6) a seu favor. >>> >>> >>> >>> On 18-11-2014 09:32, Vanderlei Nemitz wrote: >>> >>> Existe alguma maneira de resolver a questão a seguir sem precisar >>> enxergar um padrão, por meio de alguns exemplos? Mesmo que esse padrão >>> exista, não podemos garantir que irá permanecer. Gostaria de um método >>> geral. >>> >>> Obrigado! >>> >>> *O número 31^31 é um inteiro que quando escrito na notação decimal >>> possui 47 **algarismos. Se a soma destes 47 algarismos é S e a soma dos >>> algarismos de S **é T então a soma dos algarismos de T é igual a: * >>> *a) 4 * >>> *b) 5 * >>> *c) 6* >>> *d) 7 * >>> *e) 8* >>> >>> -- >>> 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. >> > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- /***
[obm-l] Re: [obm-l] Re: [obm-l] Potenciação
4 714 714714 fica repetindo na soma dos diigitos. 2014-11-23 22:00 GMT-02:00 Iuri Rezende Souza : > Olá! > > A primeira congruência: > > Como 31 tem mesmo resto que 4 ao dividir por 9, 31*31*31*...*31 (n vezes) > tem o mesmo resto que 4*4*4*...*4 (n vezes) ao dividir por 9. Logo, 31^31 = > 4^31 (mod 9) > > A segunda congruência: > > Observe o que acontece com os restos (mod 9) ao multiplicar o 4 várias > vezes. Temos a sequência 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, ..., que é > periódica com período 3. Então basta olhar o resto do expoente (31) por 3. > > Outro modo de ver isso é qual potência de 4 tem resto 1 ao ser dividida > por 9 (isso é possível, já que 4 e 9 são primos entre si). 4^3 é essa > potência. Então podemos separar os termos do produto de 3 em 3. Observe que > 4^31 = 4*4*4*4*4*...*4 = (4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*4 > = ((4^3)^6)*4. Sabendo que 4^3 tem resto 1 ao ser dividido por 9, o resto > desse número é igual a (1^6)*4 = 4. > > Mudando um pouco de problema, um exemplo disso em que podemos simplificar > uma potência com aritmética modular é o critério da divisão por 9 na base > decimal. O número com algarismos abcd é igual a a*10^3 + b*10^2 + c*10^1 + > d*10^0. Observe que 10 deixa mesmo resto que 1 ao ser dividido por 9, ou, > em outras palavras, 10 = 1 (mod 9). Assim, a*10^3 + b*10^2 + c*10^1 + > d*10^0 = a*1^3 + b*1^2 + c*1^1 + d*1^0 (mod 9). Continuando, a*1^3 + b*1^2 > + c*1^1 + d*1^0 = a+b+c+d (mod 9). Acho que isso já dá o que pensar sobre > aritmética modular. > > Att, > Iuri > > > On 19-11-2014 12:16, Vanderlei Nemitz wrote: > > Muito obrigado! Confesso que não entendo muito disso, mas vou procurar o > teorema e estudar. Uma parte que não entendi bem foi: > > Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além disso, a > cada 3 potências de 4, o resto se repete. Como 31 = 1 (mod 3), temos que > > 31^31 = 4^31 = 4^1 = 4 (mod 9). > > Se puder esclarecer, agradeço muito! > > Um abraço! > > Em 18 de novembro de 2014 12:25, Iuri Rezende Souza > escreveu: > >> Sim. >> >> A soma da soma da soma ... da soma dos algarismos de um número nos dá o >> resto do número ao ser dividido por 9. >> >> 31 = 4 (mod 9), ou seja, 31 deixa o mesmo resto que 4 quando dividido por >> 9. >> >> Observe o padrão do resto das potências de 4 divididas por 9: >> 4^2 = 4*4 = 7 (mod 9) >> 4^3 = 7*4 = 1 (mod 9) >> 4^4 = 1*4 = 4 (mod 9) >> >> Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além disso, a >> cada 3 potências de 4, o resto se repete. Como 31 = 1 (mod 3), temos que >> >> 31^31 = 4^31 = 4^1 = 4 (mod 9). >> >> PS: existe um resultado em teoria dos números que diz que se mdc(a, n) = >> 1, o menor inteiro não-nulo t tal que a^t = 1 (mod n) divide o número >> phi(n), onde phi(n) é o número de inteiros x menores que n tais que mdc(x, >> n) = 1. Com esse resultado, não precisa procurar padrões: basta saber que >> phi(9) = 6 e usar 31 = 1 (mod 6) a seu favor. >> >> >> >> On 18-11-2014 09:32, Vanderlei Nemitz wrote: >> >> Existe alguma maneira de resolver a questão a seguir sem precisar >> enxergar um padrão, por meio de alguns exemplos? Mesmo que esse padrão >> exista, não podemos garantir que irá permanecer. Gostaria de um método >> geral. >> >> Obrigado! >> >> *O número 31^31 é um inteiro que quando escrito na notação decimal possui >> 47 **algarismos. Se a soma destes 47 algarismos é S e a soma dos >> algarismos de S **é T então a soma dos algarismos de T é igual a: * >> *a) 4 * >> *b) 5 * >> *c) 6* >> *d) 7 * >> *e) 8* >> >> -- >> 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. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Re: [obm-l] Potenciação
Olá! A primeira congruência: Como 31 tem mesmo resto que 4 ao dividir por 9, 31*31*31*...*31 (n vezes) tem o mesmo resto que 4*4*4*...*4 (n vezes) ao dividir por 9. Logo, 31^31 = 4^31 (mod 9) A segunda congruência: Observe o que acontece com os restos (mod 9) ao multiplicar o 4 várias vezes. Temos a sequência 4, 7, 1, 4, 7, 1, 4, 7, 1, 4, 7, 1, ..., que é periódica com período 3. Então basta olhar o resto do expoente (31) por 3. Outro modo de ver isso é qual potência de 4 tem resto 1 ao ser dividida por 9 (isso é possível, já que 4 e 9 são primos entre si). 4^3 é essa potência. Então podemos separar os termos do produto de 3 em 3. Observe que 4^31 = 4*4*4*4*4*...*4 = (4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*(4*4*4)*4 = ((4^3)^6)*4. Sabendo que 4^3 tem resto 1 ao ser dividido por 9, o resto desse número é igual a (1^6)*4 = 4. Mudando um pouco de problema, um exemplo disso em que podemos simplificar uma potência com aritmética modular é o critério da divisão por 9 na base decimal. O número com algarismos abcd é igual a a*10^3 + b*10^2 + c*10^1 + d*10^0. Observe que 10 deixa mesmo resto que 1 ao ser dividido por 9, ou, em outras palavras, 10 = 1 (mod 9). Assim, a*10^3 + b*10^2 + c*10^1 + d*10^0 = a*1^3 + b*1^2 + c*1^1 + d*1^0 (mod 9). Continuando, a*1^3 + b*1^2 + c*1^1 + d*1^0 = a+b+c+d (mod 9). Acho que isso já dá o que pensar sobre aritmética modular. Att, Iuri On 19-11-2014 12:16, Vanderlei Nemitz wrote: > Muito obrigado! Confesso que não entendo muito disso, mas vou procurar > o teorema e estudar. Uma parte que não entendi bem foi: > > Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além disso, > a cada 3 potências de 4, o resto se repete. Como 31 = 1 (mod 3), temos que > > 31^31 = 4^31 = 4^1 = 4 (mod 9). > > Se puder esclarecer, agradeço muito! > > Um abraço! > > Em 18 de novembro de 2014 12:25, Iuri Rezende Souza > mailto:iuri_...@hotmail.com>> escreveu: > > Sim. > > A soma da soma da soma ... da soma dos algarismos de um número nos > dá o resto do número ao ser dividido por 9. > > 31 = 4 (mod 9), ou seja, 31 deixa o mesmo resto que 4 quando > dividido por 9. > > Observe o padrão do resto das potências de 4 divididas por 9: > 4^2 = 4*4 = 7 (mod 9) > 4^3 = 7*4 = 1 (mod 9) > 4^4 = 1*4 = 4 (mod 9) > > Observa-se que chega-se a 1 logo após a 3ª potência do 4. Além > disso, a cada 3 potências de 4, o resto se repete. Como 31 = 1 > (mod 3), temos que > > 31^31 = 4^31 = 4^1 = 4 (mod 9). > > PS: existe um resultado em teoria dos números que diz que se > mdc(a, n) = 1, o menor inteiro não-nulo t tal que a^t = 1 (mod n) > divide o número phi(n), onde phi(n) é o número de inteiros x > menores que n tais que mdc(x, n) = 1. Com esse resultado, não > precisa procurar padrões: basta saber que phi(9) = 6 e usar 31 = 1 > (mod 6) a seu favor. > > > > On 18-11-2014 09:32, Vanderlei Nemitz wrote: >> Existe alguma maneira de resolver a questão a seguir sem precisar >> enxergar um padrão, por meio de alguns exemplos? Mesmo que esse >> padrão exista, não podemos garantir que irá permanecer. Gostaria >> de um método geral. >> >> Obrigado! >> >> *O número 31^31 é um inteiro que quando escrito na notação >> decimal possui 47 **algarismos. Se a soma destes 47 algarismos é >> S e a soma dos algarismos de S **é T então a soma dos algarismos >> de T é igual a: * >> *a) 4 * >> *b) 5 * >> *c) 6* >> *d) 7 * >> *e) 8* >> >> -- >> 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.
