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 <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.
