ALGORITMO DE ULICES

Algoritmo de Euclides.

El máximo común divisor de dos enteros puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay un proceso más eficiente que utiliza repetidamente el algoritmo de la división. Este método se llama algoritmo de Euclides.

El algoritmo de Euclides se describe de la forma siguiente: Dados dos enteros a y b cuyo máximo común divisor se desea hallar, y asumiendo que a b > 0, (El método funciona también si a y b son negativos). Basta trabajar con los valores absolutos de estos números, debido a que M.C.D (|a|, |b|) =M.C.D (a,b) se siguen los siguientes pasos:

a) Se usa el algoritmo de la división para obtener a = q1b + r2 con

0  r1 < b. Si r1 = 0, entonces ba y M.C.D.(a, b) = b.

b) Si r1  0 se divide b por r1 y se producen enteros q2y r2 que satisfacen b =q2 r1 + r2 con 0 r2 < r1. Si r2 = 0 el proceso termina y M.C.D.(a, b) = r1.

c) Si r2  0 se procede a dividir r2 por r1 obteniendo r1 = q3 r2 + r3 con 0 r3< r2.

d) Este proceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia b > r1 > r2 > .....  0 no puede haber más de b enteros. Es decir, el proceso es finito.

e) En estas circunstancias, el máximo común divisor de a y b no es más que el último residuo no cero del proceso anterior.

Esto lo garantiza la aplicación reiterada del siguiente teorema.

8.7.1 Teorema.Sí a y b son enteros positivos con a  b y si a = qb  r entonces M.C.D.(a, b) = M.C.D.( b, r ).

Demostración

Sea d= M.C.D.(a, b). Luego da y db. De donde d(aqb) por teorema 2.2.3 y 2.2.4. Como a  qb = r, se tiene que dr. Luego d es divisor común de b y r.

Por otra parte, sea c un divisor común de b y r, luego c(qb + r) por teorema 2.2.2 y 2.2.3. Como qb + r = a, entonces ca. De lo anterior tenemos que c es un divisor común de a y b.

Como d = M.C.D.(a, b) se tiene que c d. Luego d = M.C.D.(b, r).

Ejemplo 30.

Halle M.C.D.(12.378, 3.054).

12.378 = 43.054 + 162

3.054 = 18162 + 138

162 = 1138 + 24

138 = 524 + 18

24 = 118 + 6

18 = 36 + 0

Luego M.C.D.(12.378, 3.054) = 6 que es el último residuo no cero.

Ejemplo 31.

Como M.C.D.(12.378, 3.054) = 6 podemos utilizar el ejercicio anterior para encontrar enteros x y y que cumplan la condición: 6 = 12.378x + 3.054y.

6 = 24  18

= 24  (138  524)

= 624  138

= 6(162  138)  138

= 6162  7138

= 6162  7(3.054  18162)

= 132162  73.054

= 132(12.378  43.054)  73.054

= 13212.378 + (535) 3.054

Luego x= 132; y = 535

La notación científica (o notación índice estándar) es una manera rápida de representar un número utilizando potencias de base diez. Esta notación se utiliza para poder expresar muy fácilmente números muy grandes o muy pequeños.

Los números se escriben como un producto:

siendo:

un número real mayor o igual que 1 y menor que 10, que recibe el nombre de coeficiente.

un número entero, que recibe el nombre de exponente u orden de magnitud.

La notación científica utiliza un sistema llamado coma flotante, o de punto flotante en países de habla inglesa y en algunos hispanohablantes.

Historia

Arquímedes, el padre de la notación científica.

El primer intento de representar números demasiado grandes fue emprendido por el matemático y filósofo griego Arquímedes, descrito en su obra El contador de Arena en el siglo III a. C. Ideó un sistema de representación numérica para estimar cuántos granos de arena existían en el universo. El número estimado por él era de 1063 granos. Nótese la coincidencia del exponente con el número de casilleros del ajedrez sabiendo que para valores positivos, el exponente es n-1 donde n es el número de dígitos, siendo la última casilla la Nº 64 el exponente sería 63 (hay un antiguo cuento del tablero de ajedrez en que al último casillero le corresponde -2 elevado a la 63- granos).

A través de la notación científica fue concebido el modelo de representación de los números reales mediante coma flotante. Esa idea fue propuesta por Leonardo Torres Quevedo (1914), Konrad Zuse (1936) y George Robert Stibitz (1939).

Escritura

• 100 = 1

• 101 = 10

• 102 = 100

• 103 = 1 000

• 104 = 10 000

• 105 = 100 000

• 106 = 1 000 000

• 107 = 10 000 000

• 108 = 100 000 000

• 109 = 1 000 000 000

• 1010 = 10 000 000 000

• 1020 = 100

...