Prof. simões
Algoritmo estendido de Euclides MDC(a,b)
Aplica-se o Algoritmo de Euclides como uma das maneiras de calcular
o M.D.C. entre dois números inteiros a e b.
O MDC(a,b) = d resulta da combinação linear de a e b, sendo,
a combinação linear, de grande utilidade se a e b são primos entre si.
Exemplo: Calcular o MDC(120,23)
Nota-se que: 120 e 23 são primos entre si pois o único divisor comum = 1 .
MDC(120,23), usando o Algoritmo estendido de Euclides:
Segue-se que:
120 = 5 . 23 + 5 ...... onde: 5 = 1 . 120 - 5. 23
23 = 4 . 5 + 3 ...... 3 = 1 . 23 - 4 . 5
5 = 1. 3 +2 ...... 2 = 1 . 5 - 3
3 = 1. 2 +1 ....... 1 = 1 . 3 - 2
2 = 2. 1 + 0
MDC(120,23) = d = 1
Logo, deve-se procurar escrever, 1 como combinação linear de 120 e 23, ou seja:
a .120 + b . 23, procurando-se identificar, então, a e b , como se segue.
5 = 1 .120 – 5 . 23
3 = 1. 23 – 4 . 5 ................ e, como 5 = 1 . 120 – 5 . 23
3 = 1. 23 - 4(1 .120 – 5 . 23)
3 = -4 .120 + 21.23
2 = 1 .5 – 1 . 3 ................. como 5 = 1 .120 – 5 . 23 e
3 = -4 .120 + 21 . 23
2 = 1(1 . 120 – 5 . 23) - 1(-4 .120 + 21 . 23)
2 = 5 .120 – 26 . 23
1 = 1 . 3 – 1 . 2
1 = 1(-4 .120 + 21 . 23) - 1(5 .120 – 26 . 23)
1 = -9 .120 + 47 . 23
Como: ax + by = MDC(a, b), ou seja: a = -9 e b = 47
Temos, então, que: –9 .120 + 47 . 23 = 1 = d = MDC(120,23)
