Teoría de la Divisibilidad (página 2)

i u INSSB Teor´a de la Divisibilidad Monograf´ia las propiedades de los n´meros enteros para encontrar otras propiedades. 8

o o i o u o o u o u u u u o ia Cap´itulo 3 EL ESTUDIO DE LA DIVISIBILIDAD (Fundamento te´rico) 3.1. Problema El problema detectado es, que se requiere demostrar o describir el algoritmo de la divisi´n, es as´ que nos planteamos en la presente investigaci´n descriptiva: ¿Es posible hallar y/o demostrar la divisibilidad de un n´mero entero hacia otro entero? Nos planteamos la interrogante a partir de lo siguiente: Es claro que existe un Algoritmo de la divisi´n “a = bq +r”, donde la divisi´n de un n´mero por otro es exacta o inexacta, pero s´lo para un n´mero determinado, pero no tenemos un criterio general de la divisibilidad de un n´mero, donde el n´mero es divisible por alg´n otro. Luego, a partir de una investigaci´n descriptiva, recogiendo informaci´n, analizando llegaremos a exponer los resultados a que llegar´ este estudio de la Teor´ de la Divisibilidad. 9

i a o o i o o o o INSSB 3.2. 3.2.1. Teor´a de la Divisibilidad Consideraciones preliminares Propiedades B´sicas de (+, *) Monograf´ia En los enunciados que siguen sean a, d, c y d elementos cualesquiera de Z Propiedades de la igualdad Re?exividad : a = a para todo a. Simetr´ia: Si a = b, entonces b = a Transitividad : Si a = b y b = c, entonces a = c. Propiedades de la suma y de la multiplicaci´n Bien de?nida: Si a = b y c = d, entonces a + c = b + d y a × c = b × d. Cerrada: a + b ? Z y a × b ? Z. Conmutatividad : a + b = b + a y a × b = b × a. Asociatividad : (a + b) + c = a + (b + c) y (a × b) × c = a × (b × c). Identidad : Existe un elemento 0 tal que a + 0 = 0 + a = a; existe un elemento 1 tal que a × 1 = 1 × a = a. Inverso: Para cada a existe un elemento -a tal que a + (-a) = (-a) + a = 0. Cancelaci´n: Si a × c = b × c cuando c = 0, entonces a = b. Distributividad : a × (b + c) = (a × b) + (a × c); (b + c) × a = (b × a) + (c × a). Propiedades de la desigualdad (a < b ? b > a) Tricotom´a: Para cada par de elementos a y b, s´lo uno de los siguientes enunciados es verdadero: a < b, a = b, ´ b < a. Suma: Si a < b, entonces a + c < b + c Multiplicaci´n:Si a < by c > 0, entonces a × c < b × c. Transitividad: Si a < b y b < c, Entonces a < c Muchos de los teoremas pueden ser demostrados c´mo consecuencias de las propiedades 10

i a o a o io u a ia u u u i ia ia i a u e a o INSSB Teor´a de la Divisibilidad Monograf´ia b´sicas de la igualdad, suma y multiplicaci´n; entre ellos est´n los siguientes: Propiedad del cero de la multiplicaci´n:a × 0 = 0 Producto cero: Si a × b = 0, entonces a = 0 o b = 0 Principio del buen orden (P.B.O.) Todo subconjunto no vac´ de los enteros (Z+ ) positivos tiene un elemento m´inimo. El principio del buen orden nos garantiza que cualquier subconjunto del conjunto de los enteros que contiene solo n´meros positivos, contiene un entero positivo menor menor que todos los dem´s. Por ejemplo, el conjunto de los enteros positivos pares tiene un menor elemento, el 2. Sea el subconjunto S ? Z+ ? ?a ? S : a = s; ?s ? S Obs: El axioma no es valido en todo Z+ porque no puede haber un entero negativo menor. El axioma no es valido en Q 3.3. Divisibilidad Divisibilidad, es parte de la teor´ de los n´meros que estudia las condiciones que debe reunir un numeral para ser divisible entre otro y las consecuencias que de este hecho se derivan. “El estudio de las propiedades de los n´meros enteros positivos es el objetivo central de la teor´ia de n´meros: Teor´a Elemental, Teor´ Anal´itica, Teor´ Algebraica ”(De oliveira, Plinio; p. 2; 2000) En esta monograf´a nos limitamos a la parte elemental, donde se presenta demostraciones b´sicas, que seg´n Plinio de Oliveira son necesarias para el estudio de las partes Anal´itica y Algebraica, como tambi´n para las dem´s ramas de las matem´ticas. Estudiaremos las propiedades elementales de la divisibilidad en el conjunto de los enteros, siendo el algoritmo de la divisi´n el enunciado mas importante, pues a partir del cual, 11

i u a u u u u u u o ´ i u i INSSB Teor´a de la Divisibilidad Monograf´ia podremos pasar a estudiar los N´meros Primos, el MCD (M´ximo com´n divisor), adem´s del algoritmo euclidiano, para ?nalmente llegar a Los Criterios de divisibilidad 3.3.1. Divisibilidad entre n´meros naturales Calcular el cociente 12:3 o 12/3, o dividir 12 por 3, signi?ca hallar un n´mero tal que da resultado 12 si se multiplica por tres. Entonces 12:3=4 puesto que 12=4·3 y en general a:b=c signi?ca que a=c·b. En palabras, y con referencia a n´meros naturales, tenemos: Dados dos n´meros naturales a y b llamados respectivamente dividendo y divisor, se llama cociente a:b o a/b a un n´mero c, si existe, tal que da como resultado el dividendo si se lo multiplica por el divisor: a=c·b. 3.3.2. Algoritmo de la divisi´n Teorema. Sea a, b enteros donde b > 0 entonces existen unicos enteros q y r tal que a = b · q + r, 0 = r < b Dem. Sean a,b enteros ?jos con b = 0. Consideremos todos los enteros de la forma a – bx, donde x ? Z. Primero mostraremos que algunos de estos enteros deben ser no negativos. Hay dos posibilidades: 1. Si a = 0, entonces a – b · 0 = a = 0. As´ que a – bx es no negativo para x = 0 en este caso. 2. Si a < 0, entonces -a > 0, ya que b es un entero positivo, debemos tener b = 1. multiplicando esta ultima desigualdad por el n´mero positivo -a, muestra que b(-a) = -a, o equivalente, a – ba = 0. As´ que a – bx, es no negativo cuando x = a en este caso. 12

i u i o i o i ´ i ´ u e o o o i INSSB Teor´a de la Divisibilidad Monograf´ia Luego el conjunto S de todos los enteros no negativos de la forma a – bx, con x ? Z, es no vac´io. Por el principio del buen orden, S contiene un elemento m´inimo llamemoslo r. Ya que r ? S, r es de la forma a – bx para que alg´n x, digamos x = q. As´ que hemos encontrado q y r tal que: r = a – bq, ´ equivalentemente, a = bq + r. Como r ? S, sabemos que r = 0. Ahora mostraremos que r < b. Supongamos lo contrario, que r = b, entonces r – b = 0 , as´ que: 0 = r – b = (a – bq) – b = a – b(q + 1). Ya que a – b(q + 1) es no negativo, es un elemento de S por de?nici´n. Pero como b es positivo, se tiene que r – b < r. As´ que a – b(q + 1) = r – b < r La ultima desigualdad establece que a – b(q + 1) es un elemento de S y menor que r, el menor elemento de S. Esto es una contradicci´n, as´ que se puede tener que r < b. Luego encontramos enteros q y r tal que a = bq + r y 0 = r < b. Para completar la prueba, debemos mostrar que q y r son unicos con esta propiedad (Esto es lo que “´nico´´ signi?ca en la proposici´n del teorema). Para hacer esto, supongamos que para algunos enteros q1 y r1 , tambi´n tenemos a = bq1 + r1 , con 0 = r1 < b, entonces probamos que q = q1 y r = r1 . Es claro que ´ r = r1 ´ r1 = r, sin perder generalidad consideramos r = r1 . Usando sustracci´n tenemos: a = bq + r -a = -bq1 + (-r1 ) 0 = bq – bq1 + r – r1 As´ tenemos: bq1 – bq = r – r1 b(q1 – q) = r – r1 13

i ´ o u i i e ´ i o i o o u INSSB Teor´a de la Divisibilidad Monograf´ia Esta ultima ecuaci´n dice que r – r1 es un entero m´ltiplo de b, pero b > 0 y r – r1 = 0 (ya que r = r1 ), y as´ q1 – q debe ser un entero no negativo . Luego r – r1 es uno de estos: 0b, 1b, 2b, 3b, …, etc. Pero 0 = r1 = r < b, as´ que la diferencia r – r1 es tambi´n menor estricto que b, ya que 0b < 1b < 2b < 3b < …, la unica posibilidad es que r – r1 = 0b = 0. Luego r = r1 . Finalmente, ya que b(q1 – q) = r – r1 = 0 y b > 0, debemos tener q – q1 = 0, as´ que q = q1 . Ejercicios: 1. Sea n ? Z+ , probar que a y c dejan el mismo resto cuando son divididos por n si y solo si : a – c = nk, ?k ? Z+ Dem. Si a y c dejan el mismo resto cuando son divididos por n entonces tenemos que probar que: a – c = nk, ?k ? Z+ En efecto : a = nq1 + r1 , c = nq2 + r2 , con 0 = r1 < n; con 02 < n; Pero por hip´tesis r1 = r2 , as´ que: r1 = a – nq1 y r2 = c – nq2 luego: a – nq1 = c – nq2 a – c = nq1 – nq2 a – c = n(q1 – q2 ), deaqui q1 – q2 = k a – c = nk 2. Use el algoritmo de la divisi´n para probar que todo entero impar de la forma 4k + 1 ´ 4k + 3 para alg´n entero k. Dem. Sea a un entero impar cualquiera y dividamos a entre 4 es decir: a = 4k + r , 0 = r < 4 14

i i o o o o u u u ´ u u o ´ u u INSSB Teor´a de la Divisibilidad Monograf´ia r = 0, r = 1, r = 2, r =3 Entonces reemplazando tenemos que: a = 4k + 0 , no impar, pues es de la forma par a = 4k a = 4k + 1, a = 4k + 2, ?, a = 2(2k + 1),no impar, pues es de la forma par a = 2k. a = 4k + 3 As´ a = 4k + 1 o a = 4k + 3 3.3.3. Divisibilidad De?nici´n: Sean a y b enteros con b = 0. Decimos que b divide a a (´ que b es un divisor de a ´ que b es un factor de a ´ a es m´ltiplo de b) si a = bc para alg´n entero c, en s´imbolos “b divide a a” se escribe b | a y “b no divide a a” se escribe b a. Obs. i a y -a tienen los mismos divisores. ii Todo divisor de a es menor o igual a |a| iii Un entero no nulo tiene un n´mero ?nito de divisores. 3.3.4. Primos y factorizaci´n unica Todo entero n = ± 1 tiene por lo menos 4 divisores, los cuales son ±1, ±n, ahora los enteros que tienen solo estos 4 divisores, constituyen una parte importante dentro de la teor´ia de n´meros, a estos los llamamos n´meros primos. De?nici´n.: Un entero P se dice que es primo si y solo si, sus unicos divisores son ±1 y ±p Ejemplo: Si a, b y c son enteros tales que a · b = c, entonces se dice que a y b son factores o divisores de c, y que c es un m´ltiplo de a y b. Como 3 · 4 = 12 el n´mero 3 es un factor 15

i u e u u u u ´ a u u u ´ u u e n u u INSSB Teor´a de la Divisibilidad Monograf´ia de 12, y el 12 es un m´ltiplo de 3. Tambi´n 4 es un factor de 12 y 12 es un m´ltiplo de 4. El n´mero 12 tiene otros factores. Por ejemplo, -2, ya que (-2) · (-6) = 12. Usaremos el s´imbolo d|c para denotar que d es un factor o divisor de c. Si d no es un factor de c, escribiremos d c. Consideremos ahora los enteros positivos mayores que 1, esto es, 2, 3, 4, ….Cada uno de estos enteros puede ser clasi?cado como un numero primo o como un n´mero compuesto. Un entero positivo p mayor que 1 se dice que es un n´mero primo o simplemente un pri- mo, si los unicos enteros positivos factores de p son 1 y p. Un entero positivo mayor que 1 que no es primo se dir´ que es un n´mero compuesto, o simplemente un compuesto, esto es, un n´mero compuesto es un entero positivo n que posee factores positivos diferentes de 1 y n. El 5 es un n´mero primo, ya que sus unicos factores posibles son 1 y 5. En cambio, 10 es un n´mero compuesto, pues el 2 es un factor de 10 y 2 = 1 y 2=10. Como el 1 no es ni primo ni compuesto, tenemos que cada n´mero del conjunto de los enteros positivos es o un primo o un compuesto, o igual a 1. Teorema : Todo entero n = 0, ±1, es un producto de primos Dem.: Supongamos que el teorema es falso; es decir, existe un entero m = 0, ±1 que no es un producto de primos, es decir que no se puede factorizar en producto de primos. Luego, consideremos el conjunto de todos los enteros no negativos que son producto de primos y llamemoslo S, y por lo anterior S = Ø pues m ? S, pero por el P.B.O. sabemos que S tiene un elemento m´inimo, supongamos m0 , es decir m0 m, ahora ¿m0 es primo o no lo es?, pues tenemos m0 no es primo ya m0 ? S, asi m0 = ab, 0 < a < m0 de ahi que a, b no pertenece a S, entonces a es producto de primos y b tambi´n. Entonces m0 es producto de primos es decir m0 no pertenece a S, pero esto es falso, ya que m0 es el elemento mas peque˜o de S, lo cual es una contradicci´n. Luego, el teorema esta probado. 3.3.5. Propiedades de los n´meros primos El problema de encontrar todos los primos menores que un n´mero dado n se torna muy dif´icil cuando n es grande. En verdad, para valores extremadamente grandes de n, 16

i 7 a e o o e n e u u u u u e u u a u a INSSB Teor´a de la Divisibilidad Monograf´ia el trabajo ser´ia casi imposible desde el punto de vista pr´ctico. Existen varias listas de tales primos para valores de n asta aproximadamente 10 , que son completas y dignas de con?anza. Una t´cnica llamada la criba de Erat´stenes, en honor al matem´tico griego erat´stenes (256-194 A.C.), representa un m´todo razonable para obtener una lista completa de pri- mos menores o iguales que n, cuando n es relativamente peque˜o. Esta t´cnica consiste en escribir una lista de los enteros entre 2 y n, para tachar cada segundo n´mero despu´s del 2, es decir4, 6, 8, …, ya que cada uno de tales n´meros contiene como factor a 2, y por tanto es compuesto. Continuamos eliminando cada tercer n´mero despu´s 3, es decir, 6, 9, 12, …, ya que ellos son n´meros compuestos; repetimos la operaci´n eliminando cada quinto n´mero despu´s del 5, cada s´ptimo n´mero despu´s del 7, … Muchos n´meros son tachados m´s de una vez. El proceso termina cuando todos los m´ltiplos de p distintos de v p, para todo primo p = n han sido eliminados. Los enteros que quedan despu´s de este tamizado son los primos menores o iguales a n. La tabla (abajo) muestra el resultado del tamizado para n = 100. Los primos menores o iguales que 100 est´n en los c´irculos. 17

i o ia u u INSSB Teor´a de la Divisibilidad La criba de Erat´stenes PARA n = 100 Monograf´ia 2 3 4 5 6 7 8 9 10 11 12 13 19 14 15 16 17 20 21 22 23 18 24 25 31 37 43 49 55 61 67 73 79 85 91 97 26 32 38 44 50 56 62 68 74 80 86 92 98 27 33 39 45 51 57 63 69 75 81 87 93 99 28 34 40 46 52 58 64 70 76 82 88 94 100 29 35 41 47 53 59 65 71 77 83 89 95 30 36 42 48 54 60 66 72 78 84 90 96 Notar que, excepto por los primos 2 y 3, todo primo en la tabla ocurre en primera o en la quinta columna. Los enteros localizados en esas columnas son de la forma 6k + 1 o 6k – 1, donde k es un entero positivo. Se podr´ conjeturar que todo primo, distinto de 2 y3, es de la forma 6k + 1 o 6k – 1. Teorema :El n´mero de primos es in?nito. Demostraci´n: (Por contradicci´n). Supongamos que existe una cantidad ?nita de n´meros primos; es decir: p1 , p2 , p3 , …, pn donde pi es primo; ahora, sin perder generalidad supongamos que: p1 < p2 < p3 < p4 < … < pn-1 < pn , notemos que pn es el mas grande primo. 18

i u ´ i u a u o o a u a a u a u a u INSSB Teor´a de la Divisibilidad Monograf´ia Luego, construyamos el siguiente n´mero: A = p1 · p2 · p3 · . . . · pn-1 · pn // + 1 A + 1 = (p1 · p2 · p3 · . . . · pn-1 · pn ) + 1 Ahora A+1 es primo o A+1 es compuesto(no primo); supongamos que A+1 sea primo entonces vemos que pn < A+1 lo cual es una contradicci´n (??), pues pn es el mas grande primo. Por otro lado si A + 1 es compuesto tiene mas de 2 divisores, pues los unicos divisores (primos) que tiene A + 1 diferentes de A + 1 y 1, son p1 , p2 , p3 , …, pn , ahora pues notemos que que ninguno de ellos divide exactamente a A+1; pues la division de A+1 entre pi , con i = 1, 2, 3, …, n, deja resto as´ llegamos a otra contradicci´n (??. Por lo tanto llegamos a la conclusi´n de que el n´mero construido no es primo ni compuesto, con lo que queda demostrado el teorema. 3.4. M´ximo Com´n divisor En esta secci´n analizaremos el problema de determinar el mayor de los factores comunes a dos enteros. De?nici´n Sean a y b enteros no ambos cero, el m´ximo com´n divisor (MCD) de a y b es el m´s grande entero d que divide a a y b, en otras palabras, d es el MCD de a y b, Para demostrar que un entero positivo d es el m´ximo com´n divisor de dos enteros a y b, no ambos cero, es su?ciente probar que: (i) d|a y d|b (ii) si c|a y c|b, entonces c = d. El m´ximo com´n divisor de a y b, es usualmente denotado por (a, b) Por ejemplo, el m´ximo com´n divisor de 24 y 78 es 6; esto es, 19

i 2 2 e a u ´ a i o INSSB Teor´a de la Divisibilidad Monograf´ia (24, 78) = 6. Notese tambi´n que (-24, 78) = (24, -78) = (-24, -78) = 6. Si a = b = 0, entonces (a, b) no existe. Si a = 0 y b = 0, entonces (a, b)=|a|; si a = 0 y b = 0, entonces (a, b)=|b|. Observaciones: i (a, b) = 1 ii (a, 0) = |a| iii Si (a, b)=1 Decimos que a y b son primos relativos o comprimos. Teorema : Sean a y b enteros no nulos, y sea d su m´ximo com´n divisor, entonces existen (no necesariamente unicos) enteros u y v tal que d = au + bv Demostraci´n: Sea S el conjunto de todas las combinaciones lineales de a y b, eso es : S = am + bn/m, n ? Z Encontraremos un elemento particular de S y mostraremos que el MCD. Primero notemos que a2 + b2 = aa + bb est´ en S y a2 + b2 = 0. Como a y b son ambos no nulos a +b debe ser positivo. Luego S contiene enteros positivos y de ah´ debe contener un elemento m´inimo en S, por el principio del buen orden. Sea t dicho elemento m´inimo de S. Por de?nici´n de S sabemos que t = au + bv para algunos enteros u y v, a?rmamos que t es el MCD de a y b, esto es, t = d. 20

i o i i ´ i i u u i o i a u o o a INSSB Teor´a de la Divisibilidad Monograf´ia Para probar esto mostraremos que t|a. Por el Algoritmo de la Divisi´n, existen enteros q y r tal que a = tq + r, con 0 = r < t. consecuentemente: r = a – tq r = a – (au + bv)q = a – aqu – bvq r = a(1 – qu) + b(-vb) As´ que r es una combinaci´n lineal de a y b, y de ah´ r ? S, ya que r < t (El elemento m´inimo positivo de S), sabemos que r es no positivo como r = 0, la unica posibilidad es que r = 0. Luego a = tq + r = tq + 0 = tq As´ t|a. Un argumento similar muestra que t|b. De ah´ t es un com´n divisor de a y b. Sea c cualquier otro com´n divisor de a y b, as´ que c|a y c|b entonces a = cr y b = cs, para algunos enteros r y s, consecuentemente t = au + bv = (cr)u + (cs)v = c(ru + sv) La primera y ultima parte de esta ecuaci´n muestra que c|t de donde c = |t|. Pero t es positivo, as´ |t| = t y c = t esto muestra que t es el M´ximo com´n divisor d Corolario: Sea a y b enteros no nulos y sea d un entero positivo entonces el MCD de a y b si y s´lo si d satisface: (i) d|a y d|b (ii) si c|a y c|b, entonces c|d. Demostraci´n: Supongamos que d = (a, b). Entonces d = 1 y d satisface i) por de?nici´n. El ultimo p´rrafo de la prueba del teorema muestra que (con d en lugar de t) d satisface la condici´n ii). Rec´iprocamente supongamos 21

i u u i i a u a u ´ a u ´ a u a u o o INSSB Teor´a de la Divisibilidad Monograf´ia que d es un entero positivo que satisface las dos condiciones. Entonces d es un divisor com´n de a y b por i). Si c es otro divisor com´n de a y b entonces c|d por ii). De ah´ c = |d|, pero d es positivo, as´ |d| = d de donde c = d, luego d es el m´ximo com´n divisor. Teorema : El m´ximo com´n divisor de dos enteros, no ambos cero, es unico. Demostraci´n: Si g y g‘ son dos enteros positivos que satisfacen condiciones (i) y (ii) para dos enteros a y b, no ambos cero, entonces g|g‘ y g‘|g. Por lo tanto, g = g‘. Los dos teoremas anteriores, en conjunto establecen que el m´ximo com´n divisor de dos enteros, no ambos nulos, existe y es unico; pero ninguno da un procedimiento para determinar el m´ximo com´n divisor. Ilustraremos un procedimiento para determinar el m´ximo com´n divisor. Ilustraremos un procedimiento en el caso en que ambos enteros sean distintos de 0. Este procedimiento, un algoritmo, depende de la propiedad de la di- vision. Un algoritmo es un proceso que envuelve el uso repetido de una f´rmula o regla u operaci´n tal que la informaci´n o resultado obtenido en cada paso es usado en los pasos siguientes hasta que el resultado deseado es obtenido. Consideremos dos enteros positivos a y b. Sea a > b. Entonces, por la propiedad de la divisi´n, existen qi y ri tales que a = q1 b + r1 , donde 0 < r1 < b; b = q2 r1 + r2 , r1 = q3 r2 + r3 , 22 donde 0 < r2 < r1 ; donde 0 < r3 < r2 ;

i u u o u o u o o o o o o u o e i u INSSB ············ Teor´a de la Divisibilidad rk-3 = qk-1 rk-2 + rk-1 , donde 0 < rk-1 < rk-2 ; rk-2 = qk rk-1 + rk , donde 0 < rk < rk-1 ; Monograf´ia rk-1 = qk+1 rk + 0. Observar que r1 , r2 , r3 , …, rk+1 , rk representan una secuencia decreciente de enteros pos- itivos. Como solo existe un n´mero ?nito de enteros positivos menores que b, el proceso debe terminar; es decir, solo existe un n´mero ?nito de enteros positivos ri que satisfacen aquellas condiciones. Este proceso, llamado algoritmo de Euclides produce (a, b) = rk . Para demostrar que (a, b) = rk , necesitamos probar que (i) rk |a y rk |b (ii) todo divisor de a y b divide a rk . De la ultima ecuaci´n se sigue que rk |rk-1 . Sustituyendo rk – 1 en la pen´ltima ecuaci´n, rk-2 = qk qk+1 rk + rk = (qk qk+1 + 1)rk , Por lo tanto, rk |rk-2 . Sustituyendo rk-2 y rk-1 en la antepen´ltima ecuaci´n, rk-3 = qk-1 (qk qk+1 + 1)rk + qk+1 rk = (qk-1 qk qk+1 + qk-1 + qk+1 )rk Por lo tanto, rk |rk-3 . Continuando en forma an´loga, podemos demostrar que rk |b, ya que rk |r1 y rk |r2 en la segunda ecuaci´n. Por lo tanto, usando la primera ecuaci´n, rk |a y entonces la condici´n (i) es satisfecha; es decir, rk divide a a y b. Para demostrar que la condici´n (ii) es satisfecha; sea d|a y d|b. Entonces de la primera ecuaci´n se desprende que d|r1 ; de la segunda ecuaci´n, d|r2 ; de la tercera ecuaci´n, d|r3 ; …; y ?nalmente, de la pen´ltima ecuaci´n, d|rk . Por lo tanto, todo divisor de a y b tambi´n divide rk . De aqu´ que (a, b) = rk . Si a o b es un n´mero negativo, podemos hacer caso omiso del signo negativo en el algoritmo 23

i 3.5. a u i, a u i, a u a a u o e INSSB Teor´a de la Divisibilidad Monograf´ia de euclides, ya que (a, b) = (a, -b) = (-a, b) = (-a, -b). Propiedades del m´ximo com´n divisor Se dice que dos enteros a y b, no ambos 0, son relativamente primos o primos en- tre s´ si el m´ximo com´n divisor es la unidad; esto es si (a, b) = 1. Por ejemplo, 22 y 15 son enteros relativamente primos, aunque ninguno de ellos es primo. En general los n = 2enteros a1 , a2 , …, y an , no todos 0, se dicen relativamente primos o primos entre s´ si el m´ximo com´n divisor es la unidad; es decir, si (a1 , a2 , …, an ) = 1. Adem´s, si (ai , aj ) = 1 para cada i = j e i, j = 1, 2, …, n, entonces los n = 2 enteros a1 , a2 , …, y an se dicen relativamente primos a pares. Por ejemplo, los tres enteros 5, 10 y 13 son relativamente primos ya que (5, 10, 13)=1; pero ellos no son relativamente primos a pares, puesto que (5, 10) = 1. Los siguientes teoremas concernientes a propiedades del m´ximo com´n divisor de dos enteros son de cierto inter´s. Teorema : Dos enteros a y b, no ambos 0, son relativamente primos si y solo si existen enteros x e y tales que 1 = xa + yb. Dem.: Si (a, b)=1, entonces por el teorema del MCD existen enteros x e y tales que 1 = xa + yb. Si (a, b) = d y d > 1, entonces por el teorema del MCD d es el mayor entero positivo que puede ser expresado como funci´n lineal homog´nea de a y b. Por lo tanto, 1 = xa + yb 24

i b b b b d d d i d i o INSSB Teor´a de la Divisibilidad Monograf´ia para todo par de enteros x e y. Por lo tanto, el teorema queda demostrado. Teorema : Si d=(a, b) entonces ( a , d ) = 1. Dem.: Si ( a , d ) = k, donde k = 1, entonces a = ka‘ y d = kb‘; esto es, a = dka‘ y b = dkb‘. Como dk|a y dk|b, se tiene d = (a, b). De aqu´ que, si d = (a, b), entonces ( a , d ) = 1. Teorema : Si (a, b)=1 y (a, c)=1, entonces (a, bc)=1. Dem.: Si (a, b)=1, entonces, por el teorema del MCD existen enteros x e y tales que 1 = xa + yb; si (a, c)=1 entonces existen enteros r y s tales que 1 = ra + sc. Entonces 1 = xa + yb(ra + sc) = (x + ybr)a + (ys)bc. De aqu´ que por el teorema de los coprimos, se tiene que (a, bc)=1. Teorema : Si (a, bi ) = 1 para i=1, 2, …, n, entonces (a, b1 b2 …bn ) = 1. . Dem.: La demostraci´n es por inducci´n matem´tica. Esta dado que (a, b1 ) = 1. Supong- amos ahora que (a, b1 b2 …bk ) = 1. Como (a, bk+1 ) = 1, entonces, por el teorema anterior (a, b1 b2 …bk+1 ) = 1. 25

i 3.6. a o o o o o o e o o i o o o INSSB Teor´a de la Divisibilidad Monograf´ia Por lo tanto, (a, b1 b2 …bn ) = 1. para cualquier entero positivo n, y el teorema queda demostrado. Teorema : Si a|bc y (a, b) = 1, entonces a|c. Dem.: Si (a, b)=1, entonces, por el teorema del MCD, existen enteros x e y tales que 1 = xa + yb Entonces c = xac + ybc. Como a|bc y a|ac, se tiene a|(xac + ybc); esto es, a|c. Criterios de divisibilidad y propiedades elementales de congruencias Previamente para poder demostrar muchos de los criterios de divisibilidad enunciare- mos algunas propiedades de Congruencias que nos podr´n ser de mucha ayuda. La relaci´n de las congruencias m´dulo m, cuando m es un entero positivo, es una relaci´n de equivalencia en el conjunto de los enteros; esto es, la relaci´n de congruencia m´dulo m es: 1. Re?exiva: a = a (m´d m) para todo entero a; 2. Sim´trica: s´ia = b (m´d m), entonces b = a (m´d m) para todo par de enteros a y b; 3. Transitiva: s´ a = b (m´d m) y b = c toda terna de enteros a, b y c. Algunos teoremas sobre congruencias 26 (m´d m), entonces a = c (m´d m) para

i i o o i o o i o o o i o o o i o o o u u o u u u ´ u a u u u u e o o ´ i: INSSB 1. S´ a = b Teor´a de la Divisibilidad (m´d m) y c es un entero, entonces a + c = b + c (m´d m) Monograf´ia 2. S´ a = b (m´d m) y c es un entero, entonces ac = bc (m´d m) 3. S´ a = b (m´d m) y c = d (m´d m), entonces a + c = b + d (m´d m) 4. S´ a = b (m´d m) y c = d (m´d m), entonces a – c = b – d (m´d m) 5. S´ a = b (m´d m) y c = d (m´d m), entonces ac = bd (m´d m) Para conocer si un n´mero es m´ltiplo de otro, es decir para averiguar si es divisible por ese otro, no siempre es necesario hacer la divisi´n para ver si el cociente es exacto, pues se conocen ciertas caracter´isticas que deben poseer los n´meros para ser m´ltiplos de otros determinados. Ahora veremos algunos criterios de divisibilidad. Al conjunto de condiciones que debe cumplir un n´mero cualquiera para ser divisible por otro determinado , se le llama crite- rio de divisibilidad por este ultimo n´mero. A continuaci´n se enuncian los criterios de divisibilidad m´s utilizados. Notaci´n: Para indicar el n´mero tal que : La cifra de las unidades esta representada por a, la cifra de las decenas por b, la cifra de las centenas por c, la cifra de las unidades de mil por d, etc., se utiliza la notaci´n dcba. El subrayado se efect´a para aclarar que no se trata de un producto, sino de cifras de un n´mero. Por otro lado: Sea n ? N – 0 y consideremos un b > 1, entonces un n´mero n en base b, se representa por el polinomio n = ak bk + ak-1 bk-1 + … + a1 b + a0 Donde 0 ai < b obs´rvese que la precisi´n es importante Criterios de divisibilidad por 2. Un entero es divisible por 2 si y s´lo si el ultimo d´igito de las unidades es par. Dem: Sea n un entero divisible por 2 es decir: n = 2 · k y n = ak 10k + ak-1 10k-1 + … + a1 10 + a0 As´ 27

i i u i, o 2 u e u u o 2 u 2 2 2 o INSSB Teor´a de la Divisibilidad Monograf´ia 2k = ak 10k + ak-1 10k-1 + … + a1 10 + a0 2k = 10(ak 10k-1 + ak-1 10k-2 + … + a1 ) + a0 2k – 10(ak 10k-1 + ak-1 10k-2 + … + a1 ) = a0 a 2k – 2 · 5(a) = a0 2(k – 5(a)) = a0 ; As´ a0 es par. Todo n´mero que termina en cifra par es divisible por 2. As´ 516, 24, 1968 y 4530, como puede comprobarse son divisibles por 2. Simb´licamente tenemos: n = dcba ? n = ° a es par Como toda cifra par es m´ltiplo de , tambi´n puede enunciarse: Un n´mero es divisible por 2 cuando la cifra de sus unidades es m´ltiplo de 2. Simb´licamente tenemos: n = dcba ? n = ° Ejemplos: a=2 Son n´meros divisibles por 2: 1350, pues 0 = ° 278, pues 8 = ° 10002, pues 2 = ° Criterios de divisibilidad por 5. Un entero es divisible por 5 si y s´lo si el d´igito de las unidades es 5 o 0. Dem: Sea n un entero positivo de donde: n = 10q + r; 0 = r < 10 28

i u i i, u ´ u o i o o i o i o u i, 5 u 5 5 5 ´ u u e u u u o u INSSB Teor´a de la Divisibilidad Monograf´ia donde r representa el d´igito de las unidades Luego n = 5 · 2q + r Si n es divisible por 5, entonces n = 5 · R para alg´n R, as´ 5R = 5 · 2q + r 5R – 5 · 2q = r 5(R – 2q) = r As´ r es m´ltiplo de 5, pero los unicos m´ltiplos de 5 comprendidos entre 0 y 9 son 0 y 5, es decir; r = 0 ´ r = 5 s´ el d´igito de las unidades es 0 ´ 5, entonces n = 10q + r con r = 0 ´ r = 5, as´ n = 10q + 0 ´ n = 10q + 5, as´ n = 5(2q) ´ n = 5(2q + 1), en cualquier caso n es divisible por 5 Todo n´mero terminado en 0 o en 5 es divisible por 5. As´ 30, 25, 200, 815, como se puede comprobar son divisibles por 5. Ejemplos: n = dcba a=5 o a=5 ? n =° Son numeros divisibles por 5: 1350, 110, 585, 8495, 1020. Son n´meros divisibles por 5: 1350, pues 0 = ° 110, pues 0 = ° 585, pues 5 = ° Teniendo en cuenta que 0 y 5 son los unicos n´meros de una cifra m´ltiplos de 5, el criterio de divisibilidad por 5 tambi´n puede enunciarse: Un n´mero es divisible por 5 si la cifra de las unidades es m´ltiplo de 5. Criterios de divisibilidad por 3. Un n´mero entero es divisible por 3 si y s´lo si la suma de sus d´igitos es m´ltiplo de 3. Dem. : Sea n un entero. Consideremos lo siguiente: n = ak 10k + ak-1 10k-1 + … + a1 10 + a0 ; observemos que 29

i . o o o o o o o o o o o o o o o o o o o u u ° u u u 3 3 INSSB Teor´a de la Divisibilidad Monograf´ia 1 = 1 (m´d 3)//a0 ? 10 = 1 (m´d 3)//a1 ? 102 = 1 (m´d 3)//a2 ? . . 10k-1 = 1 (m´d 3)//ak-1 ? 10k = 1 (m´d 3)//ak ? Sumando miembro a miembro : a0 = a0 a1 10 = a1 a2 102 = a2 ak-1 10k-1 = ak-1 ak 10k = ak (m´d 3) (m´d 3) (m´d 3) (m´d 3) (m´d 3) a0 + a1 10 + a2 102 + … + ak-1 10k-1 + ak 10k = a0 + a1 + … + ak-1 + ak n = a0 + a1 + … + ak-1 + ak (m´d 3) (m´d 3) Luego si: 3|n ? n = 0 (m´d 3) pero n = a0 + … + ak (m´d 3) de donde a0 + … + ak = n (m´d 3), y por transitividad tenemos a0 + … + ak = 0 (m´d 3) ? 3|a0 + … + ak , ahora Si 3|a0 + … + ak ? a0 + … + ak = 0 (m´d 3) y n = a0 + … + ak (m´d 3), por transitividad n = 0 (m´d 3) es decir 3|n Dado el n´mero 2451 la suma de los valores absolutos de sus cifras es: 2 + 4 + 5 + 1 = 12. Este n´mero 12 es 3, y se observa que el n´mero dado es divisible por 3. En efecto: 2451 = 3 · 817 + 0 Esta observaci´n es general y se enuncia en el criterio que dice: Un n´mero es divisible por 3 si la suma de los valores intr´insecos de todas sus cifras es m´ltiplo de 3. Es decir: centerlinen = dcba ? n = ° a+b+c+d=° 30

i u 3 3 3 o o . o o o o o i o o o o o o o o o o u u INSSB Teor´a de la Divisibilidad Monograf´ia Ejemplos: Son n´meros divisibles por 3: ¾ 513264 es divisible por 3, pues: 5 + 1 + 3 + 2 + 6 + 4 = 21 = ° ¾ 10101 es divisible por 3, pues: 1 + 1 + 1 = 3 = ° ¾ 29700, es divisible por 3, pues: 2 + 9 + 7 = 18 = ° Criterios de divisibilidad por 9. Un entero expresado en numeraci´n decimal por 9 si y s´lo si la suma de todos sus d´igitos es divisible por 9 Dem. Sea n = ak 10k + ak-1 10k-1 + … + a0 ; notemos que: 1 = 1 (m´d 9)//a0 ? 10 = 1 (m´d 9)//a1 ? 102 = 1 (m´d 9)//a2 ? . . 10k-1 = 1 (m´d 9)//ak-1 ? 10k = 1 (m´d 9)//ak ? De ah´ tenemos: n = a0 + … + ak (m´d 9) a0 = a0 a1 10 = a1 a2 102 = a2 ak-1 10k-1 = ak-1 ak 10k = ak (m´d 9) (m´d 9) (m´d 9) (m´d 9) (m´d 9) Si 9|n ? n = 0 (m´d 9) a0 + … + ak = 0 (m´d 9) es decir 9|a0 + .. + ak Ahora si 9|a0 + .. + ak ? a0 + … + ak = 0 (m´d 9) entonces n = 0 (m´d 9) es decir 9|n El criterio de divisibilidad por 9 es del todo an´logo al criterio de divisibilidad por 3, es decir: Un n´mero es divisible por 9 si la suma de los valores intr´insecos de todas sus cifras es m´ltiplo de 9. Es decir: 31

i 9 9 i, u 9 u u 9 9 o k o u k k o o o o o o o o o o . o o INSSB Teor´a de la Divisibilidad Monograf´ia n = dcba ? n =° a+b+c+d=° As´ en el n´mero 8127 se veri?ca que: 8 + 1 + 2 + 7 = 18 = ° luego dicho n´mero es divisible por 9. En efecto: 8127 = 9 · 903 + 0 Ejemplos: Son n´meros divisibles por 9: ¸ 74268 es divisible por 9, pues: 7 + 4 + 2 + 6 + 8 = 27 = ° ¸ 1020321 es divisible por 9, pues: 1 + 2 + 3 + 2 + 1 = 9 = ° Criterios de divisibilidad por 11. Sea n = k i i=0 ai 10 la representaci´n de un entero positivo n en base 10. Entonces n es divisible por 11 si y s´lo si i=0 (-1)i ai es divisible por 11. El n´mero 818092 es divisible por 11. Dem.: Sea n = i=0 ai 10i es decir n = a0 + a1 10 + a2 102 + … + ak-1 10k-1 + ak 10k y i=0 (-1)i ai = a0 – a1 + a2 – a3 + a4 – a5 + a6 – a7 + a8 – … + (-1)k ak Notemos que: 1 = 1 (m´d 11)//a0 ? a0 = a0 (m´d 11) 10 = -1 (m´d 11)//a1 ? a1 10 = -a1 (m´d 11) 102 = 1 (m´d 11)//a2 ? a2 102 = a2 (m´d 11) 103 = -1 (m´d 11)//a3 ? a3 103 = -a3 (m´d 11) 104 = 1 (m´d 11)//a4 ? a4 104 = a4 (m´d 11) . . 10k = (-1)k (m´d 11)//ak ? ak 10k = ak (-1)k (m´d 11) 32

i o o i o o i o u u u 11 11 u INSSB Teor´a de la Divisibilidad Monograf´ia Luego por propiedades de congruencia tenemos: a0 + a1 10 + … + ak 10k = a0 – a1 + a2 – a3 + … + (-1)k ak n = a0 – a1 + a2 – a3 + … + (-1)k ak (m´d 11) (m´d 11) S´ n = 0 (m´d 11) ? a0 – a1 + a2 – a3 + … + (-1)k ak = 0 (m´d 11) Ahora s´ a0 – a1 + a2 – a3 + … + (-1)k ak = 0 (m´d 11) Entonces n = 0(11) ? 11|n En efecto: 818092 = 11 · 74372 + 0 Se observa que la suma de las cifras de los lugares pares: 9 + 8 + 8 = 25 menos la suma de las cifras de los lugares impares, es decir, 2+0+1=3 da por resultado: 25 – 3 = 22, que es m´ltiplo de 11. Esta observaci´n es general, y se enuncia en el criterio de divisibilidad por 11: Un n´mero es divisible por 11 si la diferencia entre la suma de los valores intr´insecos de las cifras de los lugares pares y la de las cifras de los lugares impares es m´ltiplo de 11. En efecto: n = dcba ? n =° (a+c)-(b+d)=° Ejemplos: Son n´meros divisibles por 11: ¦ 32813 es divisible por 11, pues: Suma de cifras, lugares pares: 1+2 = 3 Suma de cifras, lugares impares: 3+8+3 = 14 33

i 2 ° u o o o o o o o o o o . o o o o o o o o o o o INSSB Teor´a de la Divisibilidad Monograf´ia 14 – 3 = 11 = 11 Despu´s de estudiar algunos criterios de divisibilidad, podemos deducir de esto un patron que es el siguiente: Criterio de divisibilidad por “m” en el sistema de base 10 utilizando los restos potenciales. Sea el n´mero n descompuesto polinomicamente tenemos n = ak 10k +ak-1 10k-1 +…a2 102 + a2 10 + a1 101 + a0 Entonces tenemos: 1 = 1 10 = r1 102 = r2 103 = r3 104 = r4 (m´d m)//a0 ? (m´d m)//a1 ? (m´d m)//a2 ? (m´d m)//a3 ? (m´d m)//a4 ? a0 = a0 a1 10 = r1 a2 102 = r2 a3 103 = r3 a4 104 = r4 (m´d m) (m´d m) (m´d m) (m´d m) (m´d m) . . 10k = rk (m´d m)//ak ? ak 10k = rk (m´d m) Restos potenciales Sumando miembro tenemos: a0 + a1 10 + a2 102 + … + ak-1 10k-1 + ak 10k = r0 + r1 + r2 + r3 … + rk n = r0 + r1 + r2 + r3 … + rk Luego si: m|n ? n = 0 (m´d m) pero n = r0 + … + rk (m´d m) de donde r0 + … + rk = n (m´d m), y por transitividad tenemos r0 + … + rk = 0 (m´d m) ? m|r0 + … + rk , ahora Si m|r0 + … + rk ? r0 + … + rk = 0 (m´d m) y n = r0 + … + rk (m´d m), por transitividad n = 0 (m´d m) es decir m|n 34 (m´d m) (m´d m)

i u u o u a i . i o INSSB Teor´a de la Divisibilidad Monograf´ia Finalmente el anterior enunciado, que fue demostrado, nos enuncia que, un n´mero n en base 10 es congruente con otro bajo alg´n m´dulo m, de esto deducimos que m divide al n´mero n , que es lo que busc´bamos en nuestros objetivos preliminares. Ejemplos: He aqu´ unos ejemplos, aplicando la anterior regla: para desarrollar los subsecuentes ejemplos, Hallar el criterio de divisibilidad de 13 1 = 1 10 = mod 13 – 3 102 = ( mod 13 – 3)( mod 13 – 3) = = mod 13 + 9 mod 13 + 4 103 = ( mod 13 + 4)( mod 13 – 3) = = 104 = ( = mod 13 – 12 mod 13 – 1 mod 13 – 1)( mod 13 – 3) mod 13 + 3 105 = ( mod 13 + 3)( mod 13 – 3) = = 106 = ( = = . . De ah´ tenemos los restos: mod 13 – 9 mod 13 – 4 mod 13 – 4)( mod 13 – 3) mod 13 + 12 mod 13 + 1 n = r0 (1) + r1 (-3) + r2 (4) + r3 (-1) + r4 (3) + r5 (-4) + r6 (1)… 35 (m´d 13)

i . i o INSSB Teor´a de la Divisibilidad Monograf´ia Hallar el criterio de divisibilidad de 17 1 = 1 10 = mod 17 – 7 102 = ( mod 17 – 7)( mod 17 – 7) = = = mod 17 + 49 mod 17 + 13 mod 17 + 4 103 = ( mod 17 + 4)( mod 17 – 7) = = = 104 = ( = mod 17 – 28 mod 17 – 10 mod 17 – 1 mod 17 – 1)( mod 17 – 7) mod 17 + 7 105 = ( mod 17 + 7)( mod 17 – 7) = = = 106 = ( = = = mod 17 – 49 mod 17 – 13 mod 17 – 4 mod 17 – 4)( mod 17 – 7) mod 17 + 28 mod 17 + 10 mod 17 + 1 107 = ( = . . De ah´ tenemos los restos: mod 17 + 1)( mod 17 – 7 mod 17 – 7) n = r0 (1) + r1 (-7) + r2 (4) + r3 (-1) + r4 (7) + r5 (-4) + r6 (1) + r7 (-7)… 36 (m´d 17)

i . i o INSSB Teor´a de la Divisibilidad Monograf´ia Hallar el criterio de divisibilidad de 79 1 = 1 10 = = = 102 = ( = = mod 79 – 69 mod 79 – 15 mod 79 – 6 mod 79 – 6)( mod 79 – 6) mod 79 + 36 mod 79 + 9 103 = ( mod 79 + 9)( mod 79 – 6) = = 104 = ( = = mod 79 – 54 mod 79 – 9 mod 79 – 9)( mod 79 – 6) mod 79 + 54 mod 79 + 9 105 = ( = = . . De ah´ tenemos los restos: mod 79 + 9)( mod 79 – 54 mod 79 – 9 mod 79 – 6) n = r0 (1) + r1 (-6) + r2 (9) + r3 (-9) + r4 (9) + r5 (-9)… 37 (m´d 79)

i . i o INSSB Teor´a de la Divisibilidad Monograf´ia Hallar el criterio de divisibilidad de 93 1 = 1 10 = = = 102 = ( = mod 93 – 83 mod 93 – 11 mod 93 – 2 mod 93 – 2)( mod 93 – 2) mod 93 + 4 103 = ( mod 93 + 4)( mod 93 – 2) = 104 = ( = = mod 93 – 8 mod 93 – 8)( mod 93 – 2) mod 93 + 16 mod 93 + 7 105 = ( mod 93 + 7)( mod 93 – 2) = = 106 = ( = = mod 93 – 14 mod 93 – 5 mod 93 – 5)( mod 93 – 2) mod 93 + 10 mod 93 + 1 107 = ( mod 93 + 1)( mod 93 – 2) = 108 = ( = mod 93 – 2 mod 93 – 2)( mod 93 – 2) mod 93 + 4 . . De ah´ tenemos los restos: n = r0 (1) + r1 (-2) + r2 (4) + r3 (-8) + r4 (7) + r5 (-5) + r6 (1) + r7 (-2) + r8 (4)… (m´d 93) 38

i 3.7. e u e a u u a u u iz a v u a u iz INSSB Teor´a de la Divisibilidad Monograf´ia M´todo para determinar la divisibilidad de un n´mero por otro A continuaci´n describiremos un m´todo que permitir´ determinar si un entero posi- tivo es divisible por alg´n otro o de lo contrario no es divisible por ninguno (primo). Primeramente para poder determinar esto es necesario determinar si el n´mero p dado es primo o es compuesto; en el caso de que sea compuesto se podr´ determinar por que n´meros es divisible tal n´mero p. Por ejemplo, 113. La ra´ cuadrada de 113 est´ entre 10 y 11, ya que 102 = 100 y 112 = 121 entonces 100 < 113 < 121; esto es 10 < v 113 < 11 Ahora podemos notar que lo primos menores o iguales que 113 son 2,3,5,7. Ahora veremos que ninguno de estos n´meros es factor de 113: 113 = 56 · 2 + 1 113 = 37 · 3 + 2 113 = 22 · 5 + 3 113 = 16 · 7 + 1 Por lo tanto,113 es primo, y no tiene m´s divisores que 1 y 113. Ejemplo 1: Que n´mero dividen a 1741 La ra´ cuadrada de 1741 esta entre 41 y 42 ya que 412 = 1681, 422 = 1764 y: 41 < v 1741 < 42 v 1681 < 1741 < 1764 v Los primos menores o iguales a 1741 son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. Ahora podemos discriminar, a estos primos de la siguiente manera: 39

i u u u i u i u u iz INSSB Teor´a de la Divisibilidad Monograf´ia los n´meros primos 2 y 5 no podr´ian ser factores de 1741, porque en ultimo d´igito de 1741 es 1, y sabemos que para que un n´mero tenga entre sus factores a 2 y 5 tal n´mero debe terminar en el d´igito de la unidad en par, para el 2; y en 0 o 5, para el 5, as´ que estos n´meros no los tomamos en cuenta, esto para aminorar nuestra tarea. v As´ los primos menores a 1741 son: 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. 1741 = 870 · 2 + 1 1741 = 580 · 3 + 1 1741 = 248 · 7 + 5 1741 = 158 · 11 + 3 1741 = 133 · 13 + 12 1741 = 91 · 19 + 12 1741 = 75 · 23 + 16 1741 = 60 · 29 + 1 1741 = 56 · 31 + 5 1741 = 47 · 37 + 2 1741 = 42 · 41 + 19 Ninguno de estos n´meros es divide de 1741 Por lo tanto 1741 es primo. Ejemplo 2: Que n´mero dividen a 316 La ra´ cuadrada de 316 esta entre 17 y 18 ya que 172 = 289, 182 = 324 y: 17 < v 316 < 18 v 289 < 316 < 324 v Los primos menores o iguales a 316 son 2, 3, 7, 11, 13, 17. 40

i u e u u u i u u a a u INSSB Teor´a de la Divisibilidad Monograf´ia 316 = 158 · 2 + 0 316 = 105 · 3 + 1 316 = 45 · 7 + 1 316 = 28 · 11 + 8 316 = 24 · 13 + 4 316 = 18 · 17 + 10 Ahora notemos que 2 si es un factor de 316 y divide a este n´mero pues al operar 158 · 2 + 0 = 316 nos da un resto 0, a diferencia de los otros factores primos que claramente no son factores de 316, o en otras palabras no dividen a 316; tambi´n podemos notar que el n´mero 316 es un n´mero no primo o sea es un n´mero compuesto. As´ de esta manera podemos encontrar los divisores de un n´mero p por otro n´mero, que no es m´s que un factor de p. Adem´s que podemos determinar si un n´mero es compuesto o primo. 41

o o o ia u u o u o a ia o o Cap´itulo 4 CONCLUSIONES Y RECOMENDACIONES Para este cap´itulo ?nal del trabajo de investigaci´n monogra?ca, tenemos las recomen- daciones y las conclusiones de este trabajo de investigaci´n monogra?co. 4.1. Conclusiones Luego de una descripci´n matem´tica de la Divisibilidad en Teor´ de N´meros, se llega a las siguientes conclusiones: Producto de todo lo tratado en este documento concluimos que es posible desarrollar el algoritmo de la divisibilidad para determinar la divisibilidad de un n´mero por otro. Nuestros objetivos preliminares mandaban hallar un algoritmo de la divisibilidad, se pu- do hallar el Algoritmo de la Divisibilidad en el que se pudo llegar a la forma general de los criterios de divisibilidad por m en el sistema en base 10. Para llegar a este resultado fue necesario estudiar el Algoritmo de la Divisi´n, adem´s de los los n´meros primos, y las propiedades del MCD, y la menci´n de lagunas propiedades de las congruencias, propiedades de los cuales era necesario estudiarlas, para ?nalmente poder llegar al a un criterio general general de la divisibilidad. Cabe recalcar que el objetivo general del trabajo monogr´?co, nos ped´ hallar un algo- ritmo general de la divisibilidad, evidentemente se hallo determinado logaritmo, (secci´n 3.6), el logaritmo es una generalizaci´n de la regla de los criterios de divisibilidad, el cual 42

i u i, i o o u u e u u o u a u o a ia a o e o o ia i, a u u u INSSB Teor´a de la Divisibilidad Monograf´ia nos permite descifrar el criterio de divisibilidad de un n´mero. Por otro lado nuestro objetivos espec´i?cos nos demandan cumplir determinados requisitos para desarrollar satisfactoriamente nuestros objetivos generales; es as´ que en un trabajo descriptivo como es la monograf´ia, es necesariamente imprescindible poder revisar, estu- diar y analizar determinadas teor´ias para poder enriquecer el presente trabajo y as´ es que se lo hizo; posteriormente, se describi´ y se demostr´ las propiedades de la divisibilidad, (Capitulo 3 ), asimismo se describi´ muchas otras propiedades propias de los n´meros enteros, propiedades que sin ellas no se hubiera podido demostrar el criterio general de la divisibilidad de un determinado n´mero. Tambi´n pudimos observar que determinar la divisibilidad de un n´mero por otro es posible bajo determinadas reglas del conjunto de los N´meros Enteros, y que la divisibili- dad es una relaci´n de?nida de los n´meros enteros. Adem´s podemos extractar que el el estudio de la divisibilidad es importante para poder expresar un n´mero en factores primos, tales que se son estudiados frecuentemente en los primeros cursos de secundaria. Por otro lado, es claro que la matem´tica es una ciencia exacta, que no s´lo merece ser conocida y estudiada super?cialmente por alumnos y mae- stros, sino que merece un mayor estudio y an´lisis, pues no tiene que limitarse a estudiarla super?cialmente, sino m´s al contrario deber´ de estudiarse de una manera m´s profunda, no s´lo en las universidades, tambi´n que esta forma de estudiarla llegase a los alumnos de secundaria, claro esta con una s´lida base de ciertas propiedades que la matem´tica tiene. Finalmente, es necesario que el maestro de matem´ticas de las Unidades Educativas de secundaria, este en permanente renovaci´n y actualizaci´n, tal y como lo norma la propia Reforma Educativa en actual vigencia, y no es necesario acudir a ninguna teor´ para poder a?rmar que el maestro debe saber mucho mas que el alumno sobre su especialidad, pues as´ si el maestro esta m´s preparado se ayuda mejor al alumno. 4.2. Recomendaciones Hemos visto que la divisibilidad entre n´meros es posible bajo ciertas circunstancias, pues es necesario hallar un criterio de divisibilidad para ese n´mero, esto para saber que tipo de restos potenciales deja. pero para llegar asta esto tuvimos que llegar a desarrollar primero el algoritmo de la Divisibilidad, y mediante este, los n´meros primos y los MCD 43

i u u u u u ia u o o u o a o a u a INSSB Teor´a de la Divisibilidad Monograf´ia de n´meros. Por lo anterior se considera que estudiar La Teor´ia de la Divisibilidad, es de gran utilidad al estudiante para que pueda desarrollar un n´meros mediante producto de factores primos, adem´s que pueda reconocer los divisores que un n´mero y los n´meros que lo dividen exactamente, que reconozca los divisores comunes de dos n´meros. Por otro lado, para introducir la divisibilidad en la ense˜anza de la Teor´ de n´meros en la Educaci´n Secundaria, es necesario realizar las siguientes recomendaciones: El estudiante, tiene que ampliar los conceptos matem´ticos que a visto en el nivel primario. Tal ampliaci´n tiene que estar orientada a que el alumno experimente el trabajo matem´tico puro, en un contexto netamente matem´tico. A partir de lo anterior, vea el alumno de que manera el conocimiento matem´tico de la teor´ia de n´meros tiene sus aplicaciones como un elemento de investigaci´n matem´tica. Desde luego debe tenerse muy en cuenta las propiedades b´sicas de los enteros. Propiedades de la igualdad Propiedades de la desigualdad Propiedades de la suma Propiedades de la multiplicaci´n Una b´sica noci´n de conjuntos. N´meros primos y compuestos. El MCD Criterio de divisibilidad en base 10 Todos estos puntos mencionados, nos ser´n de mucha ayuda para el estudiante, para que pueda determinar un criterio general de divisibilidad, ya que las propiedades de estos son primordiales para llegar a un criterio general. 44

A ia u u n ia a c˜ a u o ia o o u Cap´itulo 5 BIBLIOGRAF´IA RUIZ Arango, Isidro; “Teor´ de los n´meros primos”; Editorial San Marcos, Lima- Per´; A˜o 1999. HOWARD Eves, “Estudio de las geometr´ias” Universidad de Maine,Massachusetts – EE.UU,1965. PETTOFREZZO Anthony; BYRKIT Donald, “Introducci´n a la teor´ de numero”, Editorial Prentice/ hall internacional, Florida – EE.UU, 1972 DE CASTRO Korgi, Rodrigo; “El universo LTEX”; Editorial UNIBIBLOS; Bogot´, Colombia, 2001. TREJO, Cesar; BOSCH, Jorge; “Matem´tica Moderna”, Editorial Universitaria; Buenos Aires, Argentina, 1982. de OLIVEIRA Santos, Jose Pl´inio; “Introdu¸ao ´ Teoria dos N´meros”, Segunda edici´n; Rio de Janeiro, Brasil, 2001. ZORRILLA Arena, Santiago; “Introducci´n a la metodolog´ de la investigaci´n”; Editorial Melo S.A.; Mexico D.F. 1996. MOLL, Luis c.; “Vygosky y la educaci´n”; Grupo editor Aique; Argentina 1993. VOROBIOV, N.N.; “Criterios de divisibilidad”; Editorial MIR; Mosc´, URSS; 1975. 45

i o o INSSB Teor´a de la Divisibilidad Monograf´ia M.E.C.D.; “Nuevo compendio de legislaci´n sobre la Reforma Educativa y leyes conexas”; Edici´n, BOLIVIA DOS MIL S.R.L.; La Paz; 2001. 46