Teoria de números congruência

I) Qual o resto da divisão de 10^10 + 10^102+ + 10^10 100 por 7.
II) Pelo teorema de Fermat Ache o resto da dividão 2^9, 3^8, 5^13 por 7.
III) Pelo teorema de Euler encontre p resto da divisão 3^100 por 37

João Teixeira Teixeira
João Teixeira
perguntou há 2 meses

Sabe a resposta?

Ganhe 10 pts por resposta de qualidade
2 respostas
Professor Matheus Bohrer
Respondeu há 2 meses
João, você tem que proceder por aritmética modular!

I) Nota que 10 = 3 (mod 7), então (elevando ao quadrado a equacao e notando que 9 = 2 (mod 7), temos que 10² = 2 (mod 7); elevando os dois lados na quinta potencia e notando que 32 = 4 (mod 7), tu tem que 10^10 = 4 (mod 7).

Como 10^10 = 4 (mod 7), podemos elevar os dois lados ao quadrado e notar que 16 = 2 (mod 7), nos temos que 10^20 = 2 (mod 7); ainda, elevando essa ultima equacao na quinta potencia, tu obtem que 10^100 = 4 (mod 7).

Nota que até agora ja sabemos que 10^10 = 4 (mod 7), 10^2 = 2 (mod 7) e que 10^100 = 4 (mod 7). Multiplicando essas ultimas duas equacoes, obtemos 10^102 = 8 = 1 (mod 7). Assim, podemos fazer

10^10 + 10^102 + 10^10 = 4 + 1 + 4 = 9 = 2 (mod 7).

Procedendo de maneira análoga e usando o Teorema de Euler-Fermat, você resolve as outras duas. Caso precise de ajuda, dá um grito!

Abração!
Olá!

Para a resolução dos problemas, vamos lançar mão da congruência e de uma consideração.

CONGRUÊNCIA.

Se a, b e n pertencem a Z e a é congruente a b módulo n, então n divide a – b ou
a = b (mod n) => n | (a-b)

Teorema de Fermat: Seja a um inteiro positivo e p um primo, então
a^p = a (mod p)

CONSIDERAÇÃO:
10^10 + 10^102+ + 10^10 100 = 10^10 + 10^102+ 10^10.

RESOLUÇÃO.

1 - O resto da divisão de 10^10 + 10^102+ 10^10 por 7.

10 = 3 (mod 7) => *porque 10 – 3 = 7
10^2 = 3^2 (mod 7) *elevamos a igualdade ao quadrado
10^2 = 9 (mod 7)
10^2 = 2 (mod 7) * 9 = 2 (mod 7) *igualdade 1
[10^2]^5 = 2^5 (mod 7) *elevamos a igualdade a quinta potência
10^10 = 32 (mod 7)
10^10 = 4 (mod 7) *32 = 4 (mod 7) * igualdade 2
[10^10]^2 = 4^2 (mod 7) *elevamos a igualdade ao quadrado
10^20 = 16 (mod 7)
10^20 = 2 (mod 7) * 16 = 2 (mod 7)
[10^20]^5 = 2^5 (mod 7) *elevamos a igualdade a quinta potência
10^100 = 32 (mod 7)
10^100 = 4 (mod 7) *32 = 4 (mod 7) *igualdade 3
[10^100]*[10^2] = 4*2 (mod 7) * Multiplicamos a igualdade 1 pela 3
10^102 = 8 (mod 7)
10^102 = 1 (mod 7) *porque 8 = 1 (mod 7) * igualdade 4

Devido as igualdades 2 e 4 temos:

10^10 + 10^102 + 10^10 =
4 (mod 7) + 1 (mod 7) + 4 (mod 7) =>
10^10 + 10^102 + 10^10 = 2 (mod 7)

O resto da divisão de
10^10 + 10^102 + 10^10 por 7
é 2 porque
(10^10 + 10^102 + 10^10) – 2 = 7.

2 - Pelo teorema de Fermat Ache o resto da dividão 2^9, 3^8, 5^13 por 7.

2^9 por 7.

Seja r o resto.
2^9 – r = 7 =>
2^9 = r (mod 7) => *congruência
(2^2)*2^7 = r (mod 7) =>
(2^2)*2 = r (mod 7) => *porque 2^7 = 2 (mod 7) *Fermat
8 = r (mod 7) =>
8 – r = 7 *congruência.
r = 1

3^8 por 7.

Seja r o resto.
3^8 – r = 7 =>
3^8 = r (mod 7) => *congruência
(3)*3^7 = r (mod 7) =>
(3)*3 = r (mod 7) => *porque 3^7 = 3 (mod 7) *Fermat
9 = r (mod 7) =>
9 – r = 7 *congruência.
r = 2

5^13 por 7.
Seja r o resto.
5^13 – r = 7 =>
5^13 = r (mod 7) => *congruência
5*5^13 = 5*r (mod 7) => *multiplicamos por 5 a igualdade.
5^14 = 5*r (mod 7) =>
(5^7)*(5^7) = 5*r (mod 7) =>
(5)*(5) = 5*r (mod 7) => *porque 5^7 = 5 (mod 7) *Fermat
5 = r (mod 7) => *dividimos a igualdade por 5.
r = 5 (mod 7) => *propriedade simétrica da congruência
r = 5

3 - Pelo teorema de Euler encontre p resto da divisão 3^100 por 37.

Devemos encontrar p para
3^100 = p (mod 37) *Igualdade E.

3 = 3 (mod 37) =>
3^4 = 3^4 (mod 37) =>
3^4 = 81 (mod 37) =>
3^4 = 7 (mod 37) => *81 = 7 (mod 37) *igualdade A.

3 = 3 (mod 37) =>
3^3 = 3^3 (mod 37) =>
3^3 = 27 (mod 37) => *Igualdade B.

(3^4)^2 = 7^2 (mod 37) => *Elevamos a igualdade A ao quadrado.
3^8 = 49 (mod 37) =>
3^8 = 12 (mod 37) => *Igualdade C.

(3^3)*(3^8) = 27*12 (mod 37) => * fizemos Igualdade B vezes a C.
3^11 = 324 (mod 37) =>
3^11 = 28 (mod 37) => * 324 = 28 (mod 37) *Igualdade D.

(3^11)*(3^100) = 28*p (mod 37) => *Multiplicamos as Igualdades D e E.
3^111 = 28*p (mod 37) =>
(3^37)^3 = 28*p (mod 37) =>
(3)^3 = 28*p (mod 37) => *3^37 = 3 (mod 37) *Fermat
27 = 28*p (mod 37) =>
28*p = 27 (mod 37) => *propriedade simétrica da cpngruência
28*p = 952 (mod 37) => *27 = 952 (mod 37)
28*p = 952 (mod 37) => *27 = 952 (mod 37)
p = 34 (mod 37) => *Dividimos a igualdade por 28.
p = 34

Professores particulares de Matemática

+ Ver todos
Encontre e contrate um professor particular para te ajudar nos estudos.

Pergunte aos nossos professores

Você possui uma lista de exercícios ou Trabalho?

Se seu problema for dificuldade em uma lista de exercícios, revisão de teses e dissertações, correção de textos ou outros trabalhos, peça uma ajuda pelo Tarefas Profes.

Enviar Tarefa