Question

Aplicando o Teorema de Euler, encontre o resto da divisão de:

3^100 por 37

Answer 1

Queremos calcular o resto da divisão de 3¹⁰⁰ por 37.

O Teorema de Euler diz que:

Se o mdc(a,m) = 1, então $a^{\phi(m)} \equiv 1(mod(m))$.

Como mdc(3,37) = 1, e φ(37) = 36 (pois 37 é primo), então:

3³⁶ ≡ 1 (mod 37).

Sabemos que 100 = 2.36 + 28.

Então:

$3^{100}=3^{2.36+28}=(3^{36})^2.3^{28} \equiv 1^2.3^{28} \equiv 3^{28}$

Além disso, temos que:

3⁷ ≡ 4 (mod 37) → 3⁷ deixa resto 4 na divisão por 37.

Como 28 = 4.7, temos que:

$3^{100}\equiv 3^{4.7} = (3^7)^4 \equiv 4^4 = 256 \equiv 36 (mod37)$

Ou seja,

$3^{100} \equiv 34 (mod37)$

Portanto, podemos concluir que o resto da divisão de 3¹⁰⁰ por 37 é 34.

Answer 2

A partir dos dados fornecidos pelo problema e dos devidos cálculos que faremos, podemos concluir que o resto da divisão é igual a 34. E para chegar a essa conclusão tivemos que usar a fórmula do teorema de Euler.

E qual é essa fórmula?

A fórmula do teorema de Euler é:

$\large \boxed{\boxed{ \rm a ^{\phi (m)}\equiv 1(mod ~ m)}}$

Para usar esta fórmula devemos saber que $a \in \mathbb{Z}$ e também que m > 1 e o máximo divisor comum (mdc) de (a,m) é igual a 1, se satisfazendo essas condições, é possível aplicar o teorema de Euler.

Conhecendo esta fórmula, vamos calcular o resíduo que o problema nos pede.

O problema menciona que devemos aplicar o teorema de Euler para encontrar o resto da divisão do número $3^{100}$ pelo número 37.

No início do problema satisfazemos duas coisas, estas são que o número a é um inteiro e que m é um número maior que 1, então o que resta é provar que o mdc é igual a 1.

Como 3 e 37 são números primos, não podemos fatorar esses dois números, então o mdc é igual a 1, então como já atendemos todas as condições, aplicamos o teorema de Euler para calcular o resto da divisão.

$\rm 3 ^{\phi (37)}\equiv 1(mod ~ 37)$

Para executar esta expressão vamos primeiro calcular a função φ de Euler, para calcular a função φ de Euler para um número primo não tão grande usaremos a fórmula:

$\rm \phi (p) = p - 1$

• Onde p pertence aos números primos.

Aplicando esta fórmula para calcular a função φ de Euler de 37, obtemos o resultado:

$\rm \phi (37) = 37- 1=36$

Assim, podemos concluir que: $\rm 3^{36}\equiv 1(mod ~ 37)$

Então, sabendo disso, devemos saber que 100 pode ser igual a 2*36+28, então $3^{100}$ pode ser escrito como $3^{2\cdot 36+28}$. Pelas leis dos expoentes, esta expressão pode ser escrita como:

$\left(3^{36}\right)^2\cdot 3^{28}$

A partir do resultado da expressão que obtivemos anteriormente, podemos dizer que esta expressão é congruente a:

$\left(3^{36}\right)^2\cdot 3^{28}\equiv \left(1\right)^2 \cdot 3^{28}=\\ \\ =1\cdot 3^{28}=3^{28}$

Como $3^{28}$ ainda é um número muito grande, então vamos dividi-lo novamente, esse expoente pode ser igual a:

$\left(3^{7}\right)^4$

Vamos encontrar o resto de $3^7$ ou 2.187 quando dividido pelo número 37. $\rm 3^{7}\equiv 4(mod ~ 37)$

• O resto da divisão $3^7$ e 37 é igual a 4, então a expressão que fatoramos é congruente a:

$\left(3^7\right)^4\equiv \left(4\right)^4=\\ =256$

Esta expressão tem o número 34 como resto, você pode verificar isso dividindo o 256 pelo número 37. $\rm 4^{4}\equiv 34(mod ~ 37)$

Então:

$\large \boxed{\boxed{ \rm 3 ^{100}\equiv 34(mod ~ 37)}}$

ヘ( ^o^)ノ＼(^_^ ) Feitos os cálculos, concluímos que o resto da divisão é igual a 34

Você pode ver mais sobre o assunto de aritmética modular nos seguintes links:

• https://brainly.com.br/tarefa/52645887
• https://brainly.com.br/tarefa/13317193
• https://brainly.com.br/tarefa/30899224

Bons estudos e espero que te ajude :D