Boa tarde! Faltou colocar que r0 = min(x,y) para o caso de r1=0.
Saudações, PJMS Em 5 de abril de 2016 16:23, Pedro José <petroc...@gmail.com> escreveu: > Bom dia! > > Seja F(x,y) com x >=y Podemos escrever, usando a divisão euclidiana, x = > q*y + r1 com q e a naturais (pois, x,y são naturais) e 0<=r1<y. > Então F(x,y) = F (q1y +r1, y). Mas F(q1y + r1,y) = F(q1y-y+r1,y) = > F((q1-1)y+r1,y), me valendo de F(x,y) = F(x-y, y) para x >y > > Se r1 = 0 posso repetir (q1-1) vezez até obter F(x,y) = F(y,y) = y, me > valendo De F(x,y) = x se x=y. > > Se r1 for maior do que zero posso repetir q1 vezes ao total, até obter > F(x,y) = F(r1,y) > > Como r1 < y posso escrever y = q2r1 + r2 ==> F(x,y) = F(r1, q2r1 + r2) > Então F(x,y) = F(r1,q2r1 + r2) = F(r1, (q2-1)r1 + r2), me valendo de que > F(x,y)=F(x,y-x) se y>x. > > Se r2 = 0 posso repetir (q2-1) vezez até obter F(x,y) = F(r1,r1) = r1, me > valendo De F(x,y) = x se x=y. > > Se r2 for maior do que zero posso repetir q2 vezes ao total, até obter > F(x,y)= F (r1,r2) com r2 < r1 > > Posso proseguir com esse algorítimo tá que ri =0, para um dado i* (pois > ri sempre decresce a cada passo então incontestávelmente se igualará a zero > em um dado passo). E F(x,y) = rj, onde j = i*+1. > > Mas isso nada mais é que o algorítimo euclidiano para m.d.c. > > Para chegar a esse algorítimo basta provar que sejam a e b naturais e a>b, > mdc (a,b) = mdc(a,r), onde a=q*b + r, divisão euclidiana. > > Se x<y basta começar escrevendo y = q1*x + r1 e a solução é igual. > > Portanto a resposta correta é a letra c. > > Saudações, > PJMS > > > > Em 5 de abril de 2016 12:54, Vanderlei Nemitz <vanderma...@gmail.com> > escreveu: > >> Oi, pessoal, tudo bem? Gostaria de saber se alguém consegue resolver a >> seguinte questão. O que eu gostaria é "provar" genericamente e não concluir >> qual é a alternativa correta usando exemplos numéricos, pois isso é >> simples! Muito obrigado! >> >> Para *x* e *y* inteiros estritamente positivos, considere a função: >> >> F(x, y) = F(x – y, y), se x > y >> >> F(x, y) = F(x, y – x), se x < y >> >> F(x, y) = x, se x = y >> >> Podemos concluir que >> >> a) F(x, y) = 1 para quaisquer x e y >> >> b) F(x, y) = 2 se x for múltiplo de y >> >> c) F(x, y) = mdc(x, y) para quaisquer x e y >> >> d) F(x, y) = mmc(x, y) para quaisquer x e y >> >> e) F(x, y) = 1 se x for um número primo >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. > > > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
