(3.8) (3.9) '' ' 18 mismos elementos, d será un divisor de d ' . Ahora, según el teorema 3.1, resulta que d y d’ están asociados. La demostración del teorema siguiente es análoga con la del teorema anterior. Teorema 3.11: Si los elementos a y b están asociados con los elementos a ' y b ' , respectivamente, y m ?m '? es un mínimo común múltiplo de a y b (de a ' y b ' ), entonces m y m ' están asociados. El máximo común divisor y el mínimo común múltiplo de n elementos del semigrupo G se define de la misma manera que en el caso de dos elementos. Definición 3.9: Si a1 , a2 , ? an ? G , d ? G es un máximo común divisor de a1 , a2 , ? an si d es un divisor común de estos elementos y cualquier otro divisor común de ellos es un divisor de d . Definición 3.10: Si a1 , a2 , ? an ? G , m ? G es un mínimo común múltiplo de a1 , a2 , ? an si m es un múltiplo común de estos elementos y cualquier otro múltiplo común es un múltiplo de m . Obviamente, como en el caso de dos elementos, el máximo común divisor y el mínimo común múltiplo de n elementos son determinados hasta un factor invertible. Así, (a1 , a2 , ? an ) y [ a1 , a2 , ? an ] , designarán un máximo común divisor y un mínimo común múltiplo cualquiera de los elementos a1 , a2 , ? an respectivamente. Teorema 3.12: Si n ? N ? ?0,1? y dos elementos cualesquiera del semigrupo G tienen máximo común divisor, entonces (a1 , a2 , ? an ) y [ a1 , a2 , ? an ] , existen cualesquiera que sean a1 , a2 , ? an ? G . Demostración: Primero, si dos elementos cualesquiera de G tienen máximo común divisor, entonces, según el teorema 3.9, tienen también mínimo común múltiplo. Si 2 ? k ? n ? 1 , sean d k y mk definidos por recurrencia de la manera siguiente: d 2 ? ?a1 , a2 ? ; d k ?1 ? ?d k , ak ?1 ? m2 ? ?a1 , a2 ? ; mk ?1 ? ?mk , ak ?1 ? De (3.8) resulta que a1 Dd 2 , di Dd n y ai Ddi , donde i ? ?2 , n ?. Por tanto d i Dd n , cualquiera que sea i ? ?1, n ? . Si d n' es un divisor común cualquiera de a1 , a2 , ? an , entonces se puede demostrar por recurrencia: di Dd n ?2 ? i ? n ?1? y an Dd n ? dn Dd n , y por tanto d n es un máximo común divisor de a1 , a2 , ? an . De manera análoga resulta que mn es un mínimo común múltiplo de a1 , a2 , ? an . Si sabemos calcular el máximo común divisor y el mínimo común múltiplo de dos elementos, entonces (3.8) y (3.9) permiten calcular el máximo común divisor y el mínimo común múltiplo de n elementos y este proceso es fácilmente programable. Evidentemente, una permutación de los elementos a1 , a2 , ? an entre si cambiaría los resultados solo en un factor invertible. Definición 3.11: a ? G es un elemento irreducible si no es invertible y no tiene otros divisores que los elementos invertibles o los elementos asociados con a . Definición 3.12: p ? G es un elemento primo si no es invertible y a .b D p ? aDp ó bDp . Teorema 3.13: Cualquier elemento primo es irreducible. En efecto, si p ? a .b , entonces de pDp resulta que a.b D p y así tendremos a D p ó b D p , lo que implica que o bien a o bien b está asociado con p . Si a ?b? está asociado con p entonces b ?a ? es un elemento invertible. La recíproca de este teorema no es verdadera. Teorema 3.14: Si a es un elemento irreducible del semigrupo G y a no es un divisor de b , entonces a y b son primos entre sí. Demostración: Al no ser a un divisor de b , ningún elemento asociado con a puede ser un divisor de b .
19 Sea ahora d un divisor común de a y b . Al ser d un divisor del elemento irreducible a , d es o bien un elemento invertible o bien es un elemento asociado con a . Pero, teniendo en cuenta que d es también un divisor de b , d no puede estar asociado con a , ya que a no es un divisor de b . Entonces, cualquier divisor común d de a y b es un elemento invertible. Por consiguiente, a y b son primos entre sí. Teorema 3.15: Si dos elementos cualesquiera del semigrupo G tienen máximo común divisor, entonces cualquier elemento irreducible es un elemento primo. Demostración: Si c es un elemento irreducible y a.b D c , entonces, según el teorema 3.13, de la falsedad de aDc resultaría que el elemento neutro e es un máximo común divisor de los elementos c y a . Según el teorema 3.8, b ? b . e es un máximo común divisor de c . b y a.b y, dado que c es un divisor común de c . b y a . b , resulta que c es un divisor de b . Teorema 3.16: Dos elementos a y b irreducibles y no asociados son primos entre sí. Demostración: El elemento a no es un divisor de b puesto que al ser b un elemento irreducible, b ? a . q sería posible solo para q invertible y en este caso a y b estarían asociados. De esta manera, el teorema 3.16 es consecuencia del teorema 3.14. Teorema 3.17: Dos elemento primos no asociados a y b son primos entre si. Demostración: Si a y b son dos elementos primos entre sí pero no están asociados, entonces, según el teorema 3.13, los elementos a y b son irreducibles y no asociados. Así, el teorema 3.17 es consecuencia del teorema 3.16. Teorema 3.18: Si el elemento a está asociado con un elemento irreducible b entonces a es irreducible. Demostración: En efecto, b ? a.u , donde u es un elemento invertible. Suponiendo que b no es irreducible se podría escribir que b ? q . r , donde q y r no son invertibles y por tanto, tampoco están asociados con b . Así resultaría que a ? b .u ?1 ? q . r .u ?1 El elemento r .u ?1 no puede ser invertible puesto que en este caso r sería también invertible. De esta manera, q es un divisor no es invertible de a y tampoco está asociado con a , es decir, a no es irreducible. La contradicción obtenida demuestra que b debe ser irreducible. Teorema 3.19: Un elemento asociado con un elemento primo es primo. Demostración: Si p es un elemento primo y p ' ? p .u , donde u es un elemento invertible, supongamos que a .b D p ' . Entonces, a .b ? p .u . q Dado que p es un elemento primo, resulta que aDp ó bDp , es decir aDp ' ó bDp ' . §. 4. Divisibilidad en el conjunto de los números naturales. Sea N el conjunto de los números naturales. Con respecto la multiplicación, N ? ?0? es un semigrupo conmutativo con el elemento neutro 1, donde se cumple la regla de simplificación. Así, en el semigrupo ?N ? ?0? , .? quedarán válidas todas las consideraciones del párrafo anterior. El número 1 siendo el único elemento invertible del semigrupo ?N ? ?0? , .?, dos elementos de este semigrupo no pueden tener más de un máximo común divisor o más de un mínimo común múltiplo. La estructura algebraica de N es mucho más compleja que la de un semigrupo. En N se definen tres leyes de composición internas: la adición, la multiplicación y una sustracción no siempre posible. ?N , .? es un semigrupo multiplicativo con el elemento neutro 1 y ?N , ? ? es un semigrupo aditivo con el elemento neutro 0. La multiplicación es distributiva respecto la adición y la sustracción. Finalmente, existe en N una relación de orden respecto al cual N queda totalmente y bien ordenado. Esto quiere decir que dos elementos cualesquiera de N son comparables y que cualquier subconjunto no vacío de N tiene un elemento más pequeño. Estas circunstancias permiten demostrar gran cantidad de teoremas sobre la divisibilidad en N que no se podrían formular o demostrar con los medios disponibles en el semigrupo ?N , .? . Teorema 4.1: Si d ? N es un divisor común de a, b ? N , entonces d es un divisor de a ? b . En efecto, de
20 a ? d .a1 y b ? d .b1 , resulta que a ? b ? d . a1 ? d .b1 ? d . ?a1 ? b1 ? Teorema 4.2: Si d ? N es un divisor de a ? N , entonces d es un divisor de a.b , cualquiera que sea b ? N . En efecto, puesto que a ? d .a1 , a .b ? ?d . a1 ?.b ? d . ?a1 .b ? Teorema 4.3: Si a, b, c ? N , a ? b ? c y d ? N es un divisor de a y b , entonces d es un divisor de c . En efecto, de a ? d .a1 , b ? d .b1 y a ? b ? c resulta que d . a1 ? d .b1 ? c , y puesto que a ? b ? a1 ? b1 , tendremos c ? d . ?a1 ? b1 ? Teorema 4.4: Si a, b ? N y b ? 0 , entonces existen q, r ? N tales que a ? b . q ? r y 0 ? r ? b Demostración: Si a ? b , entonces Si a ? b , entonces Si a ? b , sea a ? b . 0 ? a , donde a ? b a ? b .1 ? 0 , donde 0 ? b M ? ?n / n ? N , a ? b . n ? ? N . Puesto que b ? 0 , b ? 1 ? ? , donde ? ? 0 . Entonces b . ?a ? 1? ? a ? ? . ?a ? 1? ? a , y así ?a ? 1? ? M . Por tanto, M no es el conjunto vacío. Puesto que cualquier subconjunto no vacío de N posee un elemento más pequeño, sea n0 el elemento más pequeño de M. Dado que a ? b y n0 ? 0 , resulta que n0 ? 1 . Si se pone q0 ? n0 ? 1 , entonces q0 ? M y, por consiguiente a ? b .q0 , es decir a ? b . q0 ? 0 . La desigualdad a ? b . q0 ? b es imposible puesto que esto implicaría a ? b .n0 . Así pues a ? b . q0 ? r , donde 0 ? r ? b . Observación 4.1: Si a ? N , el máximo común divisor de a y 0 es a , puesto que a es un divisor común de a y 0, y cualquier divisor común de a y 0 es un divisor de a . Observación 5.2: Si a ? N , el mínimo común múltiplo de a y 0 es 0 puesto que 0 es un múltiplo común de a y 0, y cualquier múltiplo de a y 0 es cero (por tanto un divisor de 0). Teorema 4.5: Dos elementos cualesquiera de ?N , .? tienen máximo común divisor. Demostración: Teniendo en cuenta la observación (4.1), es suficiente demostrar el teorema para a, b ? N ? ?0?. Según el teorema 5.4, existirán q1 , r1 ? N tales que a ? b . q1 ? r1 y r1 ? b . Si r1 ? 0 , existirán q2 , r2 ? N tales que b ? r1 . q2 ? r2 y r2 ? r1 . Si r2 ? 0 , existirán q3 , r3 ? N tales que r1 ? r2 . q3 ? r3 y r3 ? r2 . Si r3 ? 0 , se continúa el proceso anterior. No obstante, este proceso no puede continuarse indefinidamente puesto que en el caso contrario se llegaría a una sucesión de números naturales estrictamente decreciente e infinita: b, r1 , r2 , r3 , ? , lo que es imposible, al existir solo un número finito de números naturales menores que b . Suponiendo que rn?1 es el primer resto nulo, tendremos: a ? b . q1 ? r1 b ? r1 . q2 ? r2
21 r1 ? r2 . q3 ? r3 …………… rn?2 ? rn?1 . qn ? rn rn?1 ? rn . qn?1 . (4.1) Entonces rn es divisor de rn ?1 y, según el teorema 4.1, rn será también divisor de rn?1 . q . Al ser rn divisor común de rn y rn?1 . qn , según el teorema 4.1, rn será divisor también de rn ? 2 . A continuación, al ser rn divisor común de rn ?1 y rn ? 2 , resultará que rn es divisor de rn?3 y, repitiendo éste razonamiento un número finito de veces, se llega a la conclusión de que rn es divisor común de a y b . Al revés, si d ? N es divisor común de a y b , entonces, según los teoremas 4.2 y 4.3, d será divisor de r1 . Al ser d divisor común de b y r1 , el mismo razonamiento conduce a la conclusión de que d es un divisor de r2 . Repitiendo este razonamiento de un número finito de veces, resultará que d es divisor de rn . De esta manera, rn es divisor común de a y b , y cualquier divisor común de a y b es un divisor de rn , por tanto, rn es el máximo común divisor de a y b . Al demostrar el teorema 4.5, no solo se ha demostrado la existencia del máximo común divisor en ?N , .? sino se ha encontrado también el método práctico para su cálculo. Este método se expresa por las fórmulas 4.1 y se llama el algoritmo de Euclides. Teorema 4.6: Dos elementos cualesquiera de ?N , .? tienen mínimo común múltiplo. Demostración: Teniendo en cuenta la observación 4.2, es suficiente demostrar el teorema para a, b ? N . Según el teorema 4.5, dos elementos cualesquiera de N ? ?0? tienen máximo común divisor y entonces el teorema 2.9 garantiza la existencia del mínimo común múltiplo de dos elementos cualesquiera de N ? ?0?. Observación 4.3: Al ser 1 el único elemento invertible en el semigrupo ?N , .? , el máximo común divisor y el mínimo común múltiplo de dos elementos de N son únicos, y de 2.9 resulta que ?a , b?.?a , b? ? a .b , , cualesquiera que sean a, b ? N . Cuando los números x e y no son demasiado grandes, dentro de un programa Visual-Basic, el máximo común divisor d podría hallarse efectuando la instrucción d ? mcd ?x, y ? , donde la función mcd se ha definido de la manera siguiente: Public Function mcd(ByVal a As Double, ByVal b As Double) As Double Dim a1 As Double, b1 As Double, c1 As Double Dim q As Double, r As Double a1 = a: b1 = b If a1 < b1 Then c1 = a1: a1 = b1: b1 = c1 End If r=1 Do Until r = 0 q = a1 / b1: r = a1 – b1 * Int(q) If r <> 0 Then a1 = b1: b1 = r End If Loop mcd = b1 End Function Naturalmente, el programa tiene que asegurar que los números x e y son enteros. En Visual-Basic existe la instrucción a ? b mod c . Esto quiere decir que el resto de la división de a entre c es b . Utilizando esta instrucción, la función mcd se podría construir también de la manera siguiente: Public Function mcd(ByVal a As Double, ByVal b As Double) As Double Dim a1 As Double, b1 As Double, c1 As Double, r as Double
22 a1 = a: b1 = b If a1 < b1 Then c1 = a1: a1 = b1: b1 = c1 End If r=1 Do Until r = 0 r=a1 mod b1 If r <> 0 Then a1 = b1: b1 = r Loop mcd = b1 End Function Para calcular el mínimo común múltiplo m de dos números naturales x e y, según la observación 4.3, se podría proceder de la manera siguiente: d ? mcd ?x, y ? y m ? ?x / d ? ? y . La codificación de este cálculo es la siguiente: Public Function mcm(ByVal a As Double, ByVal b As Double) As Double Dim d As Double, m As Double, a1 as double d = mcd(a,b):a1=a/d:m=a1*b mcm = m End Function Si se trata calcular el máximo común divisor o el mínimo común múltiplo de números naturales grandes se pueden utilizar las funciones MaxComDiv y MinComMult , expuestas en la monografía: Operaciones con números enteros largos. Sin embargo, aquí se exponen también las versiones más sencillas siguientes: Public Function mcdNg(ByVal a As String, ByVal b As String) As String Dim a1 As String, b1 As String, c1 As String Dim q As String, r As String, n As Integer Dim rr() As String, x(2) As String, dif As String a1 = a: b1 = b: n = 14 x(1) = a1: x(2) = b1: dif = Restar(x(), n) If Left$(dif, 1) = "-" Then c1 = a1: a1 = b1: b1 = c1 End If r = "1" Do Until r = "0" Or r = "-0" x(1) = a1: x(2) = b1: rr() = DivisionEuclidea(x(), n) q = rr(1): r = rr(2) If r <> "0" Then a1 = b1: b1 = r End If Loop mcdNg = b1 End Function Public Function mcmNg(ByVal a As String, ByVal b As String) As String Dim n As Integer, x(2) As String, d As String Dim rr() As String, pr As String n = 7: x(1) = a: x(2) = b: d = mcdNg(a, b) x(1) = a: x(2) = b: pr = Multiplicar(x(), n) x(1) = pr: x(2) = d rr() = DivisionEuclidea(x(), 30) mcmNg = rr(1) End Function Puesto que dos números naturales siempre tienen máximo común divisor, según los teoremas 4.13 y 4.15, los números primos coinciden con los números irreducibles. Así, para averiguar que un número natural n es primo, hay que demostrar que este número no tiene otros divisores que 1 y n . Esto se podría hacer dividiendo el número n sucesivamente con los números naturales situados entre 2 y n ? 1 , ambos inclusive. Si al efectuar estas divisiones, en cierto momento la división es exacta, el número no es primo. En el caso contrario, el número será primo. El teorema siguiente reducirá considerablemente el número de las divisiones necesarias, para poder decidir si un número es primo o no.
| Página siguiente |