Ensino Superior ⇒ Teoria dos Números - Aritmética das classes Tópico resolvido

[mathprime]

Encontre, caso exista, o inverso de [2023] em [tex3]\mathbb{Z}[/tex3]₄₁₈₀.

[FelipeMartinMOD]

[tex3]2023 \cdot x = 4180 \cdot n +1 \iff 1 = 2023 \cdot x -4180\cdot n[/tex3]

temos uma equação de Bezout. Ela terá solução se, e somente se, [tex3]\mdc(2023,4180) =1[/tex3]

Esse problema sai em poucas linhas com o algoritmo de Euclides, vou fazer sem ele.

Vamos fatorar [tex3]2023[/tex3]. Primeiro note que [tex3]40 < \sqrt{2023} <50[/tex3], então, vamos considerar os fatores primos até uns 43, no máximo.

Claramente não é divisível por [tex3]2,3[/tex3] nem [tex3]5[/tex3], mas [tex3]2023 = 7 \cdot 289[/tex3].

[tex3]289[/tex3] não é divisível nem por [tex3]7[/tex3] nem por [tex3]11[/tex3], nem por [tex3]13[/tex3] a última opção é [tex3]17[/tex3], mas, [tex3]289-170 = 119[/tex3] e [tex3]119 - 34 = 85[/tex3] e [tex3]85 - 68 = 17[/tex3]. Então, [tex3]2023 = 7 \cdot 17^2[/tex3].

Vejamos se [tex3]4180[/tex3] é divisível por [tex3]7[/tex3]: [tex3]4180 = 7 \cdot 597 + 1[/tex3], então não.
Vejamos se [tex3]4180[/tex3] é divisível por [tex3]17[/tex3]: [tex3]4180 = 418 \cdot 10 = 209 \cdot 20[/tex3] e não temos que [tex3]209[/tex3] é divisível por [tex3]17[/tex3]. Então existe uma solução pra nossa equação: [tex3]1 = 2023 \cdot x -4180\cdot n[/tex3].

Vamos aplicar [tex3]\mod 7[/tex3] na nossa equação:

[tex3]1 = -4180n \mod 7 \iff 1 \equiv -n \mod 7 \iff n \equiv -1 \mod 7[/tex3]

agora vamos aplicar [tex3]\mod 17[/tex3] na nossa equação:

[tex3]1 = -4180n \mod 17[/tex3] e [tex3]4180 \mod 17 \equiv 209 \cdot 20 \mod 17 \equiv 39 \cdot 3 \mod 17 \equiv 5 \cdot 3 \mod 17 \equiv -2 \mod 17[/tex3], logo, [tex3]1 \equiv 2n \mod 17 \iff 2n \equiv 1 \mod 17[/tex3]

vamos procurar [tex3]n[/tex3] naturais da forma [tex3]7k-1[/tex3] e tais que [tex3]2n = 17m+1[/tex3]: [tex3] n\in\{6,13,20,27,34,41,48,...\implies 2n \in \{12,26,40,54,68,82,96...\}[/tex3]

[tex3]2n \mod 17 \in \{12,9,6,3,0,-3,-6,-9,-12,-15,-1,-4,-7,-10,-13,1\}[/tex3], ou seja, o décimo sexto termo da sequência [tex3]7k-1[/tex3] nos serve: [tex3]n = 16 \cdot 7 -1=111 \implies 2n = 222 = 221 +1 = 17 \cdot 13 +1[/tex3].

[tex3]2(7k-1) = 17m+1 \iff 14k = 17m +3[/tex3] temos [tex3]k=16, m=13[/tex3], o que implica que a solução geral é da forma [tex3]k =16 + 17t[/tex3], então, [tex3]n = 7 \cdot (16+17t) -1 = 111 + 119t[/tex3], pronto: [tex3]1 = 2023 \cdot x - 4180 \cdot (111+119t)[/tex3]

[tex3]2023 \cdot x -1 = 4180 \cdot (111+119t)[/tex3]

agora é fazer o lado direito [tex3]\mod 2023[/tex3] e igualar a menos um.

[tex3]4180 -4000 -46 = 180 - 46 = 140-6=134[/tex3]:

[tex3]134 (111+119t) \equiv -1 \mod 2023 \iff 713 + 134\cdot 119t \equiv -1 \mod 2023[/tex3]

[tex3]134 \cdot 119 t \equiv -714 \mod 2023 \iff 134 \cdot 119t = 2023 y -714 \iff 134 \cdot t = 17 y - 6[/tex3]

[tex3]6 = 17y -134t[/tex3], [tex3]y[/tex3] claramente deve ser par: [tex3]y = 2z \implies 3 = 17z - 67t[/tex3]

aplcando mod 17: [tex3]3 \equiv t \mod 17 \implies t \equiv 3 \mod 17[/tex3] e, na verdade, [tex3]t=3[/tex3] funciona: [tex3]3 = 17 \cdot z -67 \cdot 3 \implies z = \frac{3 + 3 \cdot 67}{17} = \frac{3 \cdot68}{17}=12[/tex3]

pronto! [tex3]t=3 \implies n= 111+119 \cdot 3 = 468 \implies x = \frac{4180 \cdot 468 + 1}{2023} = 967[/tex3]!

Eis aqui a sua resposta: o inverso de [tex3]2023 \mod 4180[/tex3] é [tex3]967[/tex3].

Quer ver como sai pelo algoritmo de Euclides?

[mathprime]

Quer ver como sai pelo algoritmo de Euclides?

Sim, por favor, e obrigado!

[FelipeMartinMOD]

queremos resolver a equação de Bezout:

[tex3]1 = 2023 x - 4180 n[/tex3]

como eu disse, essa equação tem solução se, e somente se, o mdc entre 2023 e 4180 for 1. Vamos usar o algoritmo de euclides pra encontrar esse MDC.
O algoritmo de Eculides é o seguinte:

Temos dois números naturais [tex3](a,b)[/tex3] com [tex3]a>b[/tex3], substituimos o par [tex3](a,b)[/tex3] pelo par [tex3](b, a - b)[/tex3] repetidas vezes até obtermos um par de números iguais. Mas, como [tex3]\mdc(a,b) = \mdc(b, a \mod b)[/tex3], podemos adaptar o algoritmo substituindo [tex3](a,b)[/tex3] por [tex3](b, a \mod b)[/tex3] até o termo [tex3]a \mod b[/tex3] ser zero:

Vamos lá: [tex3](4180, 2023) \to (2023, 4180-2\cdot2023) = (2023,134) \to (134, 13) \to (13,4) \to (4,1) \to (1,0) \implies\\ \implies \mdc (2023,4180)=1[/tex3]

Agora vamos encontrar [tex3]x[/tex3] e [tex3]n[/tex3] fazendo a volta. É bom marcar os quocientes de cada passagem do nosso algoritmo:
[tex3]4180 = 2023 \cdot (2) + 134[/tex3]
[tex3]2023 = 134 \cdot (15) +13[/tex3]
[tex3]134 = 13 \cdot (10) +4[/tex3]
[tex3]13 = 4 \cdot (3)+1[/tex3] <- começaremos daqui e vamos voltar nos divisores.
[tex3]4 = 1 \cdot (4) +0[/tex3]

[tex3]1 = 13 - 3 \cdot 4 = 13 - 3 \cdot (134-13 \cdot 10) = 13 \cdot 31 - 3 \cdot 134 = \\ =(2023-134 \cdot 15) \cdot 31 - 3 \cdot 134 = 2023 \cdot 31 -134 \cdot (3+31 \cdot 15) = \\ = 2023 \cdot 31 -(4180-2 \cdot 2023)(3+31 \cdot 15) = 2023 \cdot (31+2 \cdot(3+31 \cdot 15)) - 4180 \cdot (3+31 \cdot 15)[/tex3]

confuso né?

tá ai: [tex3]x = 31+2 \cdot(3+31 \cdot 15) = 31 + 6 + 30 \cdot 31 = 31^2+6 = 961+6=967[/tex3]

hahahaha muito doido né?

[FelipeMartinMOD]

aliás, vou deixar esse comentário aqui pra marcar essa questão como o método modo padrão pra resolver a equação de Bezout (Bézout)