algebra algoritmo (4)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

I Algoritmo da divis˜ao: Etapa 1: q = 0; r = a Etapa 2: Se r < b, pare. Nesse caso, o quociente ´e q e o resto r. Etapa 3: Se r ≥ b, fa¸ca r := r − b, q := q + 1 e volte `a Etapa 2. Algoritmo da divis˜ao I Observa¸c˜oes: 1. O algoritmo sempre para: sequˆencia decrescente de n´umeros inteiros positivos. 2. O resultado da aplica¸c˜ao do algoritmo corresponde `as especifica¸c˜oes da sa´ıda (trivialmente). 3. O algoritmo ´e extremamente ineficiente, em especial se a >> b. Teorema da Divis˜ao Teorema de divis˜ao: Sejam a e b inteiros positivos. Existem n´umeros inteiros q e r tais que a = bq + r 0 ≤ r < b Al´em disso, q e r s˜ao ´unicos. Prova: Unicidade - Sejam q, q 0 ,r,r 0 tais que a = bq + r 0 ≤ r < b (1) a = bq0 + r 0 0 ≤ r 0 < b (2) Subtraindo-se (1) de (2), obtemos: r − r 0 = b(q 0 − q) Ora, mas 0 ≤ r,r 0 < b e portanto 0 ≤ r − r 0 < b. Ou seja, 0 ≤ b Algoritmo Euclideano I Objetivo: Calcular o mdc entre dois n´umeros inteiros. I Defini¸c˜ao: o m´aximo divisor comum entre a e b ´e o n´umero d tal que: I d|a (ou d ´e divisor de a) I d|b I se d 0 ´e divisor de a e b, ent˜ao d 0 |d. I Escrevemos d = mdc(a, b). Se mdc(a, b) = 1, dizemos que a e b s˜ao primos entre si. Algoritmo Euclideano I Dados dois n´umeros inteiros positivos a e b tais que a ≥ b, divide-se a por b, encontrando resto r1. Se r1 6= 0, dividimos b por r1, obtendo resto r2. Se r2 6= 0, dividimos r1 por r2 e assim por diante. O ´ultimo resto diferente de zero dessa sequˆencia de divis˜oes ´e o mdc(a, b). I Exemplo: 1234 54 46 8 6 2 46 8 6 2 0 Ou seja, mdc(1234, 54) = 2. Algoritmo euclideano Perguntas: 1. Por que o ´ultimo resto n˜ao nulo ´e o mdc? 2. Por que o algoritmo para? a = bq1 + r1 e 0 ≤ r1 < b b = r1q2 + r2 e 0 ≤ r2 < r1 r1 = r2q3 + r3 e 0 ≤ r3 < r2 r2 = r3q4 + r4 e 0 ≤ r4 < r3 . . . . . . Algoritmo euclideano Respostas: I Segunda pergunta: observe que b > r1 > r2 > . . . ≥ 0 Como essa sequˆencia ´e finita, o algoritmo sempre para. Mais ainda, o n´umero de divis˜oes efetuadas ´e no m´aximo b (por que?). I Primeira pergunta: demonstra¸c˜ao do algoritmo euclideano Demonstra¸c˜ao do algoritmo euclideano Lema Sejam a e b n´umeros inteiros positivos. Se existem inteiros g e s tais que a = bg + s, ent˜ao mdc(a, b) = mdc(b,s). Prova Sejam d1 = mdc(a, b) e d2 = mdc(b,s). Afirmamos que d1 ≤ d2. De fato, existem inteiros positivos u e v tais que: a = d1u e b = d1v Substituindo a e b na equa¸c˜ao a = bg + s obtemos s = d1u − d1vg = d1(u − vg).