Guião para a Sétima Aula Prática de IPL

Delfim F. Marado Torres

23 de Abril de 1999

DIOFANTO

Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.

Cálculo do Máximo Divisor Comum de dois números

É bem sabido que quaisquer dois inteiros não nulos a e b admitem um m.d.c. Vamos examinar um dos métodos de cálculo do m.d.c. chamado algoritmo de Euclides.¹ Admitiremos, para fixar as ideias, que | a| ³ | b|. Procedemos por etapas.

Primeira Etapa.

Divide-se a por b:

a = q₁ b+r₁, 0 £ r₁ < | b| .

Se r₁ = 0, então m.d.c.( a, b) = b. Se r₁ ¹ 0, passamos à

Segunda Etapa.

Divide-se b por r₁:

b = q₂ r₁+r₂, 0 £ r₂ < r₁.

Se r₂ ¹ 0, passamos à etapa seguinte.

Terceira Etapa.

r₁ = q₃ r₂+r₃, 0 £ r₃ < r₂.

Iteramos este processo, repetindo sucessivamente as respectivas operações. Em cada estágio o resto obtido será estritamente inferior ao da etapa precedente, isto é,

| b| > r₁ > r₂ > ¼,

logo, num certo estágio, digamos na k-ésima etapa, onde necessariamente k < | b| , o resto será nulo, quer dizer:

k-ésima Etapa.

r_k-2 = q_k r_k-1.

É fácil de ver que o último resto distinto do zero, a saber r_k-1, será o m.d.c. de a e b que procuramos. De facto, têm lugar as seguintes igualdades:

(1) a

q₁ b+r₁;

(2) b

q₂ r₁+r₂;

(3) r₁

q₃ r₂+r₃;

(k-1) r_k-3

q_k-1 r_k-2+r_k-1;

(k) r_k-2

q_k r_k-1.

Da última destas igualdades decorre que r_k-1 divide r_k-2; da penúltima, dado que r_k-1 divide r_k-1 e r_k-1 divide r_k-2, resulta que r_k-1 divide r_k-3. Assim, passando de cada uma das igualdades à precedente, constatamos finalmente que r_k-1 divide r₂, r_k-1 divide r₁, r_k-1 divide b e r_k-1 divide a. Logo r_k-1 é um divisor comum de a e b. Para mostrarmos que r_k-1 é o m.d.c. de a e b falta-nos mostrar que qualquer divisor comum de a e b divide r_k-1. Suponhamos então que c divide a e c divide b. Então, das igualdades (1) , ( 2) , ¼, ( k-1) , obteremos sucessivamente que c divide r₁, c divide r₂, ¼, c divide r_k-1, provando-se o pretendido.

Examinemos o exemplo com a = 858 e b = 253. Encontremos o m.d.c. destes números, sem decompo-los em factores primos, aplicando o algoritmo de Euclides:

(a) 858

3·253+99;

(b) 253

2·99+55;

1·55+44;

(d) 55

1·44+11;

(e) 44

4·11,

donde o m.d.c.( 858, 253) = 11.

Algumas equações em números inteiros

Um resultado também bem conhecido² é o de que o número d = m.d.c.(a, b) pode ser escrito como uma combinação linear de a e b:

d = s a+t b,

onde s e t são inteiros. O algoritmo de Euclides permite determinar o valor de s e t. Não vamos dar aqui uma demonstração geral deste facto, ilustrando-o simplesmente para o exemplo que acabámos de examinar. Assim, pretendemos encontrar os inteiros s e t que satisfazem a relação

11 = s·858+t·253.

Das igualdades ( d) , ( c) , ( b) e ( a) obtemos, respectivamente:

55+( -1) ·44,

99+( -1) ·55,

253+( -2) ·99,

858+( -3) ·253.

Substituindo na primeira destas igualdades a expressão para 44 da segunda, em seguida, substituindo a expressão para 55 da terceira, etc., obteremos

55+( -1) ·( 99+( -1) ·55) = 2·55+( -1) ·99 =

2·( 253+( -2) ·99) +( -1)·99 = 2·253+( -5) ·99 =

2·253+( -5) ·( 858+( -3) ·253) = ( -5) ·858+17·253.

Logo, s = -5, t = 17.

As igualdades que ocorrem ao se encontrar o m.d.c. de dois números a e b mediante o algoritmo de Euclides permitem, pois, resolver em números inteiros qualquer equação do tipo

d = x a+y b

com d = m.d.c.( a, b) .

Em geral, qualquer equação da forma

(ED) x a+y b = c,

onde a, b e c são números inteiros conhecidos e da qual se procuram as soluções inteiras, denomina-se equação diofantina³ linear com duas incógnitas. A equação é linear, as incógnitas x e y estando na primeira potência. O termo ``diofantina'' provém do facto de serem inteiros os coeficientes e de se procurarem soluções inteiras.

Passemos à análise da existência de soluções da equação (ED) no caso geral. Observemos, antes de tudo, que nem toda a equação deste tipo admitirá uma solução. De facto, suponhamos que os inteiros x = x₀ e y = y₀ satisfazem a equação ( ED) , quer dizer, c = x₀ a+y₀ b. Neste caso, se d = m.d.c.( a, b) , então o facto de d ser divisor comum de a e b resulta que d dividirá ambos os termos à direita nesta igualdade e que, por conseguinte, dividirá c. Daqui decorre a seguinte afirmação.

Para que uma equação do tipo ( ED) admita uma solução em números inteiros, é necessário que o número c seja divisível pelo m.d.c. dos coeficientes a e b.

A equação

9 x+15 y = 7,

por exemplo, não terá solução em números inteiros, 7 não sendo divisível por 3 = m.d.c.( 9, 15) . Por outro lado, uma equação ( ED) , na qual c é divisível por d, admitirá uma solução em números inteiros. Somos mesmo capazes de encontrá-la. De facto, seja c = c^¢ d e sejam s e t dois números inteiros tais que

d = a s+b t.

Então

c = c^¢ d = a ( s c^¢) +b ( t c^¢) ,

isto é, x₀ = s c^¢ e y₀ = t c^¢ constituem uma solução da equação ( ED) .

Resolvamos, a título de exemplo, a equação diofantina

33 = 858 x+253 y.

Mais acima, mostrámos que

11 = 858·( -5) +253·17,

11 sendo o m.d.c. de 858 e 253. Multiplicando a última igualdade por 3, obteremos

33 = 858·( -15) +253·51.

Logo, x = -15 e y = 51 é uma solução da equação 33 = 858 x+253 y. Seria, porém, erróneo pensar que esta solução é única. Mesmo mais. Constata-se que qualquer equação diofantina da forma ( ED) , que admitir uma solução, admitirá uma infinidade delas. A demonstração desta última afirmação sai no entanto fora do âmbito deste trabalho e deixamos a sua análise à consideração do leitor curioso.

Tarefa

Implemente, usando o algoritmo de Euclides acima descrito, o predicado
mdc(N1,N2,M,L)

onde M é o máximo divisor comum de N1 e N2 e L é uma lista de listas com a informação de todas as etapas do algoritmo. Cada etapa, que consiste numa divisão D1 = Q * D2 + R < = > R = D1 - Q * D2, será representada pela lista [R,[-Q,D2],[1,D1]].
Implemente o predicado
diofantina(A,B,C,X,Y),

que recebe três inteiros A, B e C e retorna uma solução X,Y (caso exista) da equação diofantina A*X + B*Y = C, pelo método acima descrito.

Os Dados

Neste problema não existem outros dados para além do conhecimento acima descrito.

Os Resultados

Os predicados mdc(N1,N2,M,L) e diofantina(A,B,C,X,Y) devem produzir resultados consonantes com os exemplos que se seguem.

Exemplo ``mdc''

         ?-mdc(858,253,M,L).
         M =11
         L = [ [ 11,[-1,44],[1,55] ],
               [ 44,[-1,55],[1,99] ],
               [ 55,[-2,99],[1,253] ],
               [ 99,[-3,253],[1,858] ]
             ]

Exemplos ``diofantina''

         ?-diofantina(434,233,3,X,Y).
         X =-153
         Y = 285

         ?-diofantina(858,253,33,X,Y).
         X = -15
         Y =  51

         ?-diofantina(15,9,7,X,Y).
         No

Uma solução

         % Solu\c c\~ao para o problema DIOFANTO
         % por Delfim F. Marado Torres, Fev. 1999


         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %               mdc(N1,N2,M,L)
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %
         % M é o máximo divisor comum
         % de N1 e N2 (supomos ambos estritamente positivos com N1 > N2)
         %
         % O método usado para obter M
         % é o algoritmo de Euclides
         %
         % L é uma lista de listas com a informação
         % de todas as etapas do algoritmo. Cada
         % etapa consiste numa divisão
         %        D1 = Q * D2 + R <=> R = D1 - Q * D2
         % que será representada pela lista
         %        [R,[-Q,D2],[1,D1]]
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         mdc(N1,N2,M,L) :-
           integer(N1),
           integer(N2),
           N1 > N2,
           N2 > 0,
           euclides(N1,N2,M,L).


         euclides(N1,N2,N2,[]) :-
             etapa(N1,N2,_,0).
         euclides(N1,N2,M,L) :-
             etapa(N1,N2,Q,R),
             euclides(N2,R,M,L1),
             concatena(L1,[[R,[-Q,N2],[1,N1]]],L).

         etapa(D1,D2,Q,R) :-
           Q is D1 // D2,
           R is D1 mod D2.

         concatena([],L,L).
         concatena([X|R],L,[X|C]) :-
           concatena(R,L,C).


         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %               diofantina(A,B,C,X,Y)
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         % Dado A, B e C, pretendemos resolver uma equação diofantina da
         % forma
         %               A*X + B*Y = C             (supomos A > B)
         %
         % Se B = mdc(A,B) Entao se B divide C temos solução trivial:
         %               X = 0, Y = C/B
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %%                EXEMPLOS
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% ?- diofantina(434,233,3,X,Y).
         %%    X = -153
         %%    Y = 285
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% ?- diofantina(858,253,33,X,Y).
         %%    X = -15
         %%    Y = 51
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% ?- diofantina(15,9,7,X,Y).
         %%    No
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


         diofantina(A,B,C,X,Y) :-
           A > B,
           mdc(A,B,M,L), !,
           0 is C mod M,
           (
            M = B, L = [], X = 0, Y is C // B ;
            expande(L,[M,[Y1,B],[X1,A]]), Mlt is C // M, X is X1*Mlt, Y is Y1*Mlt
           ).


         expande([L],L).
         expande([[A1,[B1,_],[D1,E1]],[_,[B2,E1],[D2,E2]]|R],L) :-
                 B is B1 * B2 + D1,
                 D is B1 * D2,
                 expande([[A1,[B,E1],[D,E2]]|R],L).

Footnotes:

¹ Este método aparece descrito nos ``Elementos'' de Euclides.

² Ver, por exemplo, o Cap. I, Teorema 3, do livro Divisão Inexata de A. A. Belsky e L. A. Kalujnin, publicado na colecção Iniciação na Matemática da editora MIR.

³ O termo ``diofantina'' vem de Diofanto, matemático grego da antiguidade (III século a. C.) que na sua ``Aritmética'' estudou equações em números inteiros.