MÉTODO TABULAR PARA EXPRESSAR O MDC

Prévia do material em texto

MA14 - Me´todo Tabular para expressar o MDC
Prof. Ulysses Sodre´
Londrina-PR, 24 de setembro de 2012
1 Me´todo Tabular para expressar o MDC de dois nu´meros
Este me´todo foi extraı´do do Cap.1, sec.4, pg. 10-12 de “Algebra & Number Theory”,
de A. Baker, Departament of Mathematics, University of Glasgow, 10/01/2009.
A pa´gina para refereˆncia e´ http://www.maths.gla.ac.uk/˜ajb.
Mudei alguns detalhes para facilitar a explicac¸a˜o do funcionamento do me´todo.
Na resoluc¸a˜o de uma equac¸a˜o diofantina, como por exemplo, 11X +7Y = 58, deve-
mos garantir que existe soluc¸a˜o com (12, 7) = 1|58. Obtemos (11, 7) = 1, usamos o
algoritmo de um tipo de divisa˜o euclidiana:
1 1 1 3
11 7 4 3 1
4 3 1 0
Em geral, os quocientes sa˜o abandonados em detrimento dos restos, mas para ope-
rar com este me´todo, sera˜o utilizados os quocientes destacados para escrever o
ma´ximo divisor comum de dois nu´meros inteiros como uma combinac¸a˜o linear dos
referidos nu´meros.
P0 Monte duas tabelas semelhantes.
(1) Nas duas tabelas, as linhas L1 sa˜o iguais e possuem duas ce´lulas vazias no
inı´cio e os quatro quocientes obtidos acima.
(a) La e´ a segunda linha da primeira tabela, que inicia pelos nu´meros 1 e 0.
(b) Lb e´ a segunda linha da segunda tabela, que inicia pelos nu´meros 0 e 1.
L1 q1 q2 q3 q4
La 1 0
L1 q1 q2 q3 q4
Lb 0 1
Sec¸a˜o 1 Me´todo Tabular para expressar o MDC de dois nu´meros 2
P1 Os nu´meros a1, a2, a3, . . . e b1, b2, b3, . . . nas tabelas, sa˜o obtidas por somas de
nu´meros com produtos de nu´meros destacados (em vermelho) nas tabelas.
L1 q1 q2 q3 q4
La 1 0 a1 a2 a3 a4
L1 q1 q2 q3 q4
Lb 0 1 b1 b2 b3 b4
P2 Para simplificar a nossa vida, criaremos apenas uma tabela, na forma:
L1 q1 q2 q3 q4
La 1 0 a1 a2 a3 a4
Lb 0 1 b1 b2 b3 b4
Os valores a1, a2, a3.a4 e b1, b2, b3, b4 sa˜o obtidos de acordo com a forma apresen-
tada abaixo:
a1 = 1 + 0 × q1
a2 = 0 + a1 × q2
a3 = a1 + a2 × q3
a4 = a2 + a3 × q4
b1 = 0 + 1 × q1
b2 = 1 + b1 × q2
b3 = b1 + b2 × q3
b4 = b2 + b3 × q4
P3 Vamos usar os quocientes obtidos inicialmente e completar a tabela para obter:
L1 1 1 1 3
La 1 0 1 1 2 7
Lb 0 1 1 2 3 11
P4 Os quatro u´ltimos nu´meros obtidos formam uma matriz quadrada de ordem
2, cujo determinante e´ igual a 1, isto e´: 1 = 11 × 2 − 7 × 3. Multiplicando esta
igualdade por 58, obtemos
58 = 11(116) + 7(−174)
X = 116 e Y = −174 e´ a soluc¸a˜o minimal de 11X + 7Y = 58. A soluc¸a˜o geral e´:
Xn = 116 + 7n, Yn = −174− 11n (n ∈ Z)
1. Resolvemos a equac¸a˜o 8X+13Y = 27, reescrevendo na forma 8X + 13Y − 26 = 1.
Tomamos x = X e y = Y − 2 para obter a equac¸a˜o 8x+ 13y = 1.
1 1 1 1 2
13 8 5 3 2 1
5 3 2 1 0
L1 1 1 1 1 2
La 1 0 1 1 2 3 8
Lb 0 1 1 2 3 5 13
ProfMat - MA14 - Me´todo Tabular para expressar o MDC - Ulysses Sodre´ - Matema´tica - UEL - 2012
Sec¸a˜o 1 Me´todo Tabular para expressar o MDC de dois nu´meros 3
Os quatro u´ltimos nu´meros obtidos formam uma matriz quadrada, com deter-
minante -1, isto e´, −1 = 13 × 3 − 8 × 5. Multiplicando esta igualdade por -1,
obtemos
1 = 8(5) + 13(−3)
Assim, x = 5 e y = −3 e´ a soluc¸a˜o minimal de 8x + 13y = 1 e voltando a`
varia´veis originais, X = 5 e Y = −1 e´ a soluc¸a˜o minimal de 8X + 13Y = 27.
A soluc¸a˜o geral de 8X + 13Y = 27 e´
Xn = 5 + 13n, Yn = −1− 8n (n ∈ Z)
2. Resolvemos a equac¸a˜o 8X+13Y = 23, escrevendo-a como 8X−8+13Y −13 = 2.
Tomando x = X − 1 e y = Y − 1, obtemos a equac¸a˜o 8x+ 13y = 2.
1 1 1 1 2
13 8 5 3 2 1
5 3 2 1 0
L1 1 1 1 1 2
La 1 0 1 1 2 3 8
Lb 0 1 1 2 3 5 13
Como antes, obtemos 1 = 8(5) + 13(−3) e multiplicando por 2, obtemos
2 = 8(10) + 13(−6)
x = 10 e y = −6 e´ a soluc¸a˜o minimal de 8x + 13y = 2. Voltando a` varia´veis
originais, temos que X = 11 e Y = −5 e´ a soluc¸a˜o minimal de 8X + 13Y = 23.
A soluc¸a˜o geral de 8X + 13Y = 23 e´
Xn = 1 + 13n, Yn = −5− 8n (n ∈ Z)
3. Resolver a equac¸a˜o 11X + 9Y = 3. Esta equac¸a˜o tem soluc¸a˜o pois (11, 9) = 1|3.
1 4 2
11 9 2 1
2 1 0
L1 1 4 2
La 1 0 1 4 9
Lb 0 1 1 5 11
Os u´ltimos quatro nu´meros obtidos formam uma matriz quadrada com deter-
minante e´ -1, isto e´, −1 = 11(4) − 9(5). Multiplicando esta igualdade por -3,
obtemos
3 = 11(−12) + 9(15)
Assim, X = −12 e Y = 15 e´ a soluc¸a˜o minimal de 11X + 9Y = 3 e a soluc¸a˜o
geral de 11X + 9Y = 3 e´
Xn = −12 + 9n, Yn = 15− 11n (n ∈ Z)
ProfMat - MA14 - Me´todo Tabular para expressar o MDC - Ulysses Sodre´ - Matema´tica - UEL - 2012
	Método Tabular para expressar o MDC de dois números