Divisores e Múltiplos Comuns

A fórmula e o procedimento para realizar essa determinação de encontrar o máximo divisor comum é muito simples, como veremos a seguir:

Nota: dois números naturais possuem sempre divisores em comum.

Na unidade anterior, vimos a decomposição por fatores primos e por meio dela podemos calcular o MDC entre dois números. Para a realização deste cálculo são necessárias três etapas descritas abaixo:

• 1ª etapa: decompõe-se o número em fatores primos;
• 2ª etapa: seleciona-se os fatores primos de menores expoentes que se repetem em ambos os casos;
• 3ª etapa: realiza-se a multiplicação dos fatores primos.

Exemplificando:

Encontre o MDC entre 36 e 90.

1ª etapa: é preciso decompor 36 e 90, a partir dos fatores primos, podendo escrevê-los em forma exponencial também.

36 = 2 x 2 x 3 x 3 = 2² x 3²

90 = 2 x 3 x 3 x 5 = 2 x 3² x 5

2ª etapa: entre eles, selecionamos os fatores primos de menores expoentes que se repetem em ambos os casos.

Neste exemplo, os números 2 e 3² se repetem nos dois casos e possuem menores expoentes.

3ª etapa: realiza-se a multiplicação dos fatores primos, e encontra-se o resultado final.

Portanto o MDC entre 36 e 90 que é igual MDC (36,90) = 3² x 2 = 18.

‍

O matemático Diofanto foi um dos responsáveis pelo grande crescimento e evolução da álgebra no mundo, e a partir deles, outros inúmeros matemáticos se inspiraram e se dedicaram aos estudos da teoria dos números. A maioria dos historiadores colocam Diofanto como pertencente ao século III d. C. Além do fato de que seus estudos e carreira terem sidos baseados na região de Alexandria, nada mais se sabe de grande relevância sobre o grego.

Entre seus principais trabalhos, Diofanto foi cultor da aritmética, números poligonais e Porisma. Entre eles, porém, o que mais destaca-se é a aritmética, já que é a obra mais intacta e mais completa do matemático, sendo seis livros de todos os treze que já escreveu.

Nesta obra da aritmética citada, Diofanto faz uma abordagem complexa em relação à teoria dos números, se dedicando, principalmente, na resolução de 130 problemas que ocorrem entre as equações. A obra possui tanta importância no meio matemático que os problemas algébricos que tem resultados indeterminados, encontrando-se apenas soluções racionais, foram batizados como “problemas diofantinos”, e esse termo designa até hoje as soluções que não são inteiras.

Forma de Sincopação de Diofanto

Uma das técnicas de Diofanto era de realizar simplificações, por meio de abreviações. A palavra aritmética em si é uma conjunção entre arithmos (número) e techne (ciência). O autor utilizou essa palavra em grego para denotar alguns de seus símbolos e abreviações como no caso arithmos, em que colocou α e ρ, e com o passar dos anos se desenvolveu para um sinal sigma grego ϛ.

Existe também uma teoria, apesar de ainda haver dúvidas quanto a ela, de que a notação para potência se indicaria pelas letras da palavra grega dunamis (NAMI∑) que na tradução significa “potência” e “incógnita ao cubo”.

Compreendendo isso facilmente, podemos explicar os símbolos das potências seguintes da incógnita (quadrado-quadrado), (quadrado-cubo) e (cubo-cubo).

Para a expressão “menos”, Diofanto utiliza um símbolo que se assemelha a um V inverso com a bissetriz traçada nele. Também teria se originado a partir da palavra grega leipis (ᴧEIΨI∑), que significa “menos”. Todos os elementos negativos eram associados e antes de se escreverem eram denotados com o sinal de menos.

Um Pouco de História

As equações Diofantinas compõem uma teoria em que estão inseridas na teoria dos números e tem como objetivo central investigar se as soluções das equações são inteiras ou racionais, por exemplo, a equação, 2x + 4y = 5, y² - x³ = -2 ou x² + y² = z². Em relação a nomenclatura, obviamente, equações Diofantinas, faz uma homenagem a um dos maiores estudiosos de álgebra que já existiu, Diophantus de Alexandria, que foi o responsável por descobrir, desenvolver e formular inúmeras equações. Como já citado, serviu de grande inspiração para outros matemáticos brilhantes, como o francês Pierre de Fermat (1601-1665).

Fermat tinha um cargo, na época, de conselheiro, e uma de suas responsabilidades estava interligada com a condenação de pessoas para serem mortas na fogueira, por essa razão, não devia ter muitas amizades. Quando tinha tempo livre, Pierre se dedicava ao estudo da aritmética e ganhou até um apelido de “Príncipe dos Amadores”, pois nesses momentos de estudo acabou descobrindo os conceitos de probabilidade, fundamentos do cálculo e complexos teoremas sobre os números inteiros. Fermat, porém, ganhou interesse pela matemática graças a uma obra de um escritor chamado Bachet, Arithmetica de Diophantus, livro que consolidou as ideias de Diofanto.

A partir daí, Fermat iniciou um novo ciclo da área da teoria dos números, tendo entre elas a análise diofantina, sendo responsável por formular os mais famosos problemas da matemática, desafiando estudiosos por diversas gerações. Podemos afirmar que Pierre Fermat influenciou praticamente todas as áreas da aritmética, afirmando até mesmo que possuía demonstrações para as Ternas Pitagóricas: se n≥3, a equação xⁿ + yⁿ = zⁿ, não admite soluções inteiras não-nulas.

Foi nessa demonstração que criou a conhecida “demonstração de Fermat”, que por muitos anos foi considerada o desafio mais complicado e famoso da matemática, justamente por parecer muito simples, mas nenhum matemático antes de 1994 conseguiu desvendar.

Fermat adorava provocar situações embaraçosas com outros matemáticos, principalmente os ingleses, porém, o destino fez com que justamente um inglês chamado Andrew Wiles fosse o iluminado para desvendar o “último teorema de Fermat”. Na época (1994), tal feito chegou a ser comparado com a descoberta dos átomos e o descobrimento das estruturas do DNA.

Wiles conta que desde criança tinha obsessão por esse teorema e se propôs de todas as maneiras tentar resolvê-lo. É considerado uma das conquistas mais importantes da história da matemática, e tudo se originou das ideias de Diofanto, ainda no século III. Podemos perceber assim, a importância e relevância que o matemático possui em toda a história.

Equação Diofantina

As equações diofantinas costumam aparecer em problemas, cuja característica principal é de agrupamento, como nos casos abaixo:  

Exemplo 1: Um laboratório médico tem a seu dispor 2 máquinas de raio x. Uma delas examina 15 imagens por vez, já a outra 25 imagens.  Quantas vezes essas máquinas devem ser ligadas para examinar 2 mil imagens?  

Exemplo 2: Quantos campos de futebol e quantos campos de queimada são necessários para que 80 alunos joguem simultaneamente? E se forem 77 alunos?

Exemplo 3: Para agrupar 13 aviões em filas de 3 ou de 5, quantas filas serão formadas de cada tipo?

Para se resolver esses problemas, precisamos buscar soluções inteiras e positivas, sendo assim, não se permite números negativos nesses casos. Dessa forma, podemos organizar o raciocínio pela equação diofantina:

\[ax~+~b~y~=~c\]

Observando os casos acima descritos e entendendo a fórmula dada, o problema do laboratório médico pode ser descrito através de: 15x+25y = 2000.

Na questão dos campos, uma equação é 10l0x+12y=80, que demonstra 2 soluções x = 2 e y = 5 ou x = 8 e y = 0, enquanto a outra questão baseia-se no mesmo método e é representada pela equação l0x + 12y = 77, não possuindo soluções (que sejam pares de números inteiros).

Em relação aos aviões (que pode ser usado como figura de linguagem e ser, portanto, apresentado desde as fases iniciais da escola), a equação 3x+5y=13 apresenta uma única solução (pares de números inteiros e positivos)  x = 1 , y=2.

Ao se elaborar e colocar em prática qualquer um dos problemas, é preciso zelar na escolha dos coeficientes a, b e c, pois não determinarão apenas o nível de dificuldade do problema, mas também controlarão a quantidade de soluções possíveis que existirá, desde que sejam, como visto, inteiros ou inteiros positivos.

Quando estudamos qualquer problema matemático, é interessante termos algum processo para seguir, pois assim, para qualquer problema, teremos já na cabeça a forma de resolução e também identificaremos se possui ou não soluções, e se possui, saber quantas são.

Podemos citar como exemplo a equação de segundo grau abaixo:

\[ax^2 + bx + c = 0\] ,

Essa equação só terá soluções reais se os seus elementos forem maiores que zero.

\[b^2 - 4ac~0\] .

Quando isso ocorrer,vas soluções reais x1 e x2 serão dadas por:

\({{x}_{1}}=(-b+\sqrt{{{b}^{2}}-4ac})/2ª\) e \({{x}_{2}}=(-b+\sqrt{{{b}^{2}}-4ac})/2ª\)  

Quando estudamos as equações Diofantinas, ax + by = c, com a,b e c sendo números inteiros, é necessário saber se existe um critério predeterminado que permita afirmar que aquela equação, originada de um problema, possui solução e também um método para achar tais soluções, caso existam de fato. No caso das diofantinas, nosso único interesse é colocar soluções inteiras de ax + by = c.

Há, realmente, um critério único, que nos faz decidir se a equação padrão de ax + by = c possui ou não soluções inteiras. Esse critério está descrito a seguir:

1. 1. um critério de existência de solução, que já tem como subproduto um processo para encontrarmos uma solução particular;
2. 2. um algoritmo para buscar essa solução particular;
3. 3. a expressão que já propõe todas as soluções inteiras a partir de uma particular.

A Existência da Solução

Tendo, portanto, identificado a resolução da equação diofantina sendo ela:

\[ax + by = c\],

Ou seja, sendo a, b e c como números inteiros, devemos, então, procurar as soluções x e y, para que se forme um par ordenado de números inteiros.

Para isso, deveremos usar propriedades de divisibilidade, que descreveremos abaixo, sendo que as duas primeiras possuem conotação de verificação imediata e a terceira sendo responsável por prova. Essas propriedades foram retiradas da Revista Professor de Matematica (RPM):

Propriedade 1 - Se d divide a, então dividirá am, para qualquer inteiro m;

Propriedade 2 -  Se d divide a e divide b, então dividirá a + b;

Propriedade 3 - Se d é o máximo divisor comum de a e b, então existem inteiros r e s tais que ar + bs = d.

Vemos que, com base nas duas primeiras propriedades, caso o problema apareça da forma ax + by = c, e, a partir dele, houver solução com x0 e y0 inteiros, sendo d um divisor comum, de a e b, então deverá dividir o elemento c. Portanto temos já, uma condição para que se exista uma solução inteira na equação.

Segundo a terceira propriedade, essa condição já é suficiente para comprovar que há solução, não precisando de outros elementos. Entretanto no caso de d, além de divisor comum, for o máximo divisor, então c = dm, a partir daí, segundo essa propriedade três, existirão inteiros r e s tais que ar + bs = d. Assim, multiplicando-se os membros desta igualdade pelo inteiro m, teremos a (rm) + b (sm) = c, sendo que x = rm  e  y = sm  será a solução procurada.

Concluímos dessa forma, que uma equação diofantina ax + by = c, possui solução inteira, se o MDC de a e b puder dividir c.

Exemplificando:

Aplicando-se o teorema 1, podemos perceber que uma equação diofantina com os elementos 4x + 6y = 9, não possui solução, pois o máximo divisor comum (4 e 6) é 2 e o número 2 não pode dividir 9. O número 4x + 6y, com x e y, sendo inteiros, sempre serão pares, evidentemente, que jamais chegaram a ser 9, não importando a divisão que se faça.

De todo modo, se formos pensar na expressão 8x + 12y = 36, haverá solução, já que o MDC entre 8 e 12 é 4, e 4 divide 36.

Nota: Se o MDC entre o elemento a e b forem primos, então, pode-se afirmar que a equação diofantina sempre tem soluções inteiras, independentemente de qual seja o valor de c.

Cálculo de uma Solução Particular

Observamos, então, no tópico anterior, que para a busca de soluções inteiras de uma equação diofantina, podemos tomar o MDC de a e b como algum elemento primo, preferencialmente o 1, e que ao encontrar as soluções inteiras também se compara com encontrar valores inteiros para r e s tais que ar + bs = 1. Entretanto não é construtiva a prova que temos para se chegar a esses elementos r e s.

Um dos métodos que podemos utilizar, para se alcançar tais números, é aplicar o algoritmo de Euclides, que já conhecemos, ou então realizar o processo das divisões sucessivas para calcular o MDC de a e b. Esse algoritmo será autêntico quando estiver de acordo com as observações abaixo:

1. a) Caso os elementos a e b sejam inteiros, sendo o b > 0, existem inteiros q  e  r, com 0   r < b,  únicos, de forma que  a = bq + r  (esse é o algoritmo da divisão).
2. b) Caso a e b sejam também inteiros, considerando o b > 0,  e, dessa vez a = bq + r,  contendo, 0   r < b. Então o mdc(a,b)=mdc(b,r).   Dessa forma, veremos que o conjunto dos divisores comuns de a e b é similar aos divisores comuns de b e r. Concluímos, então, de modo forçado, que o máximo divisor comum de a e b é igual ao de b e r. E, finalmente, se a = bq + r e g for um divisor comum de a e b (isto é, g divide a e g divide b), então, de   a   bq = r,  segue-se que g divide b e g divide r.  Por fim, g é um divisor comum de b e r.

O oposto também é válido, se o elemento g divide b e r, como a = bq + r, segue-se que g divide a e b.

Agora, demonstraremos, através de exemplo, como encontrar os inteiros r e s, sendo eles ar + bs = 1, citado anteriormente. Para que isso aconteça, consideremos dois números, 32 e 9. Ao aplicarmos o algoritmo de Euclides, no cálculo do máximo divisor comum entre eles, teremos o seguinte resultado:

Pelo algoritmo, podemos resumir as divisões, a partir do esquema abaixo:

32 =  3  x  9 +  5     (A)

9    =  1  x 5  +  4     (B)

5    = 1  x  4  +  1     (C)

e, a partir, da análise da segunda tabela, concluímos que:  

mdc (32,9) = mdc (9,5) = mdc (5,4) = mdc (4,1) = 1.

O próximo passo é combinar de forma que fique conveniente as três expressões (A), (B), (C) e aí, encontraremos os inteiros r e s, sendo que teremos 32r + 9s = 1. Desse modo, nós tiramos da expressão (C), a afirmação  5   1 x 4=1.   De (B), resultou o axioma 4 = 9   1 x 5 que, se jogarmos na expressão acima, ficaria:

5   l x (9   l x 5) = l    ou    5   1 x 9 + 1 x 5 = 1 ou, ainda, de forma mais direta, 2 x 5   1 x 9 = 1.

Por fim, da expressão (A), obtemos 5 = 32   3 x 9 que, assim como na (B), incluiremos na expressão acima, chegando então a:

2 x (32   3 x 9)   1 x 9 =1    ou 2 x 32   7 x 9 = 1

Finalmente, os números que procuramos se fazem presentes, e são o 2 e o 7.

Construção de Todas as Soluções a Partir de Uma

Tendo os coeficientes x0, y0, obteremos uma solução inteira a partir da equação diofantina se a e b forem relativamente inteiros. Portanto a expressão deverá ficar ax0+by0 = c. Veja agora que, se, no primeiro elemento, somarmos e subtrairmos o mesmo número, essa igualdade continuará em vigor. Se quisermos colocar a e b em evidência, deveremos exigir que o número a ser acrescentado seja múltiplo de ab, ou seja teríamos uma escrita na forma abk, sendo o k um elemento inteiro. A partir daí, teríamos que:

Essa expressão, prova que o par (x0 + bk, y0   ak) continua sendo uma equação diofantina. Perceba também que até este momento ainda não utilizamos a hipótese de o máximo divisor comum a e b ser igual a 1.

A pergunta fundamental agora é: será que estas opções são todas as soluções inteiras existentes? Ou poderão existir outras? Para responder isso, faremos uma suposição de que (x0, y0) e (x1, y1) são soluções inteiras da equação, agora sim incluindo o MDC de a e b = 1. Assim teremos:    

ax0 + by0 = c        e        ax1 + by1 = c.

O que resulta em:

a (x1   x0) = b(y0   y1).

Primeiro caso: Se o a = 1, chamaremos de k; o inteiro que resultar em y0   y1 e teremos x0   x1 = bk, isto é, x1 = x0 + bk, sendo que y0   y1 = k, ou seja, y1 = y0   k, que é igual a  y1 = y0   ak,  pois  a = 1. Então, neste caso, qualquer solução (x1,y1) é da forma (x0 + bk, y0  ak), com k inteiro.

Segundo caso: Se o a  1, a não dividirá b,  isso porque a e b  são primos. Então, a divide  y0    y1, ou seja, existe k; inteiro tal que  y0    y1 = ak,  sendo que  y1 = y0    ak.  Mas então a( x1  x0 ) = bak,  e, como  a   0,  vem que  x1   x0 = bk,  ou seja,  x1=x0+bk.

Assim, exibimos um teorema que diz se o par ordenado (x0, y0) de fato for uma solução da equação diofantina ax + by = c, com regra mdc (a, b) = 1, então (x1, y1) será consequentemente solução da equação se, e somente se, existir um inteiro k tal que x1 = x0 + bk   e   y1 = y0 ak.

Preste atenção que a condição de a e b serem primos, não é necessária aqui, para que o x1 e y1 tornem-se soluções da equação diofantina, entretanto, essa regra ainda é importante para garantir que essas sejam todas as soluções da equação proposta.

Exemplificando:

Dada a equação diofantina 143x + 17y = 132, buscaremos as soluções inteiras para ela. De início, colocamos o máximo divisor comum entre (143,17) = 1, portanto, já podemos estabelecer que essa equação terá soluções inteiras. Para se achar, ao menos uma delas, veja que:

143 = 8 x 17 + 7, 17 = 2 x 7 + 3, 7 = 2 x 3 + 1. Logo temos:

l = 7   2 x 3 = 7   2 x [17   2 x 7] = 5 x 7   2 x 17 =

= 5 x [143   8 x 17]   2 x 17 = 5 x 143   42 x 17.

Em que descrevemos:

143 x [5 x 132] + 17 x [ 42 x 132] = 132,

Isto é a solução da equação que se dá por: (x0, y0) = (660, 5544), portanto, todas as demais soluções ainda não encontradas, se darão da mesma forma:    x = 660 + 17k e y =  5544   143k , em que k é um inteiro arbitrário.

As Diferentes Formas de Resolver uma Equação Diofantina

De forma conceitual, para se resolver uma equação diofantina, é necessário encontrar valores correspondentes para as variáveis x e y, que precisam necessariamente ser números inteiros. Uma solução padrão é mais fácil de ser encontrada do que uma integral, exigindo, de quem faz, um processo de inúmeras etapas. Antes de tudo, é preciso encontrar o MDC dos coeficientes dados no problema. Se, caso, conseguir encontrar uma solução integral, de uma equação linear, será mais fácil aplicar a ela um padrão e, assim, identificar inúmeras outras soluções possíveis. A seguir, colocaremos três métodos de resolução das equações, dando a cada um deles, o passo a passo necessário.

Método 1: Preparando a Equação

a) Escreva-a em formato padrão – para uma equação ser linear, não deve ter nenhum expoente maior que 1, em qualquer uma de suas variáveis. O primeiro passo para solucioná-la é escrevê-la de forma padronizada, representada no estilo diofantino ax + bx = c, sendo que a, b e c sempre serão valores inteiros. Em muitos problemas, a equação já estará neste padrão, porém, caso não esteja, é preciso utilizar-se das regras de álgebra para executar essa ordenação, ou partir para uma combinação de termos. Se o problema der, por exemplo, 23x + 4y – 7x = -3y + 15, você pode simplificar essa equação combinando elementos similares até chegar em 16x + 7y = 15.

b) Se possível reduza a equação – após sua equação estar dentro do formato padrão, observe bem os termos de a, b e c. Caso haja, entre eles, algum fator comum, busque uni-los a fim de reduzir a equação. Após reduzir igualmente os três termos, as soluções encontradas também serão válidas para a descrição original. Se os três forem elementos pares, por exemplo, poderá dividi-los e simplificá-los por 2, como segue a demonstração abaixo:

• 42x + 36y = 48 (todos os termos são divisíveis por {\displaystyle 2}2), e depois,
• 21x + 18y = 24 (todos os termos são divisíveis por {\displaystyle 2}3)
• 7x + 6y = 8 (a equação chegou ao formato mais reduzido possível)

c) Determine a impossibilidade de uma solução – para algumas equações, será possível determinar se existe ou não solução possível. Se houver, algum múltiplo comum do lado esquerdo da expressão que não convém com o lado direito, pode ser, neste caso, que a solução não exista. Se a e b forem pares, a soma de ambos os lados também precisa ser par, se não for, é possível também que não se tenha resultados. Por outro lado, se o elemento c for ímpar, aí não existirá solução inteira.

• 2x + 4y = 21 - não possui solução inteira.
• 5x + 10y = 17 - não pode ter solução inteira, uma vez que o lado esquerdo da equação é divisível por 5 {\displaystyle 5}, mas não o lado direito.

Método 2 – Utilizando o algoritmo euclidiano

a) Reaprenda o algoritmo euclidiano – esse sistema consiste em divisões repetidas, em que será usado cada resto como divisor de uma nova conta. O último divisor utilizado será o MDC entre os valores analisados. Os passos, descritos abaixo, demonstram o uso do algoritmo euclidiano na determinação do MDC entre 272 e 36:

• 272 = 7 x 36 + 20 – divida o número maior (272) pelo menor (36) e anote o resto (20);
• 36 = 1 x 20 + 16 – divida o divisor prévio (36) pelo resto (20) e anote o novo resto (16);
• 20 = 1 x 16 + 4 – repita o procedimento, dividindo o divisor (20) pelo resto prévio (16) e anote o novo resto (4);
• 16 = 4 x 4 = 0, Repita o procedimento, dividindo o divisor (16) pelo resto prévio (4), uma vez que o resto agora é 0, conclua que 4 é o MDC dos números originais 272 e 36.

b) Aplique o algoritmo euclidiano aos coeficientes a{\displaystyle {\text{a}}} e b{\displaystyle {\text{b}}} – se a equação já estiver em formato padrão, identifique os coeficientes a e b e realize o cálculo do MDC, pelo algoritmo euclidiano entre esses elementos. A partir daí, determine soluções integrais para a equação linear. Por exemplo 87x + 64y = 3. Os passos a seguir mostrarão como isso ocorre:

87 = 1 x 64 + 23

64 = 2 x 23 + 18

23 = 1 x 18 + 5

18 = 3 x 5 + 3

5 = 1 x 3 + 2

3     = 1 x 2 + 1

2 = 2 x 1 + 0

c) Identifique o máximo divisor comum (MDC) – se o algoritmo euclidiano se suceder para esse par ordenado até a divisão chegar a 1, então, concluiremos, que o MDC entre 87 e 64 é 1. Ou simplesmente dizemos que ambos os números são primos entre si mesmos.

d) Interprete o resultado – após o complemento do algoritmo e a determinação do MDC entre a e b, deveremos comparar os resultados com o valor de c, dado na equação. Se o MDC entre esses dois valores também for divisor, então, essa equação linear terá uma solução integral. Se não for, então, não haverá solução possível. Voltando ao 87x + 64y =3, essa equação terá solução integral, já que seu MDC pode ser igualmente dividido pelo elemento c (3). Se supormos que o MDC fosse 5, aí não poderia haver essa divisão, então, não obteríamos soluções integrais, evidentemente.

Método 3 – Renomeando o MDC para encontrar a solução.

a) Rotule os passos da redução do MDC – neste método, para se encontrar a solução de uma equação linear, será preciso utilizar o trabalho feito no algoritmo euclidiano como suporte em um processo de repetição, sendo que o objetivo é renomear e simplificar os valores. De início, numere os passos da redução do algoritmo para ter um caminho referencial, após isso terá a lógica que se exemplifica abaixo:

Passo 1: 87 = (1 x 64) + 23

Passo 2: 64 = (2 x 23) + 18

Passo 3: 23 = (1 x 18) + 5

Passo 4: 18 = (3 x 5) + 3

Passo 5: 5 = (1 x 3) + 2

Passo 6: 3 = (1 x 2) + 1

Passo 7: 2 = (2 x 1) + 0

{\displaystyle 87x-64y=3}

b) Comece com o último passo contendo um resto – reescreva a equação, para que siga o restante das informações dadas na expressão. Nesse problema, o passo 6 é o último a ter um resto que é o próprio 1. Nesse caso, poderá ser reescrito da seguinte forma:

1 = 3 – (1 x 2).

c) Isole o resto do passo anterior – esse processo pode ser considerado um passo a passo de como ir elevando cada etapa. Todas as vezes, você deverá rever o lado direito da equação e focar nos valores da etapa acima. É possível reavaliar o passo 5, para isolar o resto que se segue, como demonstrado abaixo:

2 = 5 – (1 x 3) ou 2 = 5 -3

d) Faça uma substituição e simplifique – observe que a revisão do sexto passo possui o número 2, e a revisão do quinto passo também é igual a 2. Então teremos que substituir ?a igual? dado do passo 5 para que entre no lugar do 2 no passo 6, como abaixo:

1 = 3 – (1 x 2) – Essa é a revisão do passo 6.

1 = 3 – (5 x 3) – Faça a substituição no lugar do valor 2.

1 = 3 – (5 + 3) – Distribuição do sinal negativo.

1 = 2 (3) – 5 – Simplifique.

e) Repita o processo de substituição e simplificação – caminhando pelos passos do algoritmo euclidiano, inverte-se a forma e repete-se o mesmo procedimento. Após cada etapa, reveja a anterior e substitua o valor do último resultado encontrado. Se a última foi o passo 5, agora refaça o quarto passo, e siga isolando o resto:

3 = 18 – (3 x 5)

Substitua o valor no lugar do 3{\displaystyle 3} na última etapa e simplifique:

1= 2 (18 – 3 x 5) – 5

1= 2 (18) – 6(5) – 5

1= 2 (18) – 7(5)

f) Continue repetindo os passos de substituição e simplificação – esse procedimento seguirá se repetindo, até que se chegue novamente a etapa original do algoritmo euclidiano. O objetivo central, deste processo, é determinar uma equação que seja baseada nos termos 87 e 64, que são os coeficientes originais do problema que estamos exemplificando.

Esse processo se repetirá, passo a passo, até chegar novamente à etapa original do algoritmo euclidiano. A finalidade desse procedimento é determinar uma equação que seja escrita em termos de {\displaystyle 87} 87 e 64{\displaystyle 64}, os coeficientes originais do problema a serem resolvidos. Desse modo, os próximos passos a se seguir são:

1 = 2(18) – 7(5)

1 = 2(18) – 7(23 – 18) – Substituição do passo 3

              1 = 2(18) – 7(23) + 7(18)

              1 = 9(18) – 7(23)

1= 9(64 – 2 x 23) – 7(23) – Substituição do passo 2

              1= 9(64) – 18(23) – 7(23)

              1= 9(64) – 25(23)

1= 9(64) – 25(87 – 64) – Substituição do passo 1

              1= 9(64) – 25(87) + 25(64)

              1= 34(64) – 25(87)

g) Reescreva o resultado em termos dos coeficientes originais – ao voltar para o início, no primeiro passo, do algoritmo euclidiano, perceba que os coeficientes do problema original também retornam. Então, recoloque os números para que se alinhem junto com a primeira equação. Desse modo, a expressão inicial para se resolver é 87x – 64y = 3. Assim, é possível remarcar a última etapa do processo a fim de deixar todos os termos padronizados. É preciso aqui, ter uma atenção especial, principalmente ao 64. Veja que na equação original, é subtraído, entretanto, o algoritmo euclidiano o trata como sendo positivo. Só será possível considerar a subtração, transformando o 34 em um valor negativo. Ficando, então, da seguinte forma nossa equação:

87  -25) – 64(-34) = 1

h) Multiplique o fator necessário para determinar as soluções – veja que o MDC do problema era 1, de tal forma que essa foi a solução exigida. Mas essa solução não representa a real solução do problema proposto, pois originalmente a equação é 87x – 64y = 3. É preciso então, uma multiplicação dos termos da última equação por esse termo, para se chegar a uma real solução, ficando:

87 (-25 x 3) – 64( -34x 3) = 1 x 3

87(-75) – 64(-102) = 3

i) Identifique a solução integral da equação – os elementos que serão multiplicados pelos coeficientes originais representam a solução x e y do nosso problema. Podemos identificar como um par ordenado, (x,y) = (-75, -102).