Divisibilidad Rafael F. Isaacs G.

*

Fecha: 14 de abril de 2005

El m´ aximo com´ un divisor La relaci´on “n divide a m” tiene sentido cuando n y m son enteros o naturales, pero no para fraccionarios o reales (por qu´e?). En la secci´on 4 vimos la forma de demostrar las propiedades mas elementales sobre esta relaci´on, propiedades que resumimos a continuaci´on utilizando la notaci´on “n|m”, tambi´en introducida en esa secci´on. Propiedades de la relaci´ on “n divide a m”. Siendo a, b, c enteros no nulos se tiene: 1. a|0 y 1|a 2. a|a 3. Si a|b y b|c entonces a|c. 4. Si a|b y b|a entonces |a| = |b|. 5. Si a|b y a|c entonces para cualesquier enteros x, y se tiene que a|(xb + yc) 6. Si a|b entonces |a| ≤ |b|. En base a estas propiedades desarrollaremos el concepto de m´aximo com´ un divisor de dos enteros a y b (no nulos). En aritm´etica elemental se conocen algoritmos para encontrar el m´aximo com´ un divisor de dos enteros y se entiende que por ejemplo el m´aximo com´ un divisor de 9 y 12 es 3, ya que de los divisores positivos comunes de 9 y 12 el mayor es 3. Nosotros nos basaremos en la siguiente definici´on: Definici´ on 1. Dados dos enteros a, b ninguno nulo, M´aximo Com´ un Divisor de a y b que notaremos (a, b), ser el entero positivo c tal que: i) c|a y c|b. ii) Si x|a y x|b entonces x|c. La condici´on i) nos indica que c debe ser un com´ un divisor y la condici´on ii) no se˜ nala que es el m´aximo. En los ejercicios 4 y 5 se da una necesaria discusi´on sobre esta definici´on. La siguiente proposici´on nos permite hablar del m.c.d. de tres o mas n´ umeros. *

UIS

1

Proposici´ on 1. ((a, b), c) = (a, (b, c)) Demostraci´on. Sean d = (a, b), e = (b, c), f = (a, e) y g = (d, c) debemos demostrar que g = f. Por ser g = (d, c) entonces g|d y g|c. Por ser d = (a, b) y g|d tenemos que d|a y d|b o sea se tiene que g divide a a, b y c. Pero si g divide a b y a c entonces g debe dividir a e = (b, c) y como tambi´en divide a a entonces g—f. De manera similar se ve que f |g lo que implica que g = kf , pero como ambos son positivos concluimos que g = f . Para hallar (n, m) un m´etodo muy antiguo, llamado el algoritmo de Euclides, consiste en hacer divisiones sucesivas, como mostraremos en el siguiente ejemplo para enseguida formalizar: Ejemplo 1. Para hallar (32, 18) dividimos 32 entre 18 y obtenemos como residuo 14, luego dividimos 18 entre 14 obteniendo como residuo 4, enseguida dividimos 14 entre 4 y obtenemos residuo 2, y al dividir 4 entre 2 obtenemos residuo 0. Como 2 es el u ´ltimo residuo no nulo, 2 es el m´aximo com´ un divisor de 32 y 18. Dividendo Divisor 32 18 18 14 14 4

Residuo 14 4 2 (32,18)

Cuadro 1: Divisiones sucesivas para encontrar (32, 18) seg´ un el algoritmo euclidiano.

Proposici´ on 2. (Algoritmo Euclidiano) Si a y b son enteros positivos por el algoritmo de la divisi´ on (Propiedad 6-1 Cap´ıtulo 1) podemos encontrar r1 , ..., rk y q1 , ..., qk+1 tales que: a = bq1 + r1 b = r 1 q2 + r 2 r 1 = r 2 q3 + r 3 .. .

0 < r 1 < b = r0 0 < r2 < r1 0 < r3 < r2 .. .

rk−3 = rk−2 qk−1 + rk−1 rk−2 = rk−1 qk + rk rk−1 = rk qk+1

0 < rk−1 < rk−2 0 < rk < rk−1

(1)

de esta forma, el u ´ltimo residuo no nulo rk , es el m´ aximo com´ un divisor de a y b. Demostraci´on. Vamos a proceder por inducci´on sobre k, que es el n´ umero de pasos que hay en el proceso. Notemos que el proceso se detiene cuando rk+1 = 0 pues no se puede hacer la siguiente divisi´on. i) Si k = 0 o sea el primer residuo r1 es 0, entonces a es m´ ultiplo de b y por tanto (ejercicio 2) el m´aximo com´ un divisor es b.

2

ii) Supongamos que se tiene demostrado cuando hay s´olo k−1 residuos, entonces empecemos el proceso en la segunda ecuaci´on de (1) o sea en b = r1 q1 + r2 . Partiendo de esta ecuaci´on hasta llegar a la u ´ltima tenemos k−1 residuos no nulos, entonces por hip´otesis de inducci´on podemos decir que rk = (b1 , r1 ). Tenemos: 1. rk |b y rk |r1 2. x|b y x|r1 ⇒ x|rk . Como r0 > r1 > ... > 0 entonces alg´ un rk+1 debe ser cero, esto nos garantiza que el proceso descrito en (1) es finito. Pero a = bq1 + r1 entonces rk |a y tenemos que i)0 rk |a y rk |b. Ahora bien, si x|a y x|b entonces x|a − bq1 o sea x|r1 y por ii) tenemos que x|rk , por tanto: ii)0 Si x|a y x|b entonces x|rk . i)0 e ii)0 nos garantizan que (a, b) = rk con lo cual queda demostrada la proposici´on.

Corolario. Si a y b son enteros, un n´ umero de la forma αa + βb con α, β ∈ Z es una combinaci´ on lineal de a y b. La menor combinaci´ on lineal positiva de dos enteros no nulos es el m´aximo com´ un divisor. Ejemplo 2. Para expresar (32, 18) como combinaci´on lineal de 32 y 18 podemos recurrir al algoritmo euclidiano pero en sentido inverso. Seg´ un este (tabla 1) tendr´ıamos: 32 = 18 × 1 + 14 18 = 14 × 1 + 4 14 = 4 × 3 + 2 4=2×2

(2)

Entonces de la pen´ ultima ecuaci´on tenemos: 2 = 14 − 4 × 3. Pero 4 = 18 − 14 × 1 entonces 2 = 14−(18−14×1), 3 = 14×4−18×3 y como 14 = 32−18 entonces 2 = (32−18)×4−18×3 = 32 × 4 + (18) × (−7) y hemos encontrado α = 4 y β = −7 tal que 2 = (32, 18) = 32α + 18α. Este proceso es el que utilizamos para la demostraci´on general. Demostraci´on. N´otese primero que si x es combinaci´on lineal de n y m, y a la vez m es combinaci´on lineal de n y m0 , entonces x es combinaci´on lineal de n y m0 (ejercicio 6). Por esta raz´on y seg´ un las ecuaciones de (1) vemos que rk es combinaci´on lineal de rk−1 y rk−2 y a la vez rk−1 es combinaci´on lineal de rk−2 y rk−3 entonces rk es combinaci´on lineal de rk−2 y rk−3 . Por este proceso “vamos subiendo” hasta llegar a que rk es combinaci´on lineal de r1 y b, pero como r1 es combinaci´on lineal de a y b; vemos que rk , el m´aximo com´ un divisor, es combinaci´on lineal de a y b. Por otra parte, el m´aximo com´ un divisor divide a a y divide a b y por tanto a cualquier combinaci´on lineal de a y b y se deduce que es la menor de todas las combinaciones lineales positivas de a y b. Definici´ on 2. a y b se llaman primos relativos si y s´olo si (a, b) = 1. 3

Proposici´ on 3. (Lema de Euclides) Supongamos que a y b son primos relativos y que a|bc entonces a|c. Demostraci´on. Como (a, b) = 1, seg´ un el corolario anterior existen α, β ∈ Z, tales que 1 = αa + βb multiplicado por c a ambos lados obtenemos que c = αac + βbc, como a|bc y a|ac entonces a|c. El siguiente resultado, cuya demostraci´on se deja como ejercicio al lector, establece un m´etodo muy usado para construir el m´aximo com´ un divisor de dos n´ umeros: Se descomponen en factores primos y se escogen aquellos factores comunes con su menor exponente. Proposici´ on 4. Si las descomposiciones en factores primos de a y b son: a = pα1 1 pα2 2 . . . pαnn y β

β

b = p1 1 p2 2 . . . pβnn entonces el m´aximo com´ un divisor de a y b, (a, b) tiene como descomposici´ on en factores primos γ γ p1 1 p2 2 . . . pγnn donde γ i es el m´ınimo entre αi y β i .

Ejercicios 1. Encontrar el m´aximo com´ un divisor de los siguientes pares de enteros. Expresarlo como combinaci´on lineal de los dos n´ umeros: a) 52, 38

b) 81, 110

c) 320, 112

d ) 7469, 238

2. Demuestre que (a, ka) = a (con a > 0) y que (1, a) = 1 3. Demuestre que la definici´on 1 es una buena definici´on. Es decir, que si dos n´ umeros c 0 0 y c cumplen la definici´on se debe tener c = c . 4. El m´aximo com´ un divisor de a y b se puede definir como aquel entero c tal que: i) c|a y c|b. ii) x|a y x|b implica x < c. Demostrar que esta definici´on es equivalente a la definici´on 1 (para esto, suponga que c0 cumple la definici´on 1 y que c cumple la anterior definici´on y deduzca que c0 = c). 5. Demostrar que (a, b) = (a, b + ka) para todo k. 6. Si x es combinaci´on lineal de n y m, y a la vez m es combinaci´on lineal de n y m0 entonces x es combinaci´on lineal de n y m0 . 7. Demostrar que a y b son primos relativos si 1 se puede expresar como combinaci´on lineal de a y b. 4

8. Si m es un entero positivo, demostrar que (ma, mb) = m(a, b). 9. Demostrar que si p es un n´ umero primo y a es un entero entonces o (a, p) = 1 o (a, p) = p. 10. Si p y q son primos distintos entonces (p, q) = 1 11. Probar que (a, bc) = 1 si y solo si (a, b) = 1 y (a, c) = 1. 12. Si x = yz + t , probar que (x, z) = (z, t). 13. Si a y b son primos relativos y c pertenece a los enteros positivos entonces: i) existen α y β tales 1 = αa + βb. ii) (a − b, a + b) es 1 o 2. iii) Si a|bc entonces a|c. iv) Si a|c y b|c entonces ab|c. v) (c, ab) = (c, a)(c, b). 14. ¿C´omo es (a2 + b2 , a + b) sabiendo que (a, b) = 1? 15. Pruebe que si a es par y b es impar entonces (a, b) = ( a2 , b). 16. Probar que si c|ab entonces c|(a, c)(b, c). 17.

a) Sup´ongase que (a, b) = 1. Pruebe por inducci´on que (an , b) = 1 (Utilice el resultado del problema 11). b) Demuestre que si (a, b) = 1 entonces (an , bn ) = 1. c) Usando b) demostrar que si a y b son enteros tales que an |bn entonces a|b.

18. Si d = (a, b), a = a0 d y b = b0 d, demostrar que (a0 , b0 ) = 1. 19. Demostrar la proposici´on 4 (utilice los resultados del ejercicio 17 de la secci´on 6). 20. Demuestre que el corolario de la proposici´on 2 implica lo siguiente: “Si los m´ ultiplos de a se marcan en rojo sobre una recta y los m´ ultiplos de b en verde donde a y b son enteros positivos cuyo m´aximo com´ un divisor es g, entonces g ser´a la distancia m´as corta de cualquier punto verde a cualquier otro rojo”. 21. Sup´ongase que ab y dc son dos fracciones reducidas a su expresi´on m´as simple ((a, b) = (c, d) = 1). Demostrar que si ab + dc = ad+bc es un entero entonces b = d o b = −d. bd 22. En base a la proposici´on 4 demostrar que si dos n´ umeros a y b son primos relativos y su producto es un cuadrado, entonces cada uno es un cuadrado perfecto. Deducir esta misma proposici´on del resultado establecido en el ejercicio 13. 23. Definir formalmente m´ınimo com´ un m´ ultiplo. Demostrar que ´este se puede obtener multiplicando los dos n´ umeros y dividiendo el producto por el m´aximo com´ un divisor. Demostrar finalmente que tambi´en se puede obtener descomponiendo en factores primos y formando el producto de todos los primos cada uno con su mayor exponente. 5

24. Definir recursivamente el m´aximo com´ un divisor de n n´ umeros. Definir recursivamente combinaci´on lineal de n n´ umeros. Demostrar que el m´aximo com´ un divisor de n n´ umeros es la menor combinaci´on lineal positiva de estos n n´ umeros. 25. Formalizar la demostraci´on dada para el colorario de esta secci´on procediendo por inducci´on sobre k. 26.

a) Demostrar que si b y c son enteros positivos tales que bc es un cuadrado perfecto y (b, c) = 1 entonces ambos b y c son cuadrados perfectos. b) En base a la anterior demuestre que no existen enteros a y b tales que a2 = 2b2 (esto demuestra que ra´ız de dos no es racional!). c) Probar que no existen enteros no nulos a y b tales que a2 = 3b2 . d ) Si n es un entero positivo que no es cuadrado perfecto probar que no existen enteros no nulos a y b tales a2 = nb2 .

ECUACIONES LINEALES DIOFANTINAS Un problema adivinanza t´ıpico es el siguiente: Mar´ıa compra pollos a $50 y patos a $70, con un costo total de $530 ¿Cu´antos pollos y cu´antos patos compr´o? Haciendo x el n´ umero de pollos e y el n´ umero de patos tenemos la ecuaci´on 50x + 70y = 530 que es equivalente a 5x + 7y = 53

(3)

Es claro que la soluci´on x e y deben ser enteras y positivas, pues no se conciben respuestas de patos ni tampoco (−3) pollos. Ecuaciones como ´estas en que las como 34 de pollos y 85 9 soluciones deben ser enteras se denominan Ecuaciones diofantinas en honor a Diofantus (S. III D.C.), matem´atico de la “segunda escuela alejandrina” y que es considerado pionero del ´algebra y la teor´ıa de n´ umeros. En su aritm´etica Diofantus da “recetas” para resolver ´estas y otras ecuaciones. Es claro que la teor´ıa de n´ umeros es el estudio de ecuaciones diofantinas en gran parte, as´ı pues el “Ultimo Teorema de Fermat” establece la imposibilidad de resoluci´on de ciertas ecuaciones diofantinas. Por ahora, vamos a trabajar con algunas ecuaciones lineales diofantinas, como la ecuaci´on (3). Con los elementos que tenemos sobre m´aximo com´ un divisor podemos justificar el procedimiento que se ilustra en el siguiente ejemplo: Ejemplo 3. Sabemos que (5, 7) = 1; existe, seg´ un el corolario de la secci´on anterior, una soluci´on a la ecuaci´on 5α + 7β = 1 Sea esta α = 3 y β = −2. Podemos entonces conocer una soluci´on entera para la ecuaci´on (3) a saber: x0 = 53α = 159, y0 = 53β = −106 ¿Hay otras soluciones a la ecuaci´on? Supongamos que x, y es otra soluci´on, ¿c´omo es? Tendr´ıamos 5x + 7y = 53, 5x0 + 7y0 = 53 Restando estas dos ecuaciones tenemos: 5(x − x0 ) = 7(y0 − y) 6

(4)

Como (5, 7) = 1 y se tiene 5|7(y0 − y). El Lema de Euclides (proposici´on 3 de la secci´on anterior) nos permite deducir que 5|(y0 − y) es decir que para alg´ un t entero 5t = y0 − y de donde tenemos que y = y0 − 5t = −106 − 5t Para encontrar los valores de x reemplazamos (y0 − y) en (4) por 5t y obtenemos: 5(x − x0 ) = 7 × 5t de donde x − x0 = 7t o sea que x = 7t + x0 = 159 + 7t. Tenemos entonces que: x = 159 + 7t y = −(106 + 5t)

(5)

Dando valores a t, obtenemos soluciones para la ecuaci´on 3 as´ı para t = 0, 1, 2, 3... se tiene x = 159, 166, 173, 180y = −106, −111, −116, −121. Ya hab´ıamos dicho que nos interesan s´olo las soluciones positivas. ¿Cu´ales t hacen a x e y positivos? Seg´ un (5) tendr´ıamos: 159 + 7t > 0 y −106 − 5t > 0 desigualdades que al despejar t nos indican: 159 t>− 7 y 106 t 0 y y > 0. 4. Sean m y n enteros diferentes. ¿Cu´antos fraccionarios con denominador n o m hay entre 1 y 0? ¿Cu´al es la menor distancia entre dos fracciones de ´estas? 5. Encontrar una soluci´on general para la ecuaci´on 1321x + 5837y + 1926z = 2983. 6. Cuando el Se˜ nor Gonz´alez en 1911 cambi´o su cheque por x pesos con y centavos, el cajero se equivoc´o y pag´o y pesos con x centavos. El Se˜ nor Gonz´alez recibi´o el doble de la cantidad mas dos centavos. ¿De cu´anto era el cheque? 7. Encontrar la forma general de las soluciones a la ecuaci´on (6) cuando ´estas existen. 8. ¿Qu´e tan separados est´an los puntos enteros de la recta 7x + 5y = 53 9. Demostrar que cuando (a, b) = 1 entonces ab < 0 si y s´olo si existe un n´ umero infinito de soluciones positivas (x > 0, y > 0) para la ecuaci´on ax + by = c. 10. Resolver en forma general los siguientes sistemas de ecuaciones para x, y, z enteros. a) 2x + 3y + z = 25

c) 4x + 6y − 2z = 12

b) 12x + 16y − 4z = 4

d ) 7x + y + z = 3

11. Determinar las condiciones necesarias y suficientes para que las ecuaciones ax+by+cz = d y a0 x + b0 y + c0 z = d0 tengan soluciones en enteros. Exhibir un m´etodo general para encontrar la forma general de las soluciones.

La Relaci´ on de Congruencia entre enteros. Con base en los resultados obtenidos en la secci´on 8 desarrollaremos una notaci´on muy u ´til dentro de la teor´ıa de n´ umeros, notaci´on introducida por Gauss. Definici´ on 3. Siempre que m|(a − b) diremos que a es congruente con b m´odulo m y se notar a ≡ b (m´od m)) (s´olo se exige que m sea diferente de 0). Esta notaci´on puede interpretarse como que a y b al dividirse por m tienen el mismo residuo. En efecto, si a y b tiene el mismo residuo al dividirse por m se tiene: a = k1 m + r y b = k2 m + r que implica (a − b) = (k1 − k1 )m, o sea que, m|(a − b).

9

Por otra parte, como 0 es el u ´nico m´ ultiplo de m que est´a entre −m y m si a ≡ b aplicando algoritmo de la divisi´on tendremos

(m´od m),

a = q1 + r 1 ; b = q2 + r 2 con 0 < r1 < m y 0 < r2 < m; por tanto m|(a − b) y (a − b) = (q1 − q2 )m + (r1 − r2 ) se sigue que m|(r1 − r2 ) pero r1 − r2 debe estar entre −m y m por tanto, r1 − r2 = 0 o sea los residuos r1 y r2 deben ser iguales. Hemos demostrado la siguientes caracterizaci´on. Proposici´ on 7. a ≡ b m.

(m´od m) si y s´ olo si a y b tienen el mismo residuo al dividirlos por

Ejemplo 5. Seg´ un el algoritmo de la divisi´on al dividir por 4 se puede obtener un u ´nico residuo entre 0 y 3 y por lo tanto un n´ umero debe ser de una u ´nica forma: 4n, 4n + 1, kn + 2 o 4n + 3. Esto nos ayuda a demostrar, por ejemplo, que todo n´ umero cuadrado es un m´ ultiplo de 4 o es de la forma 4n + 1 (Proposici´on 2 secci´on 6). Los n´ umeros de la forma 4n, los m´ ultiplos de 4, son congruentes entre s´ı, m´odulo 4. Los de la forma 4n + 1, por ejemplo 41 y l009, son congruentes entre s´ı todos. Lo mismo sucede con los de la forma 4n + 2 y por su lado con los de la forma 4n + 3. Hacer congruencias m´odulo 4 es pues, formar los n´ umeros enteros en “grupos” como se ve en la tabla ··· ··· ··· ···

−4 −3 −2 −1

0 1 2 3

4 5 6 7

··· ··· ··· ···

Cuadro 2: Los n´ umeros de cada fila son congruentes entre si m´odulo 4.

En estos ”grupos”que se forman, la relaci´on de congruencia m´odulo 4 hace el papel de igualdad. Esto nos garantiza en forma general el siguiente resultado. Proposici´ on 8. La relaci´on “ser congruente pmodm” es una relaci´ on de equivalencia en los enteros, es decir, se cumplen las siguientes leyes: Reflexiva : Siempre a ≡ a (m´od m). Sim´ etrica : Si a ≡ b

(m´od m) ⇒ b ≡ a (m´od m).

Transitiva : Si a ≡ b

(m´od m) y b ≡ c

(m´od m) ⇒ ac

(m´od m).

Demostraci´on. A manera de ilustraci´on hacemos la demostraci´on de la simetr´ıa. La reflexiva y transitiva quedan a cargo del lector. Simetr´ıa: Si a ≡ b (m´od m) seg´ un la definici´on 3, m|b − a lo que implica que m| − (b − a) o sea m|a − b que significa que b ≡ a (m´od m). Adem´as de ser la relaci´on de congruencia una relaci´on de equivalencia, tiene otra caracter´ıstica que la hace supremamente u ´til: es compatible con la suma y la multiplicaci´on de enteros. Esto es lo que indica el siguiente resultado. 10

Proposici´ on 9. Si a ≡ b a + c ≡ b + c (m´od m).

(m´od m) para cualquier c entero se tiene ac ≡ bc

(m´od m) y

Demostraci´on. Si a ≡ b (m´od m) por definici´on m|b − a entonces m|c(b − a) y por lo tanto m|cb − ca lo que indica que ca ≡ cb (m´od m). As´ı mismo, si m|b − a entonces m|(b + c) − (a + c) por tanto a + c ≡ b + c (m´od m). Ejemplo 6. Sabemos que 10 ≡ 1 (m´od 9) por la proposici´on anterior vemos que 102 ≡ 10 (m´od 9) y aplicando que la relaci´on de congruencia es sim´etrica y transitiva vemos que: 102 ≡ 10 (m´od 9) y 10 ≡ 1 (m´od 9) ⇒ 102 ≡ 1 (m´od 9) multiplicando por el mismo n´ umero 3 vemos que 3×102 ≡ 3 (m´od 9) entonces 3×102 +1 ≡ 4 (m´od 9) o sea que 301 ≡ 4 (m´od 9). Resumidamente se ha visto que como 10 ≡ 1 (m´od 9) entonces (3(10)2 + 1) ≡ (3(1)2 + 1) (m´od 9). En el ejercicio 10 se pide demostrar que si a +c ≡ b +c (m´od m) entonces a ≡ b (m´od m). Esta es una justificaci´on para la ley cancelativa de la suma en congruencia. Se podr´ıa esperar tener una ley parecida para el producto pero se puede buscar un contraejemplo r´apidamente, as´ı cuando m = 24 se tiene 1 × 6 ≡ 5 × 6 y sin embargo no es cierto que 1 ≡ 5 (m´od 24). La siguiente proposici´on nos indica cu´ando es posible cancelar factores comunes en una congruencia. Proposici´ on 10. Si (m, c) = 1 y ac ≡ bc

(m´od m) entonces a ≡ b

(m´od m).

Demostraci´on. Si ac ≡ bc (m´od m) entonces m|(b − a)c, como (m, c) = 1 seg´ un la u ´ltima proposici´on de la secci´on 8 concluimos que m|b − a y por lo tanto a ≡ b (m´od m). Una generalizaci´on de este resultado se encuentra en el ejercicio 12. Definici´ on 4. Un conjunto de n´ umeros {a0 , a1 , ..., am−1 } es un sistema completo de residuos m´odulo m si en ´el hay uno y s´olo un representante de cada residuo al dividir por m. En otras palabras se deben cumplir dos condiciones: i) i 6= j ⇒ ai no es congruente con aj

(m´od m).

ii) Para cualquier entero a existe un 0 ≤ i < m tal que:ai a

(m´od m).

La primera condici´on indica que no hay en {a0 , a1 , ..., am−1 } dos n´ umeros con el mismo residuo, la segunda condici´on asegura que ah´ı est´an todos los residuos posibles. Ejemplo 7. Para buscar un sistema completo de residuos m´odulo 4, seg´ un la figura 1, basta tomar 4 enteros, cada uno de una fila diferente. As´ı el conjunto {0, −3, 6, 11} es un sistema completo de residuos m´odulo 4, mientras si tomamos {6, 10, 5, 8} no es un sistema completo de residuos pues 6 ≡ 10 (m´od 4) y adem´as no hay ninguno que tenga residuo 3. Fijemos nuestra atenci´on en el s.c.r. {8, −3, 6, 11} teniendo en cuenta las proposiciones 2 y 3 vemos que: 8+(−3) ≡ (−3) y 6+11 ≡ (−3) y 6+(−3) ≡ 11, etc. y as´ı con el producto 11×11 ≡ −3 y (−3) × 11 ≡ 11 y 6 × 11 ≡ 6, etc. Podemos resumir esto haciendo tablas de multiplicar y sumar tendremos: × 8 −3 6 11

+ 8 −3 6 11 8 8 −3 6 11 −3 −3 6 11 8 6 6 11 8 −3 11 11 8 −3 6 11

8 −3 6 11 8 8 8 8 8 −3 6 11 8 6 8 6 8 11 6 −3

En este sistema completo de residuos el 8, por ejemplo, representa todos los n´ umeros que tienen el mismo residuo que ´el al ser dividido por 4: todos los m´ ultiplos de 4; −3 representa los n´ umeros de la forma 4n + 1; el 6 los de la forma 4n + 2 y 11 a los de la forma 4n + 3. Un sistema can´onico de residuos equivalente al anterior ser´ıa {0, 1, 2, 3} en donde las tablas nos quedan: Tablas 2. + 0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

× 0 1 2 3

3 3 0 1 2

0 0 0 0 0

1 0 1 2 3

2 0 2 0 2

3 0 1 2 1

N´otese que aqu´ı 3 × 3 ≡ 1 indica que dos n´ umeros de la forma 4n + 3 multiplicados nos da uno de la forma 4n + 1. Definici´ on 5. Cuando hablemos de la aritm´etica m´odulo m nos referiremos a las operaciones entre los n´ umeros 0, 1, 2, .., (m − 1) seg´ un la relaci´on de congruencia (m´od m). Los c´alculos en la aritm´etica m´odulo m se hacen como en los n´ umeros en cuanto se cumplen propiedades como la distributiva, las dos operaciones sin conmutativa y modulativa etc. Sin embargo hay una diferencia importante: la ley cancelativa para el producto es m´as restringida en la aritm´etica m´odulo m seg´ un la proposici´on 10. Por otra parte cuando el m´odulo es primo podemos hablar de inversos multiplicativos lo cual no sucede en los enteros, donde los u ´nicos que tienen inversos multiplicativos son..... Estas propiedades b´asicas son formalizadas en la siguiente afirmaci´on. Proposici´ on 11. (Propiedad de la aritm´ etica mod. m). i) Ley cancelativa para la suma: a + x ≡ a + y ⇒ x ≡ y. ii) Para todo a y b existe un u ´nico x tal que: a + x ≡ b. iii) Si m es primo para todo a no congruente con 0 y todo b, existe un u ´nico x tal que: ax ≡ b. iv) Si m es primo para todo a no congruente con 0, todo b y c existe un u ´nico1 x tal que: ax + b ≡ c. Demostraci´on. i) Si a + x ≡ a + y (m´od m) entonces m|(a + x) − (a + y) lo que implica que m|x − y o sea que x ≡ y (m´od m). ii) Vemos primero que para todo a existe (−a) tal que a + (−a) ≡ 0. H´agase simplemente (−a) = m − a cuando a > 0 y (−0) = 0. Para resolver la ecuaci´on a + xb (m´od m) t´omese x ≡ b + (−a) (m´od m) y se tendr´a: a + x ≡ a + (b + (−a)) ≡ b

mod m

. 1´

Unico como residuo, es decir, don soluciones son congruentes m´odulo m

12

iii) Consideremos los residuos 0, a, 2a, ..., (m − 1)a. Entre estos residuos no pueden existir dos repetidos pues si ia ≡ ja como m es primo, (m, a) = 1 y podemos aplicar la proposici´on 10 obteniendo i ≡ j o sea i = j. Esta consideraci´on nos garantiza que entre 0, a, 2a, ..., (m − 1)a no hay dos residuos iguales y por lo tanto {0, a, 2a, ..., (m − 1)a} es un sistema completo de residuos m´odulo m entre los cuales debe estar la clase residual de b, por tanto existe un x tal que ax ≡ b (m´od m). Tal x es u ´nico como residuo,en virtud de la proposici´on 10. La parte cuatro de la demostraci´on se deja como ejercicio al lector. La demostraci´on de la parte 3, como ya se indic´o, es b´asica y sutil. Su argumento lo resaltamos en la siguiente proposici´on que ser utilizada mas adelante. Proposici´ on 12. Si a no es congruente con 0 m´ odulo m cuando m es primo, entonces el conjunto {0, a, 2a, ..., (m − 1)a} es un sistema completo de residuos. Como consecuencias de la proposici´on 12 encontramos la parte iii) de la proposici´on 11, as´ı como el Teorema d´ebil de Fermat y el Teorema de Wilson, con los cuales cerramos esta secci´on. Proposici´ on 13. (Teorema d´ ebil de Fermat) Si p es primo y a no es m´ ultiplo de p, entonces: ap−1 ≡ 1 (m´od p) Demostraci´on. Seg´ un la proposici´on 12 los residuos 0, 1, 2, 3, ...., (m − 1) son exactamente los residuos de a, 2a, 3a, ..., (m − 1)a; salvo el orden. Por esta raz´on tenemos: 1 × 2 × ... × (p − 1) ≡ a × 2a × ... × (p − 1)a (m´od p) lo cual indica que: (p − 1)! ≡ (p − 1)!ap−1 y como (p − 1)! no es m´ ultiplo de p existe seg´ un la proposici´on 11 iii) existe un u ´nico x tal que: (p − 1)!x ≡ (p − 1)! (m´od p). Por tanto, ap−1 ≡ 1 (m´od p). Proposici´ on 14. (Teorema de Wilson) Si p es primo entonces: (p − 1)! − 1

(m´od p)

Demostraci´on. Sabemos que en 0, 1, 2, ..., (p − 1) est´an todos los residuos m´odulo p y adem´as que todo residuo no nulo a tiene su inverso multiplicativo a−1 (ejercicio 23). ¿Cu´ales residuos entre 1 y p − 1 tienen inverso igual a si mismo, es decir, para qu´e x se cumple xx ≡ 1 (m´od p)? Claramente para x ≡ 1 y x ≡ −1 se tiene. ¿Hay otros? Si p divide a x2 − 1, p debe dividir a (x − 1)(x + 1) o sea: (x − 1)(x + 1) ≡ 0 (m´od p) pero esto s´olo es posible cuando o bien x − 1 ≡ 0 (m´od p) o bien x + 1 ≡ 0 (m´od p) (v´ease ejercicio 15). Esto nos asegura que los u ´nicos residuos que elevados al cuadrado son congruentes con 1 son 1 y −1. O sea que cada uno tiene su inverso multiplicativo diferente salvo el 1 y −1 (o sea m − 1). Ahora bien, como p es impar hay p − 1 residuos no nulos de los cuales p − 3 (salvo el 1 y −1) tienen su inverso diferente, por tanto al multiplicar 2, 3, ..., (p − 2) tenemos un n´ umero par de residuos que se agrupan 2 a dos anul´andose todos, por lo tanto 2 × 3 × ... × (p − 2) ≡ 1 13

(m´od p)

y tenemos que (p − 1)! ≡ −1

(m´od p)

Para aclarar un poco el proceso seguido en estas u ´ltimas demostraciones analicemos un caso concreto. Ejemplo 8. Sea p = 7 y a = 4, seg´ un la aritm´etica m´odulo p (tabla 3) los elementos 0, 4, 2 × 4, 3 × 4, 4 × 4, 5 × 4 y 6 × 4 (la fila 5 de la tabla del producto) es un sistema completo de residuos (proposici´on 10) y por tanto (4 × 1) × (4 × 2) × (4 × 3) × ... × (4 × 6)1 × 2 × 3... × 6

(m´od 7)

y se tiene 46 × 6! ≡ 6!

(m´od 7)

lo que implica que 46 ≡ 1

(m´od 7)

como lo asegura el Teorema d´ebil de Fermat. + 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6

1 2 1 2 2 3 3 4 4 5 5 6 6 0 0 1 Tabla

× 0 1 2 3 3 4 5 6 3 4 5 6 0 0 0 0 0 4 5 6 0 1 0 1 2 3 5 6 0 1 2 0 2 4 6 6 0 1 2 3 0 3 6 2 0 1 2 3 4 0 4 1 5 1 2 3 4 5 0 5 3 1 2 3 4 5 6 0 6 5 4 para la suma y el producto modulo

4 0 4 1 5 2 6 3

5 0 5 3 1 6 4 2

6 0 6 5 4 3 2 1

7

Por otro lado, seg´ un la tabla 2 × 4 ≡ 1 y 3 × 5 ≡ 1, por tanto: 6! = 2 × 3 × 4 × 5 × 6 ≡ 6 ≡ −1

(m´od 7)

que es el teorema de Wilson. Preguntas y Ejercicios 1. Demostrar que la relaci´on de congruencia es reflexiva y transitiva. 2. Demostrar que si a ≡ b

(m´od m) y c ≡ d (m´od m) entonces, a+c ≡ b+d (m´od m).

3. Hacer las tablas de adici´on y multiplicaci´on m´odulo 11 y 12 y encontrar todos los residuos x que en cada caso cumplan la ecuaci´on dada: a) 3x ≡ 6 b) 3x ≡ 6 c) 3x ≡ 7

(m´od 11) (m´od 12) (m´od 11)

d ) 3x ≡ 7 (m´od 12) e) x2 ≡ 1 (m´od 11) f ) x2 ≡ 8 (m´od 12) 14

g) x2 ≡ 3

(m´od 11)

4. Qu´e horas indica el reloj si: a) 29 horas antes indicaba las 11. b) 100 horas antes eran las 2.

c) 50 horas despu´es ser´an las 6.

5. Determine la forma de todos los enteros que cumplen a la vez cada par de congruencias: a) x ≡ 3

(m´od 7) y x ≡ 4

(m´od 9)

b) x ≡ 5

(m´od 6) y x ≡ 8

(m´od 1)2

6. Explicar en t´erminos de congruencias (m´odulo 4): a) El doble de un impar sumado con un m´ ultiplo de 4 es un n´ umero de la forma 4n + 2. b) Un n´ umero no primo de la forma 4n+3 tiene al menos un divisor diferente de ´el, de la forma 4n+3. c) Lo anterior no es cierto si cambio 4n + 3 por 4n + 1. 7. ¿Qu´e se puede concluir de que a2 ≡ b2

(m´od p) cuando p es primo?

8. En la aritm´etica m´odulo m se puede hablar de algoritmo de la divisi´on? 9. Encontrar todas las triplas (x, y, z) m´odulo 5, tales que x2 + y 2 = z 2 10. Demostrar que si a + b ≡ c + b

(m´od m) entonces a ≡ c

(m´od m).

11. Demostrar que si n es entero positivo impar entonces 1 + 2 + 3 + ... + (n − 1) ≡ 0

(m´od n)

12. Sea p(x) un polinomio con coeficientes enteros. Demostrar que x ≡ y que f (x) ≡ f (y) (m´od m). 13. Sea (m, c) = d y m = dn; si ac ≡ bc

(m´od m) entonces a ≡ b(modn).

14. Demostrar que si p es primo xp + y p ≡ (x + y)p

(m´od p).

15. Demostrar que si p es primo ab ≡ 0 (m´od p) implica a ≡ 0 (m´od p). ¿Qu´e se puede decir si p no es primo? 16. Probar que cuando p es primo impar xp +y p ≡ 0 17. Siendo p primo ap ≡ a

(m´od m) implica

(m´od p).

18. Encuentre el residuo al dividir por 7:

15

(m´od p) o b ≡ 0

(m´od p) implica xp +y p ≡ 0(modp2 ).

a) 22131 + 512 . b) 2131 + 512 + 824 .

c) 2131 + 546 + 2 × 624 . d ) 21131 +15212 +3×18124 .

19. A qu´e congruencia de grado inferior a 7 es equivalente la congruencia: 2x17 + 6x16 + x14 + 5x12 + 3x11 + 2x10 + x9 + 5x8 + 2x7 + 3x5 + 4x4 + 6x3 + 4x2 + x + 2 ≡ 0 (m´od 7)? 20. Probar el teorema d´ebil de Fermat demostrando que (1 + 1 + ... + 1)p = (1 + 1 + ... + 1) siempre que el n´ umero de 1’s sea menor que p. 21. Si a0 , a1 , ..., am−1 es un sistema residual completo m´odulo m, entonces ka0 , ka1 , ..., kam−1 tambi´en lo es. Demostrar que esto se tiene si k es primo relativo con m. 22. Deducir un resultado similar al anterior para los enteros ka0 + 1, ka1 + 1, ..., kam−1 + 1. 23. Demostrar que si (a, m) = 1 entonces: a) Existe a−1 tal que aa−1 ≡ 1 b) Si ax ≡ 0

(m´od m).

(m´od m) entonces x ≡ 0

(m´od m).

24. Demostrar que cuando p es primo, si a0 , a1 , ..., an no son m´ ultiplos de p entonces a0 a1 ...an no es m´ ultiplo de p.

16