Achar o resto do divinaō de 3^100 por 34.

Para encontrar o resto da divisão de \( 3^{100} \) por 34, podemos usar o pequeno teorema de Fermat. O teorema afirma que se \( p \) é um número primo e \( a \) é um inteiro não divisível por \( p \), então:<br /><br />\[ a^{p-1} \equiv 1 \pmod{p} \]<br /><br />No entanto, como 34 não é primo, precisamos usar outra abordagem. Vamos usar o Teorema Chinês dos Restos (TCR).<br /><br />Primeiro, fatoramos 34 em seus fatores primos:<br />\[ 34 = 2 \times 17 \]<br /><br />Agora, encontramos os restos de \( 3^{100} \) módulo 2 e módulo 17.<br /><br />1. \( 3^{100} \mod 2 \):<br />Qualquer potência de 3 é ímpar, então:<br />\[ 3^{100} \equiv 1 \pmod{2} \]<br /><br />2. \( 3^{100} \mod 17 \):<br />Usamos o pequeno teorema de Fermat, pois 17 é primo:<br />\[ 3^{16} \equiv 1 \pmod{17} \]<br />Então, podemos escrever \( 3^{100} \) como:<br />\[ 3^{100} = (3^{16})^6 \cdot 3^4 \]<br />\[ (3^{16})^6 \equiv 1^6 \equiv 1 \pmod{17} \]<br />Portanto:<br />\[ 3^{100} \equiv 3^4 \pmod{17} \]<br />Calculamos \( 3^4 \):<br />\[ 3^4 = 81 \]<br />E agora encontramos o resto de 81 dividido por 17:<br />\[ 81 \div 17 = 4 \text{ com resto } 13 \]<br />Portanto:<br />\[ 3^{100} \equiv 13 \pmod{17} \]<br /><br />Agora temos dois sistemas de congruências:<br />\[ x \equiv 1 \pmod{2} \]<br />\[ x \equiv 13 \pmod{17} \]<br /><br />Usando o Teorema Chinês dos Restos, combinamos essas duas congruências. Como 2 e 17 são coprimos, existe uma solução única módulo \( 34 \).<br /><br />A solução é:<br />\[ x \equiv 13 \pmod{34} \]<br /><br />Portanto, o resto da divisão de \( 3^{100} \) por 34 é \( 13 \).