Exercícios - Algoritmos de Euclides 2021-2

6. (25 pontos) Nesta pergunta você deve mostrar a corretude do algoritmo de Euclides, respondendo os seguinte três itens. (a) (10 pontos) Sejam a, b, q, r ∈ Z tal que a = bq + r, onde q ≠ 0. Seja d ∈ Z. Demonstre a seguinte equivalência: d|a ∧ d|b ⟺ d|b ∧ d|r, dividindo a demonstração em ⟹ e ⟸. Você pode (deve) usar as seguintes propriedades como ponto de partida (Teorema [3.4.1]): Sejam a, b, c ∈ Z. Então, (i) se a|b e a|c então a|b + c; (ii) se a|b então a|bc; (iii) se a|b e b|c então a|c. (b) (5 pontos) Use o item anterior para demonstrar a seguinte afirmação: mdc(a, b) = mdc(b, r). (c) (5 pontos) Use a definição original de divisor como base para demonstrar que mdc(r, 0) = r. As provas de (b) (c) e (d) demonstram a corretude do algoritmo de Euclides. Colocando a = r0; b = 1 basta mostrar que mdc(a, b) = mdc(r0, r1) = mdc(r1, r2) = ... = mdc(rn-2, rn-1) = mdc(rn-1, rn) = mdc(rn, 0) = rn. Onde ri = ri+1q + ri+2, sempre é a relação (*). Ou seja, o algoritmo não muda o mdc de ri e ri+1 nas suas iterações, e termina assim que rn+1 = 0. (d) (5 pontos) Demonstre que dois termos sucessivo da sequência de Fibonacci são primos entre si. Dica: use um dos itens anteriores desta questão. (e) (5 pontos extra) Na a relação (*), não exigimos que r é um resto, ou seja, que 0 ≤ r < b. Essa condição é necessário para prover corretude do algoritmo? Explique.