01 Congruência Modular
HTML-код
- Опубликовано: 26 окт 2024
- A todos que curtiram e quiserem contribuir com o canal, segue abaixo a minha chave PIX, no meu nome mesmo. Não se sinta obrigado a doar, meu trabalho aqui no RUclips é de divulgação de conhecimento, de forma gratuita mesmo. Mas claro, qualquer ajuda é bem vinda e eu desde já agradeço muito pela sua contribuição e audiência!
b4bb1b4d-2746-450d-bb78-b788af84438c
Seja membro do canal e tenha acesso a inúmeros benefícios para os seus estudos! As lives do Exatas são gratuitas, mas o acesso posterior a elas não! Como membro você tem acesso a elas e a muito mais. Aulas completas de matemática e física muito além do conteúdo que está aqui publicado! Escolha um nível para você e aproveite! Considere também nos enviar um "Valeu" ali no botão de doação para nos ajudar a manter o nosso trabalho!
![Quando Rondo - Life Goes On [Official Music Video]](http://i.ytimg.com/vi/eIf3fhMXAow/mqdefault.jpg)
Até agora foi a melhor aula de congruência que eu assisti!!! a mais completa! Parabéns!
Parabéns pela aula a respeito de congruência. Em termos da qualidade e do conteúdo da aula, conseguiu superar a maior parte dos vídeos que existem (Brasil ou exterior) sobre o assunto.
No caso (2³⁶)/5 também poderia ser resolvido assim:
2³⁶ = [(2²)²]⁹ = (4²)⁹ = 16⁹
16 ≈ 1 (mod 5)
16⁹ ≈ 1 (mod 5)
R = 1
.........
Obrigado pela ótima vídeo-aula. Foi muito útil para mim.
Muito bom! - Mas como determinar os quatros últimos algarismos de 3^2004 (3 elevado a 2004)?? Um abração!!!
Opa, tudo tranquilo, meu rapaz?
Então, geralmente quando queremos saber os n últimos dígitos de um número N qualquer basta calcular o menor valor inteiro não negativo de k tal que:
N ≡ k (mod 10ⁿ)
Esse k é, não por acaso, o resto da divisão de N por 10ⁿ. Sabemos que o resto da divisão de um dividendo D por um divisor d deixa resto R tal que D ≡ R (mod d), sendo esse R justamente o menos inteiro não negativo que satisfaz essa congruência.
Por exemplo, quais são os 3 últimos dígitos de 10715?
Podemos fazer:
10715 ≡ k (mod 10³)
10715 ≡ k (mod 1000)
Daí, o resto da divisão de 10715 por 1000 é justamente 715.
Agora, vamos à sua questão!
Queremos saber os 4 últimos dígitos de 3²⁰⁰⁴. Dessa forma, queremos saber o resto da divisão de 3²⁰⁰⁴ por 10⁴:
3²⁰⁰⁴ ≡ k (mod 10⁴)
3²⁰⁰⁴ ≡ k (mod 10000)
Daqui, devido aos números grandes, podemos utilizar o Teorema Chinês dos Restos, que nos diz que um sistema de congruências modulares com módulos primos entre si admite uma solução mútua que é o produto dos módulos.
Veja que 10⁴ = 2⁴ · 5⁴ = 16 · 625. Logo, devemos calcular p e q tais que 3²⁰⁰⁴ ≡ p (mod 16) e 3²⁰⁰⁴ ≡ q (mod 625). Vejamos como resolver cada um.
Para o primeiro, podemos pensar da seguinte forma. Sabemos que 3⁴ = 81. Logo, como 80 é múltiplo de 16:
3⁴ ≡ 1 (mod 16)
(3⁴)⁵⁰⁶ ≡ 1⁵⁰⁶ (mod 16)
3²⁰⁰⁴ ≡ 1 (mod 16)
Agora, para o segundo, 3²⁰⁰⁴ mod 625. Podemos usar a função totiente de Euler, ϕ(n). Uma propriedade muito útil nos diz que se n é um inteiro positivo e k é um inteiro positivo co-primo com n (ou seja, n e a são primos entre si), então:
a^(ϕ(n)) ≡ 1 (mod n), o chamado teorema de Euler.
Não vou entrar no mérito das propriedades dessa função aqui. Mas uma delas nos diz que se p é um número primo, então ϕ(pⁿ) = pⁿ - pⁿ ⁻ ¹. Logo:
ϕ(625) = ϕ(5⁴) = 5⁴ - 5⁴ ⁻ ¹ = 625 - 125 = 500.
Dessa forma, pelo teorema de Euler:
3⁵⁰⁰ ≡ 1 (mod 625)
(3⁵⁰⁰)⁴ ≡ 1⁴ (mod 625)
3²⁰⁰⁰ ≡ 1 (mod 625)
3²⁰⁰⁰ · 3²⁴ ≡ 1 · 3²⁴ (mod 625)
3²⁰²⁴ ≡ 3²⁴ (mod 625)
Aqui é só ir repetindo as exponenciações que a gente chega, agora que tá reduzido o expoente:
3² ≡ 9 (mod 625)
3⁴ ≡ 81 (mod 625)
3⁸ ≡ 6561 ≡ 311 (mod 625)
3¹⁶ ≡ 311² = 96724 ≡ 471 (mod 625)
3²⁴ ≡ 3⁸ · 3¹⁶ ≡ 311 · 471 = 146481 ≡ 231 (mod 625)
Por fim, de posse dessas duas incríveis e gostosas congruências, podemos utilizar o Teorema Chinês dos Restos no sistema:
3²⁰⁰⁴ ≡ 1 (mod 16)
3²⁰⁰⁴ ≡ 231 (mod 625)
Como 16 e 625 são primos entre si, essa solução módulo 10000 será única. Podemos encontrá-la resolvendo:
x ≡ 1 (mod 16)
x ≡ 231 (mod 625)
Resolvendo esse sistema encontraremos x = 6481!
Meu fofinho mais lindo. Cara top em tudo o que faz. Recomendo a todos
Excelente aula!!!!!
Parabéns professor. Excelente aula.
Excelência em ensino.
👏👏👏👏
Parabéns.
Gostei.
Muito obrigado
Saudações, mestre! Nesse trecho, ele teria dois restos? 21 e 1?? 59:53 / 1:19:44
Fala meu rapaz! Então, vamos lá. Para que algo seja resto de uma divisão, tem que cumprir duas condições: 1ª) tem que ser não-negativo; 2ª) tem que ser menor que o divisor. Então, apesar de termos tanto 21⁵ ≡ 21 (mod 5) e 21⁵ ≡ 1 (mod 5), apenas o "1" satisfaz ambas as condições (pois é o único que é menor que 5, o divisor). Beleza? Grandes abraços, rapaz, qualquer dúvida é só falar!
@@exatasmilitar Ataaaa! Muito obrigado por responder, mestre! Imensamente grato! Está difícil entender congruência, mas estou longe de desistir rsrs. Abraços, mestre!
@@heitor9351 Que coisa boa, meu rapaz! É isso aí, vamos que vamos!!!
O relógio pode girar no sentido negativo?
Como 3 divido por 3 dá zero? 0:30:00
Fala, boa noite! Porque quando estamos falando de congruência o que importa na divisão é o resto, e o resto da divisão de 3 por 3 é 0. Da mesma forma, por exemplo, a divisão de 15 por 3 permite desenvolvermos que 15 ≡ 0 (mod 3), visto que 15 deixa resto 0 na divisão por 3.
Espero ter ajudado! Bons estudos!
Um professor de ensino fundamental. Precisa disso? KKKKK
@@lourivaldivinofaria2701 Opa meu amigo, tudo bem?
Rapaz, "precisar" é uma palavra muito forte. Eu pessoalmente acho que em termos de escola há coisas mais importantes. Se eventualmente sobrasse algum tempo, porém, não há mal em mostrar aos alunos que existe uma aritmética dos restos da divisão euclidiana. É interessante, ALTAMENTE aplicável na vida prática e pode ser muito divertido.