Comecemos por encontrar o maior divisor comum de 527 e 341 usando o algoritmo Euclidiano padrão como um aquecimento:

O algoritmo padrão é sucinto e direto e servirá como um pequeno guia agradável para implementar o algoritmo estendido.

Para o Algoritmo Euclidiano Estendido vamos pegar a terceira equação (em azul), subtrair 155(1) de ambos os lados, e fazer um pequeno rearranjo para fazer uma equação equivalente onde 31 é isolado.

Próximo substituiremos 155 por 341-186(1), que pode ser encontrada resolvendo a segunda equação para 155, dando-nos o seguinte

Agora vamos limpar isto. Certifique-se de distribuir o sinal negativo através do parêntese e substitua 186 + 186 por 186-2.

Como você pode notar, nós estamos simplesmente trabalhando para trás através do algoritmo padrão. Vamos precisar executar este processo mais uma vez para produzir uma equação envolvendo 527 e 341, que é o nosso objetivo final.

Para fazer isso, substitua 186 por 527 – 341(1), que vem da primeira equação quando resolvemos para 186.

Abrir simplificando a equação distribuindo os 2 e combinando em grupos de 527 e 341.

Extraímos agora 31 como uma combinação linear de 527 e 341. Muito legal, huh?

Outras vezes o número do lado oposto da combinação linear é o maior divisor comum. Então neste caso o 31 é o maior divisor comum de 527 e 341.

O Algoritmo Euclidiano Estendido é útil porque produz a Identidade de Bezout assim como destaca o gcd.

Obrigado pela leitura!