Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 5: Aritmética modular- O que é aritmética modular?
- Operador módulo
- Desafio de Módulo
- Módulo de congruência
- Relação de congruência
- Relações equivalentes
- O teorema do resto do quociente
- Adição e subtração modular
- Adição modular
- Desafio de Módulo (Adição e Subtração)
- Multiplicação modular
- Multiplicação modular
- Exponenciação modular
- Exponenciação modular rápida
- Exponenciação Modular Rápida
- Inversas modulares
- O Algoritmo Euclidiano
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
O Algoritmo Euclidiano
Lembre-se que o Máximo Divisor Comum (MDC) de dois inteiros A e B é o maior inteiro que divide A e B.
O Algoritmo Euclidiano é uma técnica para encontrar de forma rápida o MDC de dois inteiros.
O Algoritmo
O Algoritmo Euclidiano para encontrar o MDC(A,B) é dado por:
- Se A = 0, então MDC(A,B)=B, uma vez que MDC(0,B)=B, e podemos parar a verificação.
- Se B = 0, então MDC(A,B)=A, uma vez que o MDC(A,0)=A, e podemos parar a verificação.
- Escreva A na forma do resto do quociente (A = B⋅Q + R)
- Encontre o MDC(B,R) usando o Algoritmo Euclidiano, já que MDC(A,B) = MDC(B,R)
Exemplo:
Encontre o MDC de 270 e 192
- A=270, B=192
- A ≠0
- B ≠0
- Faça uma divisão longa para descobrir que 270/192 = 1 com um resto de 78. Podemos escrever isso como: 270 = 192 * 1 +78
- Encontre o MDC(192,78), já que MDC(270,192)=MDC(192,78)
A=192, B=78
- A ≠0
- B ≠0
- Faça uma divisão longa para descobrir que 192/78 = 2 com um resto de 36. Podemos escrever isso como:
- 192 = 78 * 2 + 36
- Encontre o MDC(78,36), já que MDC(192,78)=MDC(78,36)
A=78, B=36
- A ≠0
- B ≠0
- Faça uma divisão longa para descobrir que 78/36 = 2 com um resto de 6. Podemos escrever isso como:
- 78 = 36 * 2 + 6
- Encontre o MDC(36,6), já que MDC(78,36)=MDC(36,6)
A=36, B=6
- A ≠0
- B ≠0
- Faça uma divisão longa para descobrir que 36/6 = 6 com um resto 0. Podemos escrever isso como:
- 36 = 6 * 6 + 0
- Encontre o MDC(6,0), já que MDC(36,6)=MDC(6,0)
A=6, B=0
- A ≠0
- B =0, MDC(6,0)=6
Assim, mostramos que:
MDC(270,192) = MDC(192,78) = MDC(78,36) = MDC(36,6) = MDC(6,0) = 6
MDC(270,192) = 6
Entendendo o Algoritmo Euclidiano
Se analisarmos o Algoritmo Euclidiano, podemos ver que ele usa as seguintes propriedades:
- MDC(A,0) = A
- MDC(0,B) = B
- Se A = B⋅Q + R e B≠0, então MDC(A,B) = MDC(B,R) sendo Q um inteiro, e R um inteiro entre 0 e B-1
As duas primeiras propriedades nos permitem encontrar o MDC se qualquer número for igual a 0. A terceira propriedade nos permite pegar um problema maior, e mais difícil de resolver, e reduzi-lo a um problema menor, mais fácil de resolver.
O Algoritmo Euclidiano faz uso dessas propriedades para reduzir o problema em problemas cada vez mais simples, usando a terceira propriedade, até que ele seja facilmente resolvido através do uso de uma das duas primeiras propriedades.
Podemos entender o porquê dessas propriedades funcionarem através da prova.
Podemos provar que o MDC(A,0)=A da seguinte forma:
- O maior inteiro que pode dividir A sem deixar resto é A.
- Todos os inteiros podem dividir 0 sem deixar resto, uma vez que para todo inteiro, C, podemos escrever C ⋅ 0 = 0. Então, concluímos que A deve dividir 0 sem deixar resto.
- O maior número que divide A e 0 é A.
A prova para MDC(0,B)=B é similar. (É a mesma prova, mas substituímos A por B).
Para provar que MDC(A,B)=MDC(B,R) primeiro precisamos mostrar que MDC(A,B)=MDC(B,A-B).
Suponha que temos três números inteiros A,B and C such that A-B=C.
Prova que MDC(A,B) divide C sem deixar resto
O MDC(A,B), por definição, divide A sem deixar resto. Como resultado, A deve ser algum múltiplo do MDC(A,B). Isto é, X⋅MDC(A,B)=A onde X é algum inteiro
O MDC(A,B), por definição, divide B sem deixar resto. Como resultado, B deve ser algum múltiplo do MDC(A,B). Isto é, Y⋅MDC(A,B)=B onde Y é algum inteiro
A-B=C nos dá:
- X⋅MDC(A,B) - Y⋅MDC(A,B) = C
- (X - Y)⋅MDC(A,B) = C
Assim, podemos ver que MDC(A,B) divide C sem deixar resto.
Uma ilustração dessa prova é mostrada na parte esquerda da figura abaixo:
Prova que o GCD(B,C) divide A sem deixar resto
O MDC(B,C), por definição, divide B sem deixar resto. Como resultado, B deve ser algum múltiplo do MDC(B,C). Isto é, M⋅MDC(B,C)=B onde M é algum inteiro
O MDC(B,C), por definição, divide B sem deixar resto. Como resultado, B deve ser algum múltiplo do MDC(B,C). Isto é, M⋅MDC(B,C)=B onde M é algum inteiro
A-B=C nos dá:
- B+C=A
- M⋅MDC(B,C) + N⋅MDC(B,C) = A
- (M + N)⋅MDC(B,C) = A
Assim, podemos ver que MDC(B,C) divide A sem deixar resto.
Uma ilustração dessa prova é mostrada na figura abaixo
Prove que GCD(A,B)=GCD(A,A-B)
- MDC(A,B), por definição, divide B sem deixar resto.
- Provamos que MDC(A,B) divide C sem deixar resto.
- Uma vez que MDC(A,B) divide B e C sem deixar resto, ele é um divisor comum de B e C.
MDC(A,B) deve ser menor ou igual ao MDC(B,C), porque o MDC(B,C) é o “máximo” divisor comum de B e C.
- MDC(B,C) por definição, divide B sem deixar resto.
- Provamos que MDC(B,C) divide A sem deixar resto.
- Uma vez que MDC(B,C) divide A e B sem deixar resto, ele é um divisor comum de A e B.
MDC(B,C) deve ser menor ou igual a MDC(A,B), porque MDC(A,B) é o “máximo” divisor comum de A e B.
Dado que o MDC(A,B)≤MDC(B,C) e MDC(B,C)≤MDC(A,B), podemos concluir que:
MDC(A,B)=MDC(B,C)
O que é equivalente a:
MDC(A,B)=MDC(B,A-B)
Uma ilustração dessa prova é mostrada no lado direito da figura abaixo.
Prove que GCD(A,B) = GCD(B,R)
Provamos que MDC(A,B)=MDC(B,A-B)
A ordem dos temos não importa, então podemos dizer que MDC(A,B)=MDC(A-B,B)
Podemos fazer MDC(A,B)=MDC(A-B,B) repetidamente para obter:
MDC(A,B)=MDC(A-B,B)=MDC(A-2B,B)=MDC(A-3B,B)=...=MDC(A-Q⋅B,B)
Mas, A= B⋅Q + R, então A-Q⋅B=R
Assim, MDC(A,B)=MDC(R,B)
A ordem dos temos não importa, desta forma:
MDC(A,B)=MDC(B,R)
Quer participar da conversa?
Nenhuma postagem por enquanto.