[Algoritmo de Euclides]

Ao determinarmos o MDC de dois números por meio do Algoritmo de Euclides, encontram-se cinco quocientes de soma igual a 6. Calcule os números sabendo que o MDC encontrado foi 20. 

gabarito:

O algoritmo completo

......... 1 .... 2 ... 1 ... 2 ---> 1 + 2 + 1 + 2 = 6
260 | 160 | 60 | 40 | 20
60  .| _40 | 20 | .0-|

Tente fazer o caminho oposto para descobrir 260 e 160

Olá Castelo;

Uma propriedade é que os quocientes sempre serão maiores ou iguais a 1, pois na divisão euclidana entre dois números p e q inteiros positivos distintos, supondo p> q:

[latex]p = kq + r, \text{ } \text{ }p> q \implies kq + r > q \implies r > q-kq[/latex]

[latex]0 \le r < q , \text{ } r > q-kq \implies q > q -kq \implies kq >0 \implies k>0 \implies k \ge 1[/latex]

Como na última divisão chega-se no mdc, ela deve ser exata com p> q isso significa que um [latex] p = 20k[/latex] e[latex]\text{ } q = 20[/latex]
[latex]\implies k\cdot 20 > 20\implies k > 1 \implies k \ge 2 [/latex] note que a única solução seria se todos os demais quocientes fossem 1 e o último fosse dois.

1+ 1+1 +1 +2 = 6

Demonstração:

Sejam [latex]x_1, \text{ }x_2, \text{ } x_3, \text{ } x_4 \text{ }e \text{ } x_5 [/latex] os quocientes do algoritmo na ordem em que são executados:

[latex]x_1 \ge 1, \text{ } x_2 \ge 1, \text{ } x_3 \ge 1, \text{ } x_4 \ge 1, \text{ } x_5 \ge 2 \implies x_1 + x_2 + x_3 + x_4+ x_5 \ge 6[/latex]

Portanto a solução só ocorre quando cada x_i é mínimo.

Bons estudos

Muito obrigado pelo auxílio, colegas. Compreendi perfeitamente.