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 <[email protected]> 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.
