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 saulo.nil...@gmail.com
escreveu:
4 714 714714 fica repetindo na soma dos diigitos.
2014-11-23 22:00 GMT-02:00 Iuri Rezende Souza iuri_...@hotmail.com:
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 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.
--
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.
