Algoritmo de euclides

Unidade: Divisibilidade
Tema: Algoritmo de Euclides.
Objetivo: Apresentar o algoritmo da divisão euclidiana e suas aplicações.

1. Arte
Divisibilidade
Se , , então temos duas possibilidades:
i) é múltiplo de , ou seja, ii) está entre dois múltiplos consecutivos de , ou seja,

2. Arte
Algoritmo de Euclides
Dados,
onde

3. Arte
Unicidade
é múltiplo de
Suponha que existam e tais que , com

Suponhamos que , digamos .
Então e
Mas de temos

Como e , da eq. (1) temos que:
, o que é um absurdo.
Da mesma forma, prova-se que a desigualdade também é impossível.
Portanto e consequentemente .

4. Arte
Exemplos
Para e temos que e pois
Para e temos que e pois
Para e temos que e pois

5. Arte
Exercício
Mostre que todo número ímpar pode ser escrito na forma ou .

6. Arte
Solução
Seja um número ímpar qualquer tal que.
Temos que .
Se temos que é par.
Se temos que é ímpar.
Se temos que é par.
Se temos que é ímpar. 7. Arte
Exercício
Mostre que o quadrado de um número inteiro qualquer é do tipo ou .

8. Arte
Solução
Seja um inteiro qualquer. Se então , ou seja .
.
Se ,
Se ,
Se ,

9. Arte
Exercício
Na divisão euclidiana de 802 por , o quociente é 14. Determine os valores possíveis de e do resto.

10. Arte
Solução
Pelo algoritmo euclidiano temos que , vemos que o maior valor possível para é 57, visto que qualquer outro valor maior não permite que o quociente seja 14.
Com argumento similar obtemos que menor valor possível para é 54.
Portanto, os possíveis valores para são: 54, 55,56 e 57 com os respectivos valores para iguais a 4, 18,32 e 46, visto que

1. Arte
Dinâmica Local
É possível encontrar dois inteiros múltiplos de 5 tais que o resto da divisão euclidiana de um pelo outro seja 13? Justifique sua resposta.

Resolução no quadro digital

Unidade: Divisibilidade
Tema: Aula de Exercícios.