Algoritmo de divisão.

O processo de executar uma divisão simples é de conhecimento de todos desde as séries iniciais na escola. Entretanto, o que poucos sabem é que esta mesma operação permite atacar problemas bem mais complicados, conhecidos como problemas Diofantinos.
Vejamos um exemplo: "No reino de Diofante, os responsáveis pela economia decidiram alterar a moeda corrente, permitindo apenas notas cujos valores eram de 7 e 11 unidades, chamadas hips. Uma pessoa pagará uma conta de 111 hips em notas de 11 hips e deseja seu tronco em notas de 7 hips. Como deverá ser feita esta transação?"
Poderíamos tentar obter a solução através de tentativas, mas pode levar algum tempo. Usaremos o algoritmo de divisão para resolvê-lo.
A ideia e efetuar a divisão entre as duas notas, de 11 e 7 hips.

Prosseguimos fazendo a divisão entre o divisor (7) e o resto (4):

Finalmente, realizamos novamente a divisão entre o novo divisor (4) e o novo resto (3):

Quando o ultimo resto dá 1, encerramos o processo.
Realizada esta etapa, devemos utilizar as contas anteriores de trás para frente, como mostraremos adiante.
A última conta mostra que:
1 = 4 - (1x3)     (A)
Assim, veja que o valor 1 foi escrito como uma combinação envolvendo os valores 4 e 3, que eram o dividendo e o divisor da última divisão.
A penúltima conta diz que:
3 = 7 - (1x4)     (B)
Se na primeira conta (a), trocarmos o valor em negrito 3 por 7 (1x4), identificada por (B), teremos:
1 = 4 - [1x ( 7 - 1x4)] = 4 - (7 - 4)
Aqui precisamos explicar o que ocorre quando há um sinal do lado de fora dos parênteses. Suponha que você esteja fazendo a seguinte conta:
10 - (5 + 2)
Você pode "distribuir" o sinal mesmo trocando os sinais de tudo o que estiver do lado de dentro dos parêntesis. Assim:
10 - 5 - 2 = 3
Da mesma forma, a conta 1 = 4 (7 - 4) ficará:
1 = 4 - 7 + 4, portanto,
1 = (2x4) - (1x7)     (C)
Veja que o valor foi escrito como uma combinação envolvendo os números 7 e 4, que eram o dividendo  o divisor da penúltima divisão.
Finalmente, a primeira divisão nos diz que
4 = 11 - (1x7).
Se na afirmação identificada por C, trocarmos o 4 em negrito por 11 - (1x7) teremos:
1 = 2x11 - (1x7) - (1x7) =  (2x11) - (3x7)
Escrevemos o 1 como uma combinação dos valores 7 e 11, que eram o dividendo e o divisor da primeira divisão. Como no problema desejamos encontrar o valor 111, que é 111 vezes o valor 1, basta multiplicarmos a conta anterior por 111:
1 = (2x11) - (3x7) x111
111 = (222x11) - (333x7)
Assim, a pessoa pagará a conta com 222 notas de 11 hips e receberá de troco 333 notas de 7 hips.
Há outras soluções possíveis.

Fonte: Prof. Fausto Arnaud Sampaio.