Download Taller 2

Universidad de Talca
Taller de Matemática 2010
Estudiantes de Enseñanza Media
Taller 2
Divisibilidad y Restos
Todos conocemos el concepto de número par (como también el de número impar). Decimos
que n ∈ ΙΝ es un número par si n es un múltiplo de 2, es decir si hay k ∈ ΙΝ tal que
n = 2 ⋅ k = 2k . Más general podemos hacer la siguiente definición:
Definición: Un número natural n se dice múltiplo de a ∈ ΙΝ si hay k ∈ ΙΝ tal que n = ak .
Ejemplo.
10 es un múltiplo de 5 (y también de 2); 14 es un múltiplo de 7; 540 es un múltiplo de 9, y
también es múltiplo de los siguientes 1, 2, 3, 4, 5, 6, 10, 12, 15, 18, 20, 27, 30, 36, 45, 54,
60, 90, 108, 135, 180 y 270 y de 540, más aún estos son los únicos números naturales de
los cuales 540 es múltiplo.
Si n es un múltiplo de a se dice también que a es un factor de n o también que a divide
a n o que n es divisible por a .
Preguntas:
1. ¿Es 37 ⋅ 4 divisible por 3?
2. ¿Es 2 3 ⋅ 3 divisible por 5?, ¿Es 2 3 ⋅ 5 divisible por 8?, ¿Es 2 3 ⋅ 5 divisible por 10?
3. ¿Es cierto que si un número natural es divisible por 3 y por 4 entonces es divisible por
12 = 4 ⋅ 3 ?
4. ¿Es cierto que si un número natural es divisible por 4 y por 6 entonces es divisible por
24 = 4 ⋅ 6 ?
En general sucede que si consideramos dos números naturales, digamos Ν y m (podemos
pensar que N > m ) entonces Ν no es un múltiplo de m . Por ejemplo si m = 2 entonces
podemos pensar que solo la mitad de todos los números naturales son múltiplos de 2. Si no
podemos expresar un número Ν como un múltiplo de 2 entonces Ν − 1 es un múltiplo de
2. Digamos Ν − 1 = 2 ⋅ q , cierto q ∈ ΙΝ ∪ {0} y entonces Ν = 2q + 1 .
Por lo tanto vemos que los números se dividen en dos tipos: los de la forma 2 p y los de la
forma 2q + 1 . Pero esto ya lo sabemos, los números naturales se clasifican en dos tipos
disjuntos, pares e impares.
¿Que sucede si en lugar de m = 2 consideramos otro número R como 3, 4, 9, 11, etc?
Estudiemos el caso R=3.
Si N es múltiplo de 3 estamos listos, pues N = 3q , cierto q . ¿Si N no es múltiplo de 3
entonces que hacemos?.
Instituto de Matemática y Física
1
Universidad de Talca
Taller de Matemática 2010
Estudiantes de Enseñanza Media
Observación: Dado un número natural
3q ≤ N < 3( q + 1) .
N
entonces hay
q ∈ ΙΝ ∪ {0} tal que
Ejercicio 1:
Para cada uno de los números: 4, 8, 17, 18, 19, 20, 21, 22, 23, 25, 51, 67, 76 encuentre el
q de la afirmación de arriba. Calcule para cada uno de estos N − 3q . ¿Que valores se
obtienen?
Ejercicio 2:
Realizar el mismo experimento con 4 en vez de 3. ¿Que valores se obtienen para N − 4q en
este caso?
Más general se puede demostrar lo siguiente:
Teorema: Dado N y m números naturales existen números naturales (posiblemente 0) q
y R tal que
N = mq + R con 0 ≤ R < m
R se llama resto de N modulo m .
Observemos que R = 0 si y solo si N es un múltiplo de m . También observamos que hay
m posibilidades para R , a saber 0, 1, 2, … , m − 1 .
Dos números N 1 y N 2 se dicen congruentes modulo m si ellos tienen el mismo resto
modulo m . En este caso anotamos N 1 ≡ N 2 mod(m ) .
Ejemplos: 6 ≡ 8 mod(2) , 16 ≡ 8 mod(4) , 6 ≡ 27 mod(3) .
Ejercicio 3:
Para cada uno de los siguientes m = 6, 11, 13 encuentre tres números que sean congruentes
entre ellos modulo m . Encuentre cinco números que no sean congruentes modulo
m = 6, 11, 13 .
Un ejemplo cotidiano del uso de esta idea es con las horas de los días, se cuentan modulo
24. Observamos que dos números N 1 y N 2 son congruentes modulo m si y solo si
N 1 − N 2 es un múltiplo de m .
Ejercicio 4:
¿Para que números positivos m es cierta la congruencia 75 ≡ 19 mod(m) ?
Ejercicio 5:
Instituto de Matemática y Física
2
Universidad de Talca
Taller de Matemática 2010
Estudiantes de Enseñanza Media
Cierto número natural entre 1 y 1200 deja restos 1, 2, 6 modulo 9, 11, 13 respectivamente.
¿Cuál es el número?
Teorema sobre los restos: La suma (el producto) de dos números naturales tiene el mismo
resto modulo m que la suma (el producto) de sus restos modulo m .
Ejercicio 6:
Para cada uno de Ν 1 = 2, 5, 7, 9, 12, 14 y N 2 = 3, 4, 6, 10, 13, 17 y m = 5, 7, 9 compruebe el
teorema anterior con sumas y productos.
Ejemplo-Ejercicio 7:
Pruebe que para cualquier número natural N se tiene que N 3 + 2 N es divisible por 3. De
esta forma se generan algunos múltiplos de 3. Por ejemplo para N = 2 obtenemos
8 + 4 = 12 , para N = 11 obtenemos 1353.
Solución. El número N puede tener tres restos modulo 3. A saber 0, 1 o 2.
•
Si N tiene resto 0 modulo 3 entonces N es múltiplo de 3 y por lo tanto N 3 y 2 N
también son múltiplos de 3 y como la suma de múltiplos de 3 es un múltiplo de 3
tenemos que N 3 + 2 N es múltiplo de tres.
•
Si N tiene resto 1 modulo 3 entonces usando el teorema (con el producto) vemos que
N 3 tiene resto 13 = 1 . Por otra parte como 2 tiene resto 2 por el teorema vemos que
2 N tiene resto 2 ⋅ 1 = 2 . En consecuencia (usando la parte de la suma del teorema)
vemos que N 3 + 2 N tiene resto 1+2=3 modulo 3. Pero 3 tiene resto 0 modulo 3. Y así
N 3 + 2 N tiene resto 0 modulo 3, esto es un múltiplo de 3.
•
Problema: Caso resto 2.
Ejercicio 8:
Usando la misma técnica, probar que cualquier número de la forma N 2 + 1 no es un
múltiplo de 3.
Ejemplo-Ejercicio 9:
Suponga que se sacan huevos de una cesta de la siguiente manera: de a 2 a la vez, de a 3 a
la vez, de 4 a la vez, de 5 a la vez o de 6 a la vez, siempre queda 1, pero cuando se sacan de
a 7 huevos a la vez no queda ninguno.
¿Cuál es el número mínimo de huevos que había en la cesta?
Solución. Sea x la cantidad de huevos en la cesta. El enunciado lo podemos expresar como
que x satisface las siguientes congruencias:
Instituto de Matemática y Física
3
Universidad de Talca
Taller de Matemática 2010
Estudiantes de Enseñanza Media
x ≡ 1 mod(2)
x ≡ 1 mod(3)
x ≡ 1 mod(4)
x ≡ 1 mod(5)
x ≡ 1 mod(6)
x ≡ 0 mod(7)
Usando la última congruencia vemos que:
•
•
•
•
x es un múltiplo de 7 y escribimos x = 7k1 cierto k1
insertando este valor de x en la penúltima congruencia obtenemos
7k1 = 6k1 + k1 ≡ 1 mod(6) por lo tanto k1 ≡ 1 mod(6) y entonces k1 − 1 = 6k 2 cierto k 2 y
así k1 = 6k 2 + 1 .
Por lo tanto x = 7k1 = 7(6k 2 + 1) = 42k 2 + 7 .
Insertando este valor en la congruencia modulo 5 obtenemos 2k 2 + 2 ≡ 1 mod(5) y
multiplicando esta a ambos lados por 3 obtenemos 6k 2 + 6 ≡ 3 mod(5) que es lo mismo
que k 2 + 1 ≡ 3 mod(5) , de donde k 2 ≡ 2 mod(5) . Por lo tanto k 2 − 2 = 5k 3 cierto k 3 .
Continuar este proceso y al llegar a la última congruencia elegir el menor valor posible para
el k correspondiente.
Ejercicio 10 (Brahmagupta, siglo 7 AC)
Al extraer huevos de una cesta de 2, 3, 4, 5, 6 a la vez, en la cesta quedan 1, 2, 3, 4, 5
huevos respectivamente. Al sacar de 7 huevos por vez no quedan huevos en la cesta. ¿Cuál
es el número mínimo de huevos que había en la cesta?
Problemas
Problema 1. Nunca es múltiplo de 3
Sea n un número entero. ¿Cuál de los siguientes números no es nunca un múltiplo de 3?:
2n + 1, n 2 , n( n + 1), 6n − 1, n 3 − 2
Problema 2. Contando múltiplos
Considere los 261 productos 0 ⋅ 260, 1 ⋅ 259, 2 ⋅ 258, L, 260 ⋅ 0 . ¿Cuántos de estos productos
son múltiplos de 260?
Instituto de Matemática y Física
4
Universidad de Talca
Taller de Matemática 2010
Estudiantes de Enseñanza Media
Problema 3. Una demostración
Usando la técnica del ejercicio 7, probar que n 5 + 4n es un múltiplo de 5. Probar que
n 3 − n es un múltiplo de 24 para cualquier n impar.
Problema 4. Repartición
Siete niños, por turno, reciben un caramelo. Cuando cada uno tiene 17 caramelos ya no se
puede seguir repartiendo equitativamente pero sobran caramelos. El número de caramelos
para repartir es mayor que 100. ¿Qué cantidad de caramelos podría haber como máximo
para repartir?
Problema 5. Cantidad de monedas
Una banda de 17 piratas robó un saco lleno de monedas de oro. Cuando trataron de dividir
la fortuna en partes iguales, quedaron 3 monedas. Lo que produjo una pelea entre ellos que
resulto en la muerte de un pirata. Decidieron repartir las monedas nuevamente, esta vez
sobraron 10 monedas. Otra pelea se produjo entre ellos y nuevamente un pirata murió. Al
repartir por tercera vez las monedas no sobro ninguna.
¿Cuál es el mínimo número de monedas que fueron robadas?
Problema 6. Encontrando un número enetro
Encuentre un entero que:
a. Tiene resto 1, 2, 5, 5 cuando se divide por 2, 3, 6, 12 respectivamente.
b. Tiene resto 2, 3, 4, 5 cuando se divide por 3, 4, 5, 6 respectivamente.
c. Tiene resto 3, 11, 15 cuando se divide por 10, 13, 17 respectivamente.
Instituto de Matemática y Física
5