Melhor resposta
Primeiro, você precisa olhar para o módulo (ou o número pelo qual estamos tentando dividir). Nesse caso, é 1818. Em seguida, você insere 1818 na função de totiente de Euler para obter ϕ (18) ϕ (18). Em particular, para todos os inteiros nn, temos
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
onde o produto atravessa todos os fatores primos únicos de nn. Portanto, neste caso,
ϕ (18) = (18) (1/2) (2/3) = 6 (18) = (18) (1/2) (2/3) = 6.
Ok, então a próxima etapa é teorema de Euler “, que diz que para qualquer outro inteiro aa que seja relativamente primo a nn, temos que aa elevado à potência ϕ (n) ϕ (n) deixa um resto de 11 quando dividido por nn. Ou seja,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Visto que 1717 é de fato relativamente primo a 1818, sabemos que 176176 folhas um lembrete de 1. Isso significa que podemos continuar dividindo 176176 de 1720017200 sem alterar o restante. Outra maneira de dizer isso é que 17 elevado a qualquer potência que “um múltiplo de 6 deixará um resto de 1. Portanto, no final, como 200 é 2 mais do que um múltiplo de 6, sabemos que
17200≡172 (mod18) .17200≡172 (mod18).
Isso torna o problema muito mais simples – estamos quase lá! Um atalho aqui para terminar o problema é perceber que 1717 deixa um resto de −1−1 quando dividido por 1818 (ou seja, 17≡ − 1 (mod18) 17≡ − 1 (mod18)), então 172172 deixa um resto de (- 1) 2 = 1. (- 1) 2 = 1.
Portanto, nossa resposta é 1 . Da próxima vez que você tiver um problema envolvendo o restante de grande potência, você pode usar esta bela solução generalizada e parecer inteligente ao mesmo tempo :). Se você nunca viu a notação modmod antes, consulte Aritmética modular .
PS Você pode ter ouvido falar de um caso especial deste teorema chamado de pequeno teorema de Fermat , que funciona quando você tem um módulo que “um número primo (não é o caso aqui). O teorema diz que para qualquer pp primo e o inteiro aa que não é múltiplo de pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Este é um truque interessante, mas é basicamente o mesmo que “s acima, pois ϕ (p) = p − 1ϕ (p) = p − 1 para qualquer pp primo. Esses tipos de perguntas tornam-se realmente simples se você entender o conceito de restos negativos . Sempre tente reduzir o dividendo para 1 ou -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Resposta
Fundamentos importantes necessários para resolver o problema :
Sabemos que o resto obtido quando r divide pq é o produto dos restos obtidos quando r divide pe qseparadamente. Isso é chamado de lema sobre restos. Você pode prová-lo pelo teorema da divisão de Euclides.
A solução
17 quando dividido por 18 deixa o resto -1 (é conveniente trabalhar com -1 do que 17)
Aplicando o lema do resto a 17 × 17 × 17 … × 17 (2.000 vezes) quando dividido por 18, o resto será obtido quando o os restos individuais são multiplicados, ou seja, -1 × -1 .. × -1 (2.000 vezes) que o resto é 1 \ blacksquare
Se fosse 17 elevado a algum número ímpar, o resto seria -1 ou 17 .