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 9999999...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 <[email protected]> escreveu: > 4 714 714714 ....fica repetindo na soma dos diigitos. > 2014-11-23 22:00 GMT-02:00 Iuri Rezende Souza <[email protected]>: > > 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 <[email protected] >> > 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. > -- /**************************************/ 神が祝福 Torres -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
